Library

A reference on the basics of C++ that solutions in competitive programming rely on.

These concepts and techniques are the building blocks of most solutions, whatever the problem is about and whatever language it is written in.

A data structure keeps values in a form suited to a particular use: usually so that some operations are fast, sometimes so that the values take little memory. The right choice often decides whether a solution fits the limits.

A graph is a set of vertices joined by edges. Roads between cities form one, and so do the moves in a game or the order in which tasks depend on each other. Many problems become standard once you see the graph in them.

Dynamic programming solves a problem by splitting it into smaller problems of the same kind, solving each of them once and storing the answers in a table. It applies when the same smaller problems come up again and again, which is what makes a plain recursive solution slow.

Number theory studies whole numbers: which numbers divide which, and what remains after a division. In competitive programming it comes up in problems about fractions and periods, and whenever the answer is asked modulo a large prime.

String problems ask where a word occurs in a text, whether two parts of it are equal, or which part repeats. Comparing character by character is often too slow, and string algorithms answer such questions in about the time it takes to read the text once.