teacher
Sign in
Track

DSA & Competitive Programming

From your first loop to Codeforces Candidate Master.

57 lessons~36 hours of lessonsTarget: Candidate Master (Codeforces 1900+)C++ · Java
Reality check
  • Reading these lessons will not raise your rating. Solving problems will. The lessons only make that practice efficient.
  • Reaching Candidate Master usually takes one to three years of steady practice. Many people take longer, a few take less. There is no shortcut and no magic trick.
  • People who get there have typically solved several hundred to over a thousand problems, most of them a little above their current level (about +100 to +300 rating).
  • Rating only moves in contests. Give contests regularly and upsolve the problems you could not finish — that is where most growth happens.
  • Plateaus of weeks or months are normal. Keep the volume up, review mistakes, and the next jump comes.
  1. Stage 10/8

    Foundations

    Read a problem carefully, write correct code, and know whether it will run in time.

    Milestone: Solve most 800–1000 rated problems on your own.

    1. 01Start HereHow this track is organised, how Codeforces works, and the practice loop that actually raises your rating.800–100015 min
    2. 02How to Think About a ProblemA repeatable routine for reading a statement, finding a brute force, spotting the pattern and checking your answer before you submit.800–100020 min
    3. 03Language Setup and Contest TemplateA C++ and Java template with fast input, multiple test cases, 64-bit integers and modular arithmetic, plus the errors that cost beginners the most submissions.800–100025 min
    4. 04Complexity and ConstraintsEstimate whether a solution will run in time from the input size, using Big-O and the rule of thumb of about 10^8 operations per second.800–120025 min
    5. 05Math Basics for ContestsParity, divisibility, remainders with negatives, gcd and lcm with Euclid, ceiling division, sums of series and digit tricks.800–120025 min
    6. 06Implementation and SimulationTurn a statement into correct code step by step, with off-by-one control, string handling and a checklist for easy problems.800–100025 min
    7. 07Sorting and Binary Search BasicsSort arrays and pairs with correct comparators, then use lower_bound and upper_bound to search sorted data in logarithmic time.800–120030 min
    8. 08STL and Java CollectionsThe standard containers in C++ (STL) and Java side by side, what each operation costs, and the pitfalls that cause wrong answers and timeouts.800–120030 min
  2. Stage 20/8

    Arrays and searching

    Prefix sums, hashing, two pointers, windows, binary search and stacks — the tools behind almost every easy problem.

    Milestone: Pupil (1200) — Div. 2 A, and most B problems.

    1. 01Arrays and StringsThe loops, counters and in-place tricks that almost every easy and medium problem is built from.800–120035 min
    2. 02Prefix SumsPrecompute running totals once so any range sum, range XOR or range update is answered in constant time.1100–170035 min
    3. 03Hashing and Frequency CountingUse hash maps and sets to answer "have I seen this?" and "how many times?" in constant time, and turn pair-counting into a single pass.800–150035 min
    4. 04Two PointersWalk two indices through an array to replace a nested loop with a single pass.800–140030 min
    5. 05Sliding WindowKeep a moving range of the array and update its total as it grows and shrinks, instead of recomputing it each time.1000–150035 min
    6. 06Binary SearchHalve the search range each step using an invariant, so a lookup in a million sorted items takes about twenty comparisons.1000–140035 min
    7. 07Binary Search on the AnswerWhen you can quickly test whether a candidate answer works, and bigger candidates never hurt, binary search the answer itself.1100–170040 min
    8. 08Stacks, Queues and Monotonic StructuresUse a stack for matching and "nearest greater" questions and a deque for sliding-window maximum, each in a single linear pass.1000–160040 min
  3. Stage 30/3

    Recursion and bits

    Break a problem into smaller copies of itself, search by trying choices, and use bits as sets.

    Milestone: Recursive search and the common bit tricks feel routine.

    1. 01RecursionSolve a problem by calling the same function on smaller inputs, and learn to see the call stack, the recursion tree and the cost of repeated work.1000–150035 min
    2. 02BacktrackingBuild a solution one choice at a time, undo each choice after exploring it, and cut off branches that cannot succeed.1100–150040 min
    3. 03Bit ManipulationTreat integers as rows of on/off flags, learn the handful of bit tricks that matter, and use masks to enumerate subsets.800–150040 min
  4. Stage 40/3

    Greedy and construction

    Build an answer directly, justify a locally best choice, and sweep intervals from left to right.

    Milestone: Constructive and greedy Div. 2 B problems.

    1. 01Constructive AlgorithmsBuild an object that meets given conditions by solving small cases, spotting the pattern, and using parity and invariants to know when it is impossible.800–140040 min
    2. 02Greedy AlgorithmsMake the locally best choice at every step, and learn how to check that this really gives the best overall answer.1000–150040 min
    3. 03Sweep Line and IntervalsTurn intervals into start and end events, sort them, and sweep left to right to count overlaps, merge ranges and handle huge coordinates.1000–170040 min
  5. Stage 50/3

    Counting and number theory

    Primes, remainders and counting — the math that shows up once implementation is solid.

    Milestone: Specialist math, roughly 1400–1600.

    1. 01Number Theory BasicsPrimes, divisors and gcd, covering the sieve, factorising with a smallest-prime table, divisors in square-root time and the gcd properties contests lean on.900–160040 min
    2. 02Modular ArithmeticWork with remainders so huge answers fit in 64 bits, with fast exponentiation, modular inverses and nCr modulo a prime.900–160040 min
    3. 03CombinatoricsCounting without listing, using the sum and product rules, nCr, Pascal's triangle, stars and bars, inclusion-exclusion and the pigeonhole principle.1000–160040 min
  6. Stage 60/7

    Trees and graphs

    Heaps, trees, BFS and DFS, then shortest paths, disjoint sets and spanning trees.

    Milestone: Specialist (1400–1600) — graph B and C problems.

    1. 01Heaps and Priority QueuesKeep a changing collection ready to hand you its smallest or largest item in O(log n), and use that for top-k and merging problems.1100–160040 min
    2. 02Trees BasicsStore a tree as adjacency lists, walk it with DFS and BFS, and compute parent, depth, subtree size and diameter in one linear pass.1100–150040 min
    3. 03Graphs, BFS and DFSStore a graph as adjacency lists, find shortest paths on unweighted graphs and grids with BFS, and count components, detect cycles and 2-colour with DFS.1200–170050 min
    4. 04Topological SortOrder the nodes of a directed graph so every edge points forward, detect cycles with Kahn's algorithm or DFS, and run DP over the order.1500–200040 min
    5. 05Shortest PathsDijkstra with lazy deletion for non-negative weights, 0-1 BFS for weights 0 and 1, Bellman-Ford for negative edges and Floyd-Warshall for all pairs on small graphs.1500–200055 min
    6. 06Disjoint Set UnionTrack which items belong to the same group while groups merge, using union by size and path compression for near-constant time per operation.1300–190040 min
    7. 07Minimum Spanning TreeConnect all nodes at the lowest total edge weight with Kruskal (sort edges, join with DSU) or Prim (grow one tree with a heap), and know why greedy works.1600–200040 min
  7. Stage 70/8

    Dynamic programming

    Name a state and a transition, then move from one-dimensional DP through knapsack to trees, masks and digits.

    Milestone: Expert (1600+) — standard DP no longer scares you.

    1. 01Dynamic Programming BasicsSpot repeated subproblems, then reuse each answer with memoization or a table. Learn to name the state, transition, base case and answer.1000–150040 min
    2. 021D DP PatternsThe four one-dimensional DP shapes you meet most - take or skip, minimum coins, counting ways, and jumps - each with state, transition, base case and answer.1200–170040 min
    3. 03DP on Grids and StringsFill a two-dimensional table where each cell depends on its neighbours - counting grid paths, longest common subsequence and edit distance.1300–180045 min
    4. 04Knapsack DPChoose items under a weight limit to maximise value - 0/1 and unbounded versions, subset sum, and the one-array trick where loop direction is the whole difference.1500–200045 min
    5. 05Longest Increasing SubsequenceThe O(n^2) DP, the O(n log n) tails array with binary search, how to reconstruct the answer, and how LIS hides inside other problems.1500–200040 min
    6. 06Tree DP and RerootingRoot the tree, compute each vertex from its children, then reuse those answers to get the result for every possible root in linear time.1300–210045 min
    7. 07Bitmask DPUse an integer's bits as a set of chosen items, so you can run DP over subsets when n is at most about 20 - assignment problems and the travelling salesman.1800–220045 min
    8. 08Digit DPCount numbers up to N that satisfy a digit property by building them one digit at a time, with a tight flag that tracks whether the prefix still matches N.1900–240040 min
  8. Stage 80/5

    Range queries

    Answer questions about a segment of an array, from a static table to trees that handle updates.

    Milestone: Range-query problems in the 1700–2000 band.

    1. 01Sparse TablePrecompute answers for every power-of-two length so that range min, max or gcd on a fixed array takes O(1) per query.1700–220030 min
    2. 02Fenwick TreeA short, fast structure for prefix sums with updates, built on the lowest set bit of an index, also used for counting and range add.1800–230040 min
    3. 03Segment TreeAnswer range queries and point updates in O(log n) by storing the answer for every halved segment of the array.1600–230045 min
    4. 04Lazy PropagationAdd to or assign a whole range in O(log n) by leaving a pending note on a segment tree node and pushing it down only when needed.1800–240045 min
    5. 05Sqrt Decomposition and Mo's AlgorithmSplit the array into blocks of about sqrt(n) to balance update and query costs, and reorder offline range queries so two moving pointers do little work in total.1800–240045 min
  9. Stage 90/3

    Advanced trees

    Jump around a rooted tree, flatten subtrees into array ranges, and merge the smaller set into the larger.

    Milestone: Tree problems that need more than one DFS.

    1. 01LCA and Binary LiftingFind the lowest common ancestor, distances and k-th ancestors in a rooted tree by jumping 2^k steps at a time.1800–220040 min
    2. 02Euler Tour on TreesFlatten a tree with tin and tout times so every subtree becomes one array range, then use a Fenwick or segment tree on it.1900–230040 min
    3. 03Small-to-Large Merging and DSU on TreeMerge the smaller set into the larger so each element moves O(log n) times, and reuse that idea as DSU on tree to answer subtree queries.1800–240045 min
  10. Stage 100/3

    Strings

    Compare substrings in constant time, find a pattern in linear time, and store prefixes in a trie.

    Milestone: Standard string problems up to about 2000.

    1. 01String HashingTurn substrings into numbers with a polynomial hash so any two substrings compare in O(1), and know exactly when it can fail.1700–220040 min
    2. 02KMP and Z-functionFind a pattern in a text in linear time with the prefix function, and read borders and periods straight from the prefix and Z arrays.1700–230045 min
    3. 03Trie (Prefix Tree)Store strings or binary numbers on the edges of a tree so prefix questions and maximum-XOR questions take time proportional to the length, not the count.1700–220040 min
  11. Stage 110/4

    Advanced topics

    Four separate ideas, in rising difficulty — games, expected value, matrix powers, and strong connectivity.

    Milestone: Candidate Master ideas for Div. 2 D and E.

    1. 01Game Theory, Nim and Grundy NumbersDecide who wins a two-player game with perfect play, using win/lose states, the XOR rule of Nim, and Grundy numbers for sums of games.1400–220045 min
    2. 02Probability and Expected ValueCompute averages over random processes with linearity of expectation, indicator variables and expected-value DP, and print fractions modulo a prime.1500–220045 min
    3. 03Matrix ExponentiationTurn a linear recurrence or a walk-counting question into one matrix, then raise it to a huge power in O(d^3 log n) with repeated squaring.1500–230040 min
    4. 04SCCs, Bridges and Articulation PointsOne DFS with low-link values finds strongly connected components in a directed graph, and bridges and cut vertices in an undirected one.1700–230050 min
  12. Stage 120/2

    Contest craft

    Talk to an interactive judge, then practise, compete and get through the plateaus on the way up.

    Milestone: Candidate Master (1900+) — a repeatable contest habit.

    1. 01Interactive ProblemsTalk to a judge program through standard input and output, flush after every query, stay under the query limit, and find hidden values with binary search.1400–190035 min
    2. 02Contest Strategy and the Road to Candidate MasterAn honest plan for reaching Codeforces 1900 - practice a little above your level, give contests, upsolve, manage time, stress test, and survive plateaus.35 min