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)

• Prefix sum (l, r) = (1, r)-(1,l-1) is just too op

1. 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
2. Where you store several cum arrays/fenwick trees, each for a certain remainder x modulo m

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)

How can we save?

1. Use set/map

• CF1284-Hello-D (So we can keep track of the maximum/minimum of endpoints of intervals we are looking at)
• CF525-D2-E (To quickly find number of subsets which add to a certain sum)

1. Amortized analysis CF732-D2-E
2. Sieve of Eratosthenes for analyzing complexity

DFS

1. Standard counting
2. Graph coloring
3. For 2d grid
4. Articulation points and bridges
5. SCC
6. Non obvious need to root the tree

Dijkstra

1. Standard
2. Fancier (keep track of something on top of distance)

other graphs

1. Construct another graph based on original
2. Can you go from source to destination with certain constraints
3. Consider connected components separately
4. Consider cycles
5. Connected tree -> spanning tree
6. Use dsu to union a component and treat is as one vertex

Sortings, relative order

1. Reverse index/what you are thinking about
2. Permutation inversions (ai > aj); useful to consider one element at a time
3. Permutation/sortings with pairs containing original array index
4. Somtimes sorting in an order helps solve the problem immediately (mentioned above)
5. Indices/subindices/subsub indices -> practice to get familiar with this, it's just complicated to understand, but once you understand the problem is easy
6. Using values as index
7. idx/j subroutine, e.g. get counts of each block in 1, 1, 2, 2, 2, 3, 3, 3, 2, 2, 1, 1, 1, 1
8. Use segment tree to store answer (forgot how exactly this works)

Local (greedy)

1. Lexicographical order — ALWAYS consider digit by digit
2. Powers of 2 consideration
3. Again, move by one consideration
4. Greedy where working out 1 or 2 things makes the rest work out

Global

1. Can sometimes turn quadratics into linear by aggregating
2. Double counting

Constructions

1. Yes/No question? Sometimes one of yes or no direction is trivial
2. Similarly, Even/odd consideration (sometimes the answer is always no for one of them)
3. Think in simple global structure, aka don't think the problem is too hard, there needs to be something that is easy to think about
4. Try to get rid of the condition in one go

Game theory

1. Typical DP
2. Some problems avoid the typical game theory dp thing Usually a big jump, where one player can just do something big and that's pretty much the end of game
3. Elimination games => consider winner

Number theory

1. Standard problem if you actually know all the basics
2. Problems almost solved after considering gcd/consider when things are relatively prime (get extra assumption if divide by gcd)

Misc

1. Algebra pattern finding, AKA simple induction; be careful with base case
2. PIE
3. WLOG one side is bigger
4. TRIE for non obvious xor problem, tho this is a bit overused so hopefully you won't see it ever again