Solves
counting
Articles
DP
Technique
Dynamic programming
Reduce a problem to subproblems, solve each once and keep the answers in a table.
states × transitions
2 problems
DP
Technique
Bitmask DP
The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile.
O(2ⁿ · n²) for the travelling salesman
2 problems
DP
Technique
Digit DP
Lucky tickets in any range in one pass over the digits: 55,252 out of a million, and any range up to 10¹⁸, in about a millisecond.
O(D · 10 · S)
2 problems
NUM
Algorithm
Chinese remainder theorem
A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes.
O(k²) operations on machine numbers
2 problems
Problems
Two books for a gift card
Frequent words in one pass
How many schemata survive
How many triangles
Pairs closer than r
Routes with no step back
A crossing under repair
A gift with a purchase
A lift without fours
All the spanning trees
Counting in the transform
Exact change
How many times the line runs
Lucky in a range
The forgotten code
Triangles of imports
Where the k-th can lie
How many times each word
Often together
dynamic programming 3 maps and navigation 3 classic 3 contests 3 optimization 2 number theory 2 memoization 1 DAG 1 recursion 1 interviews 1 bit tricks 1 logistics 1