Problems Base course RU

Solves

optimization

Articles

SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems GRA Algorithm Hungarian algorithm Which job for whom at the least total cost: potentials, tight pairs and augmenting paths in O(n³). O(n³) 2 problems 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 Interval DP The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing. O(n³) 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 Convex hull trick A minimum of lines instead of a search: 1776 catalogue tests split into sandbox runs, and a quadratic DP becomes linear. O(n) 2 problems DP Technique Knuth and divide-and-conquer optimisations 45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone. O(k · n log n) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems PAR Technique Branch and bound 38 airports with a direct flight from each to each: a colouring bound shrinks the search from a million nodes to 242. exponential in the worst case 1 problem NUM~ Algorithm Gradient descent Finds the minimum of a function by steps against the gradient, in the direction of steepest descent. O(κ · log(1/ε)) steps 2 problems RND Algorithm Genetic algorithm A population of solutions, selection, crossover and mutation: the evolution of a racing line on a real circuit. O(G · N · c) 2 problems

Problems

Sawing a log The longest safe step A pick-up point Brackets on a calculator Couriers and orders Lights out Two coins Who takes which order Batches of tests Merge neighbours Nobody rides far Reading evenings The cheapest plan The goods lift

Often together

classic 9 contests 7 dynamic programming 5 interviews 4 maps and navigation 3 geodata 3 greedy 2 matrix 2 logistics 2 counting 2 scheduling 2 approximation 2