The problem is obvious that it should just be some data structures
Segment tree CF474-D2-F
Just DP, e.g. CF489-D2-F
Converting from brute force
Sometimes it just works ??? this works especially well if you notice the input is extremely small
Meet in the middle to be square root smaller CF525-D2-E CF1006-D3-F
Backtracking to prune states
Memoization (this is just dp lol)
Look at something in a new way
Remove what seems to be impossible, NO it’s just not cause you don’t know some fancy technique, just try you best to convert the impossibility into something familiar!!
ROOT THE TREE, probably a third of random tree problems on cf can be solved with this, it’s pretty powerful, either can be direction recursion, or use do
CF486-D2-D (A bit different in that need to consider each node as a root)
Sorting things
CF732-D2-E
CF474-D2-F
JUST look at the array from left to right and consider elements one by one~ this works really well with permutation problems because permutations look hard but it becomes trivial when you actually just consider elements one by one Similarly, sometimes problems delete characters of a string/elements of array -> don’t think about how the string/array gets smaller, just think in terms of the original string/array
Convert array to frequency array
Splitting bigger things to smaller things/combining smaller things to bigger things
Splitting input into interesting groups
Array problems -> fix one endpoint, interesting if we observe special properties as we extend right endpoint CF689-D2-D
Group input into two buckets, where different methods apply for each bucket, AKA sqrt algorithms (27.1 in cases) CF1207-EDU-F CF797-EDU-E
DP is a form of grouping?? many times it's hard cuz you can't find the important one CF489-D2-F
Rectangle -> consider length/width as independent things CF1284-Hello-D
Scanline -> intervals between event endpoints are interesting CF1284-Hello-D
When you need to compare things one-to-one correspondence -> Canonical representations
Order/smallest iteration that something repeats
Complementary counting
fix on something special to the problem and loop over/consider in terms of that
Freely do things until the last step, but the last step automatically gets taken cared of anyways
General independency
e.g. Minimize Manhatten distance = minimize on Xs + minimize on Ys
= n is equivalent to (<= n) — (<= n-1)
Find sparse/discrete/distinctive elements (AKA we like BIGGGGGG things)
Binary exponentiation (when lots of identical things) CF702-EDU-E CF621-D2-E
There aren’t that many powers, powers are op CF732-D2-E
Using a number’s binary representation
Find representatives
A character is sometimes enough to represent a whole string
Winner of elimination games
Endpoints of intervals are usually interesting
Not that many distinct prime factors for any reasonable number
Summarizing info
Preprocessing is op (range sums, segment tree)
DP space saving
CF489-D2-F (Don't actually need to keep track of which row we are currently on)
Keep track of cumulative result as we scan for dp
Observe interesting things
"Intermediate value theorem"
CF689-D2-D (As right endpoint exteneded, max only increases, min only decreases, so in between must be where max = min)
One choice affects another, intertwined => dp? flow?
Move by one consideration (THIS IS SUPER POWERFUL && NONOBVIOUS, SOMETIMES THIS KILLS PROBLEM IMMEDIATELY)
Symmetry
Things don't matter
doesn't matter how many times you turn sth on/off, it only depends on parity
The process must stop at some point, it might seem you like you need to simulate to infinity, but actually you only need to do a finite number of times)
Increasing sequence??
Trick with "optimized can always look a certain way", this is when you go, let's say you have something that looks a certain way, then if you change it in some ways then it's even better -> oh so the optimized thing must look a certain way
Simulating something once is easy, but tle when trying all inputs => binary search (especially if the problem asks for min/max)
