olimp-coding

C++ solutions to an olympiad-style programming problem set, March 2019: 33 single-file programs in 8 topic folders, from quadratic sorts to Dijkstra and Bellman-Ford. Every program reads its input from stdin and writes the answer to stdout, in contest style (global arrays sized to the problem limits, no input validation).

What it covers

Folder	Topic
1-sqr-sort	insertion sort printing every pass (a), bubble sort with a custom ordering (d) and with forbidden swaps (f), greedy answers on sorted data (b, c), producing an array with exactly k inversions (e)
2-quick-sort	randomized three-way partition quicksort (a), the same sort applied to parallel arrays (b) and pairs (c), greedy on std::sorted data (d), quickselect for the k-th order statistic (e)
3-bin-search	binary search on sorted arrays: membership (a), first/last occurrence to count duplicates (b); real-valued bisection for n-th roots and monotone equations (c, d) and for a geometric optimum (e)
4-bin-search	binary search on the answer with a feasibility check: minimum time to inflate m balloons (a), maximum minimum gap for k cows in stalls (b), cutting ropes into k equal pieces (c); d is an empty stub
5-graphs	DFS on adjacency lists: connected components (a, c), tree check via white/gray/black colouring and cycle detection (b), flood fill on a character grid (d)
6-topologic-sort	DFS-based topological order over a dependency graph with per-task durations
7-wide-search	BFS: shortest path length (a), path reconstruction (b), knight moves on an n x n board (c); two-pass DFS over a height map to count basins (d)
8-dijkstra-ford-bellman	Dijkstra in O(V^2) on an adjacency matrix (a), graph centre via Dijkstra from every vertex (b), Bellman-Ford with negative-cycle extraction (c), Bellman-Ford on a maze with "slide" edges (d)

Notable exercises

• 2-quick-sort/a.cpp: quicksort with a random pivot and a three-way (less / equal / greater) partition, so arrays with many duplicates do not degrade. 2-quick-sort/e.cpp reuses the same partition as quickselect on 10^7 elements generated by a cubic formula, allocated on the heap.
• 4-bin-search/b.cpp: binary search on the answer with a greedy countCows feasibility check (the classic "aggressive cows" problem).
• 5-graphs/b.cpp: three-colour DFS with parent tracking that reports whether an adjacency matrix describes a tree (no cycle, all vertices reached).
• 7-wide-search/d.cpp: first DFS pass records finishing order along "downhill" edges, second pass walks "uphill" from that order to count components - a two-pass approach in the spirit of Kosaraju.
• 8-dijkstra-ford-bellman/c.cpp: Bellman-Ford with n-1 relaxation rounds, one extra round to detect a negative cycle, and parent pointers to print the cycle's vertices.
• 8-dijkstra-ford-bellman/d.cpp: builds a weighted graph from an ASCII maze by DFS - unit edges to the four neighbours plus "slide until a wall" edges - then runs Bellman-Ford to the target cell.

Running

There are no build files; each .cpp is a standalone program. Range-based for and brace initialisation require C++11, for example:

g++ -std=c++11 -o a 8-dijkstra-ford-bellman/a.cpp
./a < input.txt

Notes

• Solutions use int/short arrays sized to the stated limits (up to 100 000 elements) rather than std::vector, as is common in contest code; <vector> and <queue> appear from the graph section on.
• 4-bin-search/c.cpp and 4-bin-search/d.cpp are unfinished.
• Comments are sparse and, where present, in Russian. 33 files, about 1 800 lines; early learning code kept as a record.