Guide · Algorithms · Advanced techniques

Advanced Techniques – Learning Guide

Advanced techniques are general ways of thinking that turn a slow solution (two or three nested loops, checking all possibilities) into a fast one. Each of them appears in dozens of competition tasks.

For these lessons you need to know arrays, sorting, binary search, the stack and the queue.

  • Grades 7–8 and secondary school
  • C++
  • Competition preparation
How to recognize the technique: "the sum of a part of an array" → prefix sums; "a consecutive part with a condition" or "a pair in a sorted array" → two pointers; "the first larger/smaller to the left or right", "the minimum of every window" → a monotonic stack/queue; "the most at the same time" → the sweep line method; n ≤ 20 and "choose a subset" → masks; "the smallest/largest X such that…" → binary search on the answer; "take the best you can now" → a greedy algorithm (after checking that it is correct).

Some lessons linked below are available only in Serbian for now. They are marked (SR).

1 One pass through an array

Techniques that replace two loops with one.

2 Intervals and subsets

Working with times, intervals and all possible choices.

3 General approaches

How a solution is built from smaller parts or by a greedy choice.

4 What next

Topics that build on these techniques.

Suggested order

  1. The two pointers technique (SR)
  2. Prefix sums (SR)
  3. Monotonic stack and queue (SR)
  4. The sweep line method (SR)
  5. Bitwise operations and masks (SR)
  6. Divide and conquer (SR)
  7. Greedy algorithms

Useful external resources