Problem Solving

General methods

Use direct reasoning
Work specific to general
- Remove or impose restrictions on problem
Guess and check
- Solve examples
- Try as many versitile hypotheses as possible
- Notice a pattern
Work backwards
- If f(u) = v, find u = f^-1(v)
- Work from ending to beginning
Work opposite
- If f(u) = v, find all x : f(x) != v
- Use contrapositive
- Work by contradiction
Interpretation manipulation
- Solve equivalent problem
- Manipulate formulas
- Restate the problem in other words
- Solve dual form
- Look for a formula, solve an equation
- Draw a picture
Use known results, models, theorems
Bruteforce, exhaustion
Exploit special features
Is problem a special case?
- Do a simulation
Additional tips:
- identify subgoals

Algorithmic

Graphs:
- Floyd-Warshall (maybe use bit parallelism)
- Ford-Bellman, Dijkstra (E*logV, V^2), BFS for 0-1 edge weights, DFS
- Topological Sorting
- Minimum Spanning Tree
- Strongly Connected Components
- 2-SAT, Biconnected Components
- LCA
- Eulerian path
- Transform to Bipartite Graph
- Heavy Light decomposition
- MinCut / MaxFlow (of Min Cost), Max Matching
- Replace minCostMaxflow with maxflow
- Add edges one by one, maintaining connected components with disjoint sets.
- Disjoint sets, connected components.
Case analysis
- Write brute-force solution to find pattern
- Solve recurrence: GF, annihilator method or wolframalpha.com
- Find sequence: interpolation or oeis.org
DP
- Dynamic Proramming: shortest path for acyclic graph, knapsack, matrix chain, edit distance, mask, take/don't take, tsp
- Use <= instead of = for some parameter.
- use dp[a-b] instead of dp[a][b];
- Reverse dp[x]->answer into dp[answer]->x, push-dp: dp[i+x]<-dp[i]
- DP can use linear memory if dp[a][...]->dp[a-1][...]
- Start with a slow DP, then optimize it. (Segment Trees, Knuth optimization, convex hull, divide and conquer)
- Sprague-Grundy theorem
Greedy
- Make local decision which "cares"/optimizes for future
- Schedule theory (schedule problem, deadline problem,boxes problem, a+b a-b a/b sorting)
- Optimal loop invariant and induction
Combinatorics
- Inclusion-exclusion
- Independent classes
- Equivalence binary relation
- Burnside lemma
- Map combination from omega to set,multiset, ordered set or urdered multiset and use C,A,n^k,n!
Queries
- Segment Tree
- Treap
- Persistency
- Sqrt Split and Rebuild 0..Sqrt(n) or Sqrt(n)..2Sqrt(n)
- Sqrt Lazy Operation, Rebuild when Sqrt(n) operations
- Log(n) structures with O(n) rebuild
- KDTree (Sqrt(n) queries on all rectangle queries)
Merging small tree into a big one, obtaining O(n*log(n)) transitions
Brute Force, Precalculation, Precalculation on Prefixes / Suffixes
Bit-level parallelism
Counting Sort
Two Pointers
Meet In The Middle
Scan line with events
Binary search
Ternary search
Combine above: Binary search + Greedy, Binary search + DP , Binary Search + Two Pointers
SQRT-decomposition, Sparse Table, Query Caching
Offline query (Mo algorithm)
Segment Tree, Treap, Persistent Tree
Hashing, Suffix Array, KMP, LCP, Suffix Automata, Aho-Corasick
Matrices, Gauss Elimination, Linear algebra for xor - problems
Randomized algorithm, Random Search, Shuffle
Symmetric strategy
Pigeonhole principle
Solve inverse problem (min / max)
Simplex algorithm
Traverse tree in dfs-order, map subtrees to segments
Euler formula: V - E + F = 2
Tree center
Linearity of Expectation
Find solution for n-1. Use it to find solution for n.
Decompose complicated problem into simple cases
Random-restart hill climbing
Solve problem from the end
Simplify input
- Change of Coordinates X+Y, X-Y. Affine Transformation (c*x - d*y, -a*x + b*y)
- Consider d[i] = a[i] - b[i] instead of a[i] and b[i], or d[i] = a[i+1] - a[i]

Examples

Use Direct Reasoning

Direct reasoning is the simplest form of problem solving, you just apply your knowledge.

Problem: "You have 10 apples you ate 3. How many apples do you have now?"

The solution is 10-3=7 apples.

Work Specific to General

Very powerful principle. Assume there is a set soltuions {S} to solve problem P with or without contraint C. If you can prove that relaxed problem P' is not harder as the original (i.e. original problem can have relaxed constraint in input initally or can be solved by relaxed problem itself) the set of solutions to solve P' is {S'} which can be smaller subset of {S}! You had just reduced search space for free!

Example:

Problem: Find occurrence of string B in string A.
Redution: Whatever algorithm there may be it should be able to search string B if string B is 1 letter string. Therefore whatever algorithm there is - don't even try to find it if you can't solve problem for 1 letter.

Problem: You have some red and blue cards. The cost of i'th red card is R[i]-A and cost of i'th blue card is B[i]-B, where A and B is the amount of red and blue cards you already have. Find the order of purchases such that the total cost is minimized.
Reduction: Whatever algrithm there may be it should be able to solve the problem when all B[i]=0 (because it's a subproblem of original). Exploring this solution to this subproblem gives insights to the original one.

Problem: Find a formula rotating point (x,y) aroung point (a,b) by angle A.
Reduction: Whatever formula there may be it should be able to rotate around point (0,0). Assume you have found the formula for rotation around (0,0), then to rotate point (x,y) around (a,b) simply transfer the point to the origin (0,0), rotate it and then transfer it back: Rotate((x-a,y-b))+(a,b)

Guess and Check

Guess and check method is relied on pattern recognition and hypotheses: solve examples, make assumptions and notice a pattern.

Problem: "You have 2 numbers A and B, every next day you set number A=HarmonicMean(A,B)*ArithmeticMean(A,B)/B and B=HarmonicMean(A,B)*ArithmeticMean(A,B)/A. What are the numbers A and B after 100 days?"

This problem is easily solved by actually writing down these numbers and noticing that they remain the same. The solution is: after 100 days A will be equal to A and B will be equal to B

Problem 2: "N people walk into a bar, everyone makes a handshake pairwise, how many handshakes were made?"

Hypothesis: formula is a polynomial. Interpolating the polynomial you find: N*(N+1)/2 handshakes were made.

Work Backwards

Working backwards proposes you to find an invert function or restoring initial state of problem from a final solution and then backtracking.

Problem: "You have n houses on the x-axis with random coordinates, you need to place m people in these houses such that the minimal distance between neighbouring people is maximial."

Solving this problem directly might be difficult, you are trying tell from m people the maximal distance - build an invert statement: tell how many people you can fit in these houses using fixed distance. if you can't fit m people - decrease your distance, otherwise increase it.

Problem 2 (Polya's example): "How can you bring up from the river exactly 6 quarts of water when you have only two containers, a 4 quart pail and 9 quart pail, to measure with?"

Solve this problem by backtracking from the solution, you have 6 quarts in your 9 quart pail, you got this 6 quars either by poring 4 quart pail into 9 quart pail when it had 2 quarts of water OR you you poured 3 quarts from 9 quart pail, you could do it if 4 quart pail had 1 quart of water. Exploring first possibility yields no result, but exploring second yields the solution. Solution:

action	4 quart pail	9 quart pail
initial	0	0
fill 9 quart	0	9
pour into 4 quart	4	5
empty 4 quart	0	5
pour into 4 quart	4	1
empty 4 quart	0	1
pour into 4 quart	1	0
fill 9 quart	1	9
pour into 4 quart	4	6
empty 4 quart	0	6

Work Opposite

Working opposite requires you to do opposite of what your are trying to do

Problem: "If number n equals to p*q prove that either p or q <= sqrt(n)."

You are given a statement A and B and required to prove A->B, well, do the opposite: prove not(B)->not(A). The contrapositive statement is: "if p and q > sqrt(n) prove that p*q does not equal n". Now apply direct reasoning: if p and q > sqrt(n), then p*q>sqrt(n)*sqrt(n), which is the same as p*q>n, therefore p*q!=n. Therefore we proved not(B)->not(A), which is the same as A->B.

Problem 2: "There are 5 people in the room, what is the probability that atleast 2 of them have the same birthday?".

The statement is: "atleast 2 of them have the same birthday" is opposite of "none of them have the same birthday", and from probability theory: p=1-not(p). Apply direct reasoning to find probability that none of them have the same birthday: First guy has a birhday at a day D1 there are 365 days to chose from, second guy has birthday at a day D2, there are 364 days to choose from (he cant have birthday on day D1), etc.. The formula is: 365*364*363*362/(365*365*365*365) =0.98364408753. Therefore probability that atleast 2 of them have the same birthday is: 1-0.98364408753=0.01635591246.

Interpretation Manipulation

Without a doubt this is the most powerful method of solving any problem. It relies on finding a new problem which is equivalent to the initial one, you can draw the solution of initial problem from the solution of the equivalent problem.

Problem: "An infinite amount of mathematicians walk into a bar, first one buys 1 litre of beer, the second one buys 1/3 of what first one has bought, the third one buys 1/3 of what the second one has bought and so on. How many litres of beer did they buy?"

Transfer the problem to the realm of numbers and then manipulate formulas: total_beer=1+1/3+1/(3*3)+1/(3*3*3)... but at the same time total_beer/3=1/3+1/(3*3)+1/(3*3*3)+1/(3*3*3*3)... therefore total_beer-total_beer/3=1, solving for total_beer gives total_beer=3/2.

Problem 2: "You are given n girls and m boys, girls want to marry boys, given a list of boys every girl likes maximize number of girls to be married".

Transfer this problem into the realm of graphs: make girls and boys vertecies and add edge from every girl to all boys she likes. The resulting graph will be bipartite and the problem has a known algorithm: kuhn algorihm for maximal bipartite matching.

Problem 3:

undefined

In this example solving direct problem is unpleasant, however it's convex, you know that for convex problems solution to the Lagrangian lower bound solution is the same:

undefined

This problem yields solution to the original and has a nice algorithm to solve it: Sequential Minimal Optimization algorithm.

Problem 4: "Prove that there is no general finite formula using radicals to solve quintic polynomial"

The solution of this example is long, you saved this problem to notes only as the most notable example of how a problem which had absolutely no approach is solved by introducing an equivalent form: "The quintic equation is solvable if and only if the chain of commutator subgroups for it's Galois group is finite". Now the problem lies in the group theory. Galois group of a general quintic equation is S5, but the chain of its commutator subgroup gets stuck at A5. The problem is solved by solving an entirely different problem, one would even not notice any connection between the two.

Uniqueness and Existence of Math Objects

If and only if: Sometimes you are asked to prove something of the form "A if and only if B" or "A is equivalent to B." The usual way to do this is to prove two things: first, prove that "A implies B," and then prove that "B implies A." Use any of the possible techniques to prove these two implications.

Uniqueness: You are often asked to prove that some object satisfying a given property is unique. The trick is to assume that there is another object satisfying the property, and then show that it actually equals the original one.

Existence: This sort of proof often goes hand in hand with uniqueness. You are given some specified property, and then asked to show that an object exists which has that property. There are often two ways to do this. One can offer up a constructive proof, in which the object is explicitly constructed. A nonconstructive proof is the exact opposite - it shows that the object exists, but it gives no indication as to what the object looks like.