Translate (AKA immediate implementation problem)

1. The problem is obvious that it should just be some data structures

• Segment tree CF474-D2-F

1. Just DP, e.g. CF489-D2-F

Converting from brute force

1. Sometimes it just works ??? this works especially well if you notice the input is extremely small
2. Meet in the middle to be square root smaller CF525-D2-E CF1006-D3-F
3. Backtracking to prune states
4. Memoization (this is just dp lol)

Look at something in a new way

1. 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!!
2. 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)

1. Sorting things

• CF732-D2-E
• CF474-D2-F

1. 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
2. Convert array to frequency array
3. Splitting bigger things to smaller things/combining smaller things to bigger things

Splitting input into interesting groups

1. Array problems -> fix one endpoint, interesting if we observe special properties as we extend right endpoint CF689-D2-D
2. 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
3. DP is a form of grouping?? many times it's hard cuz you can't find the important one CF489-D2-F
4. Rectangle -> consider length/width as independent things CF1284-Hello-D
5. Scanline -> intervals between event endpoints are interesting CF1284-Hello-D
6. When you need to compare things one-to-one correspondence -> Canonical representations
7. Order/smallest iteration that something repeats
8. Complementary counting
9. fix on something special to the problem and loop over/consider in terms of that
10. Freely do things until the last step, but the last step automatically gets taken cared of anyways
11. General independency

• e.g. Minimize Manhatten distance = minimize on Xs + minimize on Ys

1. = n is equivalent to (<= n) — (<= n-1)

Find sparse/discrete/distinctive elements (AKA we like BIGGGGGG things)

1. Binary exponentiation (when lots of identical things) CF702-EDU-E CF621-D2-E
2. There aren’t that many powers, powers are op CF732-D2-E
3. Using a number’s binary representation
4. Find representatives

• A character is sometimes enough to represent a whole string
• Winner of elimination games
• Endpoints of intervals are usually interesting

1. Not that many distinct prime factors for any reasonable number

Summarizing info

1. Preprocessing is op (range sums, segment tree)
2. DP space saving

• CF489-D2-F (Don't actually need to keep track of which row we are currently on)

1. Keep track of cumulative result as we scan for dp

Observe interesting things

1. "Intermediate value theorem"

• CF689-D2-D (As right endpoint exteneded, max only increases, min only decreases, so in between must be where max = min)

1. One choice affects another, intertwined => dp? flow?
2. Move by one consideration (THIS IS SUPER POWERFUL && NONOBVIOUS, SOMETIMES THIS KILLS PROBLEM IMMEDIATELY)
3. Symmetry
4. Things don't matter

• doesn't matter how many times you turn sth on/off, it only depends on parity

1. 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)
2. Increasing sequence??
3. 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
4. Simulating something once is easy, but tle when trying all inputs => binary search (especially if the problem asks for min/max)