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
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.
The two pointers technique (SR)
A pair with a given sum, a sliding window, two arrays.
Open lesson →Prefix sums (SR)
The sum of a part of an array in O(1), a difference array, prefix sums in a matrix.
Open lesson →Monotonic stack and queue (SR)
The next greater element, a histogram, the minimum of a window.
Open lesson →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.
Divide and conquer (SR)
Fast exponentiation, the maximum subarray sum, the complexity of recursion.
Open lesson →Greedy algorithms
Making change, activity selection, when greedy works and when it does not.
Open lesson →Binary search on the answer (SR)
Optimization by checking an answer.
Open lesson →4 What next
Topics that build on these techniques.
Suggested order
Useful external resources
- CSES Problem Set – the "Sorting and Searching" section
- USACO Guide – Prefix Sums – prefix sums with tasks
- cp-algorithms – an encyclopedia of techniques
