SansPapyrus683

C++ Style Guide

The defaults of our coding style will be here. Anything not mentioned within will defer to what is specified in the link.

Naming Conventions

Variables and Functions

Variables are to be named using snake_case, like bruh_moment or jesus_mcphricking_christ. Acronyms are to be treated as their own word and will be written in all lowercase, like pratyay_istg.

Classes, Structs, and Namespaces

SansPapyrus683

first editorial that i can be informal in hooray

anyway the editorial is for this problem it's kinda misleading- they say that the prominence is h_min, when it's really the elevation - h_min

but anyways, this is a dsu problem, if dsu was awful and something you wanted to rage at every night (the 2d aspect doesn't make it any better)
i'll assume you know enough about dsu to not die on a simple problem about it

so you add the squares in one at a time from highest to lowest and link them to any previously added squares with some

SansPapyrus683

wow another solution in just a day
_{(does anyone even read these)}

but anyways i did this, and it basically gives you an array of 1e5 elements and a target n <= 1000
and then it asks you to find the smallest segment that has a subset which sums to that given target

this problem is really stupid because it asks for like this one really niche method of using two pointers

a simpler problem

SansPapyrus683

hi it's me again

i should probably make a cf blog or something but the people on there are more unpredictable than my history teacher

so i came upon this problem and god the editorial was awful

so we have a tree with nodes and values, normal crap
and they want us to find how many subtrees have a sum of t (t <= 100)

SansPapyrus683

hi i'm back with another solution thing
whatever you like to call it

so this time it's this problem from the codeforces educational portal or whatever

so this is a standard dsu problem, except this time you need to

1. get the value of a certain node
2. increment all the values of a set (given by a certain node) by some value

SansPapyrus683

alright
time for this unholy problem

oh my god i want to kill the author of this

not even joking
this problem was so hecking hard

but anyways, i want to make you suffer less on this problem if you decide to give up
so we have a normal tree w/ at most 400 nodes and we want to find a subtree of k nodes such that the number of edges connecting it to the rest of the tree is minimal

SansPapyrus683

usaco time
i've been doing some old problems that i failed at before
and one of them was this problem, and i thought the solution was hot garbage (no offense benq) so i'm deciding to write my own that actually makes sense

so
we have 10^5 line segments, standard stuff
and we want the sum of the complexities of each segment, where the complexity is the number of connected components in the union of a segment

SansPapyrus683

AHAHAHAHA I THREW DEC GOLD SO HARD
only managed to cumulatively solve one problem, that's how sad i am

my friends kept on asking me for help on this one silver problem, and to be fair, it is pretty hard
the fact that benq's editorial reads like some post-college math paper doesn't help either

(my solution requires knowledge of prefix sums tho)

but without further ado, here's my solution

SansPapyrus683

hi
december contest ptsd again
this problem again

since the problem explanation is too complicated, i'll just let you read the problem yourself, there's no way i'm going to explain it myself

ok i'll assume you read the thing

anyway just the first thing i did was write a brute force python script to

SansPapyrus683

"Domination". Look it up.

— Scout, TF2

after the dec contest, i have come to the conclusion that i suck a** at dp
so i was grinding cf and i came upon this problem that had the tag dp
but my solution was anything but that, so lemme just share my sol