Problems Base course RU

Found in

maps and navigation

Articles

DS Data structure Disjoint set union Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks. O(α(n)) 2 problems GRA Technique Storing a graph Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply.

neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists

2 problems GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((V + E) log V) 2 problems GRA Algorithm Johnson's algorithm Shortest paths with negative weights: Bellman–Ford potentials, reweighting and Dijkstra from each vertex. O(V·E + V·(V + E) log V) 2 problems GRA Algorithm Contraction hierarchies A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up. O((V + E′) log V) 1 problem GRA Algorithm Graph colouring Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables. O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap 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 GRA Algorithm Eulerian path Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E). O(V + E) 3 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 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 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 GEO Technique Vectors and orientation The sign of the cross product is a left or right turn; almost all of computational geometry stands on it. O(1) per turn 2 problems GEO Algorithm Delaunay triangulation and Voronoi diagram Zones of the nearest point and triangles with empty circles: two sides of one structure. O(n log n) on average 2 problems

Problems

Is there such a street piece A stop on the way An honest hint Bike stations Do the segments cross Night closures Routes with no step back The courier's route A crossing under repair A navigator without trigonometry An electric car in the hills Couriers and orders Fewest turns Fire stations Frequencies for the towers Queries over the tiers Street closures The shortest loop Where to put a new station Nobody rides far The snowplough

Often together

classic 14 graph 9 interviews 7 weighted graph 6 contests 5 shortest path 5 heap 4 heuristic 4 matrix 3 optimization 3 logistics 3 dynamic programming 3