CodeISM CP/DSA Textbook Notes
Expanded topic-wise textbook-style notes based on the uploaded class materials
Generated on 15 May 2026
This version is intentionally detailed. It is written like a study textbook: every chapter contains theory, intuition,
templates, examples, common mistakes, and revision checkpoints.
Note: This is a cleaned and expanded learning version based on the provided class PDFs. It is not a word-for-word copy of
the source files.
Index
Chapter 1: Foundations of Competitive Programming 7
Why constraints matter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
Typical complexity guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Fast I/O and template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Debugging mindset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter 2: Arrays, Vectors and Basic Storage 8
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Example: prefix sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Common mistakes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Chapter 3: STL Containers 9
Vector, pair and sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Set and multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Map and unordered_map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Example: frequency map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9
Chapter 4: Stack, Queue and Deque 10
Stack intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Balanced brackets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Balanced bracket code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Monotonic stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Next greater element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Queue and BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Chapter 5: Binary Search 11
Core idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Basic search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Lower bound intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Binary search on answer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Answer template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Example idea: minimum maximum pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Chapter 6: Ternary Search 12
Unimodal functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Integer ternary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Floating point ternary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Chapter 7: Two Pointers and Sliding Window 13
Two pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Merging sorted arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Pair sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Sliding window . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Variable window template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Chapter 8: Bit Manipulation 14
Binary representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Basic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Bitmask subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Subset iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Chapter 9: Number Theory 15
GCD and Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
GCD code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
LCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Modulo arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Binary exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Sieve code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Fermat and modular inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Euler totient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapter 10: Dynamic Programming 16
What is DP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
How to design DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Memoization vs tabulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Fibonacci example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Coin combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Coin combinations I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Coin combinations II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Bitmask DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Assignment DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Digit DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Game DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Chapter 11: Graph Theory Basics 18
Graph representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
DFS code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Tree DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
BFS code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Chapter 12: Advanced Graphs 19
Directed cycle detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Cycle code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Bipartite graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Topological sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
0-1 BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
0-1 BFS code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Chapter 13: DSU, MST, SCC and Diameter 20
DSU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
DSU code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
MST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
SCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Kosaraju . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Tree diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Chapter 14: String Algorithms 21
Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Trie node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Trie operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Prefix function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Pattern search idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Chapter 15: Range Queries 22
Static vs dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Sparse table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Sparse table min query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Segment tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Build segment tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Query segment tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Point update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Chapter 16: Practice and Revision Plan 23
How to study each chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Practice ladder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Common mixed patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Final checklist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Chapter 1: Foundations of Competitive Programming
Why constraints matter
In competitive programming, constraints decide the algorithm. If n is 10^5, an O(n^2) approach is usually too slow.
If n is 20, a 2^n bitmask DP may be possible. If values go up to 10^9, you often need logarithmic algorithms or
mathematical observations.
Typical complexity guide
n <= 20 -> O(2^n), bitmask DP, backtracking
n <= 500 -> O(n^3) may pass
n <= 5000 -> O(n^2) may pass
n <= 1e5 -> O(n log n) or O(n)
n <= 1e9 -> O(log n), math, binary search
multiple tests -> multiply complexity by total input size
Fast I/O and template
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve() {
// write solution here
}
int32_t main() {
ios::sync_with_stdio(false);
[Link](nullptr);
int t = 1;
cin >> t;
while(t--) solve();
}
Debugging mindset
Most wrong answers come from boundary cases, overflow, wrong indexing, or misunderstanding whether order
matters. Always test n=1, all equal elements, sorted/reverse sorted input, maximum values, and disconnected
graph cases.
Chapter 2: Arrays, Vectors and Basic Storage
Arrays
An array stores elements of the same type in contiguous memory. Access by index is O(1). Arrays are useful when
size is fixed or when global memory is required.
Vector
A vector is a dynamic array. It grows automatically when elements are pushed. In CP, vector is usually preferred
over raw arrays unless you need very large global memory.
Example: prefix sum
vector<int> a(n + 1), pref(n + 1, 0);
for(int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
// sum from l to r
int rangeSum = pref[r] - pref[l - 1];
Common mistakes
If you use 1-based indexing, allocate n+1 size. If you use 0-based indexing, range [l,r] formulas change. Be
consistent throughout the problem.
Chapter 3: STL Containers
Vector, pair and sorting
Vector stores dynamic sequences. Pair stores two related values. Sorting vectors and vector of pairs is common in
greedy and interval problems.
Set and multiset
Set stores unique sorted elements. Multiset stores sorted elements with duplicates. Both support lower_bound and
upper_bound in O(log n).
Map and unordered_map
Map stores sorted key-value pairs in O(log n). Unordered_map gives average O(1), but can degrade in worst case.
Use map when order is needed.
Priority queue
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
[Link](x);
int best = [Link]();
[Link]();
Example: frequency map
map<int,int> freq;
for(int x : a) freq[x]++;
for(auto [value, count] : freq) {
cout << value << " appears " << count << " times\n";
}
Chapter 4: Stack, Queue and Deque
Stack intuition
A stack is like a pile of plates. The last plate placed is the first one removed. This LIFO property makes it useful for
matching, undo operations, recursion simulation, and monotonic problems.
Balanced brackets
For every closing bracket, the most recent unmatched opening bracket must match it. This is exactly stack
behavior.
Balanced bracket code
bool isBalanced(string s) {
stack<char> st;
for(char c : s) {
if(c=='(' || c=='{' || c=='[') [Link](c);
else {
if([Link]()) return false;
char t = [Link](); [Link]();
if(c==')' && t!='(') return false;
if(c=='}' && t!='{') return false;
if(c==']' && t!='[') return false;
}
}
return [Link]();
}
Monotonic stack
A monotonic stack keeps elements in increasing or decreasing order. When a new element breaks the order, we
pop until order is restored. Each element is pushed and popped at most once, so total time is O(n).
Next greater element
vector<int> nextGreater(vector<int>& a) {
int n = [Link]();
vector<int> ans(n, -1);
stack<int> st; // stores values or indices
for(int i = n - 1; i >= 0; i--) {
while(![Link]() && [Link]() <= a[i]) [Link]();
if(![Link]()) ans[i] = [Link]();
[Link](a[i]);
}
return ans;
}
Queue and BFS
A queue is FIFO. It is the natural structure for BFS because nodes are processed level by level.
Deque
Deque supports insertion/removal from both ends. It is used in 0-1 BFS and sliding window maximum/minimum.
Chapter 5: Binary Search
Core idea
Binary search repeatedly halves the search space. It works not only on sorted arrays but also on any monotonic
yes/no condition.
Basic search
int binarySearch(vector<int>& a, int target) {
int l = 0, r = (int)[Link]() - 1;
while(l <= r) {
int mid = l + (r - l) / 2;
if(a[mid] == target) return mid;
if(a[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}
Lower bound intuition
Lower bound means first position where value is at least x. It is the first true in the condition a[i] >= x.
Binary search on answer
Many optimization problems ask for minimum possible maximum or maximum possible minimum. If you can write a
check(mid) function that says whether mid is possible, binary search can find the answer.
Answer template
bool check(long long mid) {
// true if mid is feasible
}
long long l = 0, r = 1e18, ans = -1;
while(l <= r) {
long long mid = l + (r - l) / 2;
if(check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
Example idea: minimum maximum pages
If students can be assigned books such that no student reads more than X pages, then any larger X is also
possible. This monotonicity allows binary search.
Chapter 6: Ternary Search
Unimodal functions
Ternary search is used when the function has a single peak or single valley. Unlike binary search, which needs
monotonicity, ternary search needs unimodality.
Integer ternary search
int ternaryMax(int l, int r) {
while(r - l >= 3) {
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
if(f(m1) < f(m2)) l = m1;
else r = m2;
}
int ans = f(l);
for(int i = l; i <= r; i++) ans = max(ans, f(i));
return ans;
}
Floating point ternary search
For real-valued domains, run fixed iterations or stop when r-l is less than epsilon.
Chapter 7: Two Pointers and Sliding Window
Two pointers
Two pointers are used when two indices move monotonically. Since each pointer moves at most n times, the
complexity is usually O(n).
Merging sorted arrays
vector<int> mergeSorted(vector<int> a, vector<int> b) {
int i = 0, j = 0;
vector<int> res;
while(i < [Link]() && j < [Link]()) {
if(a[i] <= b[j]) res.push_back(a[i++]);
else res.push_back(b[j++]);
}
while(i < [Link]()) res.push_back(a[i++]);
while(j < [Link]()) res.push_back(b[j++]);
return res;
}
Pair sum
In a sorted array, if a[l]+a[r] is too small, increase l. If it is too large, decrease r. This works because the array is
sorted.
Sliding window
Sliding window is a two-pointer technique for subarrays/substrings. Expand right pointer, and while invalid, move
left pointer.
Variable window template
int l = 0, ans = 0;
for(int r = 0; r < n; r++) {
// add a[r]
while(window_is_invalid) {
// remove a[l]
l++;
}
ans = max(ans, r - l + 1);
}
Chapter 8: Bit Manipulation
Binary representation
Every integer is stored in binary. Bit operations are fast and allow compact representation of subsets and states.
Basic operations
// check ith bit
bool on = (n & (1LL << i));
// set ith bit
n |= (1LL << i);
// clear ith bit
n &= ~(1LL << i);
// toggle ith bit
n ^= (1LL << i);
// count set bits
int cnt = __builtin_popcountll(n);
Bitmask subsets
A mask from 0 to 2^n - 1 represents a subset of n elements. If bit i is set, element i is included.
Subset iteration
for(int mask = 0; mask < (1 << n); mask++) {
for(int i = 0; i < n; i++) {
if(mask & (1 << i)) {
// element i is in subset
}
}
}
Chapter 9: Number Theory
GCD and Euclid
The Euclidean algorithm is based on gcd(a,b)=gcd(b,a%b). It runs in logarithmic time.
GCD code
long long gcd(long long a, long long b) {
if(b == 0) return a;
return gcd(b, a % b);
}
LCM
Use lcm(a,b)=a/gcd(a,b)*b. Divide before multiplying to reduce overflow risk.
Modulo arithmetic
Modulo keeps values small. For subtraction, add mod before taking modulo to avoid negative values in C++.
Binary exponentiation
long long binpow(long long a, long long b, long long mod) {
long long ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
Sieve
Sieve of Eratosthenes marks multiples of primes as composite. It precomputes primality up to n efficiently.
Sieve code
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for(long long i = 2; i * i <= n; i++) {
if(prime[i]) {
for(long long j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
Fermat and modular inverse
If mod is prime and a is not divisible by mod, then inverse of a modulo mod is a^(mod-2) modulo mod.
Euler totient
phi(n) counts integers from 1 to n that are coprime with n. If prime factorization is known, phi(n)=n product over
primes p dividing n of (1-1/p).
Chapter 10: Dynamic Programming
What is DP?
Dynamic programming solves problems by storing answers to overlapping subproblems. It is useful when brute
force recomputes the same states repeatedly.
How to design DP
Define state, base case, transition, answer, and complexity. Most DP mistakes happen because the state is
incomplete.
Memoization vs tabulation
Memoization is recursive top-down DP. Tabulation is iterative bottom-up DP. Both compute the same states but in
different order.
Fibonacci example
vector<int> dp(n + 1, -1);
int fib(int n) {
if(n == 1) return 0;
if(n == 2) return 1;
if(dp[n] != -1) return dp[n];
return dp[n] = fib(n - 1) + fib(n - 2);
}
Coin combinations
If order matters, loop over sum first then coins. If order does not matter, loop over coins first then sum.
Coin combinations I
dp[0] = 1;
for(int sum = 0; sum <= x; sum++) {
for(int coin : coins) {
if(sum >= coin) {
dp[sum] = (dp[sum] + dp[sum - coin]) % MOD;
}
}
}
Coin combinations II
dp[0] = 1;
for(int coin : coins) {
for(int sum = coin; sum <= x; sum++) {
dp[sum] = (dp[sum] + dp[sum - coin]) % MOD;
}
}
Knapsack
Knapsack problems usually ask whether to take or skip an item. State may be index and remaining capacity.
Bitmask DP
Use mask to represent which items are already used. This is common in assignment, matching, travelling salesman
style problems.
Assignment DP
long long rec(int i, int mask) {
if(i == n) return 1;
if(dp[i][mask] != -1) return dp[i][mask];
long long ans = 0;
for(int j = 0; j < n; j++) {
if(!(mask & (1 << j)) && can[i][j]) {
ans = (ans + rec(i + 1, mask | (1 << j))) % MOD;
}
}
return dp[i][mask] = ans;
}
Digit DP
Digit DP counts numbers in a range. State usually includes position, tight flag, started flag, and extra information
like sum/mod/previous digit.
Game DP
Game DP handles two-player optimal games. The transition assumes both players play optimally.
Chapter 11: Graph Theory Basics
Graph representation
Adjacency list is usually preferred for sparse graphs. Adjacency matrix is useful when edge lookup must be O(1)
and n is small.
DFS
DFS explores deeply before backtracking. It is used for connected components, tree DP, cycle detection, subtree
calculations, and topological sort.
DFS code
void dfs(int node) {
vis[node] = 1;
for(int child : adj[node]) {
if(!vis[child]) dfs(child);
}
}
Tree DFS
void dfs(int node, int parent) {
for(int child : adj[node]) {
if(child == parent) continue;
dfs(child, node);
}
}
BFS
BFS explores level by level and gives shortest path in unweighted graphs.
BFS code
queue<int> q;
vector<int> dist(n + 1, -1);
dist[src] = 0;
[Link](src);
while(![Link]()) {
int node = [Link]();
[Link]();
for(int child : adj[node]) {
if(dist[child] == -1) {
dist[child] = dist[node] + 1;
[Link](child);
}
}
}
Chapter 12: Advanced Graphs
Directed cycle detection
Use three colors: unvisited, currently in recursion stack, and completed. Reaching an ongoing node means cycle.
Cycle code
bool dfs(int node) {
color[node] = 1;
for(int child : adj[node]) {
if(color[child] == 1) return true;
if(color[child] == 0 && dfs(child)) return true;
}
color[node] = 2;
return false;
}
Bipartite graph
A graph is bipartite if it can be colored with two colors such that adjacent nodes have different colors. Odd cycle
means not bipartite.
Topological sort
Topological ordering exists only in DAGs. It is used for dependencies and DP on DAG.
0-1 BFS
When edge weights are only 0 or 1, deque-based BFS gives shortest paths faster than Dijkstra.
0-1 BFS code
deque<int> dq;
dist[src] = 0;
dq.push_front(src);
while(![Link]()) {
int node = [Link]();
dq.pop_front();
for(auto [child, wt] : adj[node]) {
if(dist[child] > dist[node] + wt) {
dist[child] = dist[node] + wt;
if(wt == 0) dq.push_front(child);
else dq.push_back(child);
}
}
}
Dijkstra
Use for non-negative weighted graphs. Priority queue always expands the currently closest node.
Bellman-Ford
Use when negative edges exist. It can detect negative cycles by checking for relaxation on the nth iteration.
Floyd-Warshall
All-pairs shortest path using DP over intermediate nodes. Complexity O(n^3).
Chapter 13: DSU, MST, SCC and Diameter
DSU
Disjoint Set Union maintains connected components under union operations. Path compression and union by size
make operations nearly O(1).
DSU code
vector<int> parent, sz;
int find(int x) {
if(parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
MST
Minimum Spanning Tree connects all nodes with minimum total edge weight. Kruskal sorts edges and uses DSU.
Prim grows the tree using a priority queue.
SCC
Strongly Connected Components are groups of nodes in a directed graph where every node can reach every other
node in the group.
Kosaraju
First DFS stores finish order. Reverse graph. Process nodes in reverse finish order. Each DFS in reversed graph
gives one SCC.
Tree diameter
Diameter is the longest path in a tree. Run BFS/DFS from any node to farthest A, then from A to farthest B.
Distance A-B is diameter.
Chapter 14: String Algorithms
Trie
Trie is a prefix tree. It stores strings character by character. It is useful for prefix count, dictionary search, contacts
problem, and binary XOR tries.
Trie node
struct TrieNode {
TrieNode* child[26];
int ending;
int holding;
TrieNode() {
for(int i = 0; i < 26; i++) child[i] = nullptr;
ending = 0;
holding = 0;
}
};
Trie operations
Insertion creates missing nodes. Prefix count walks down the prefix and returns how many words pass through that
node. Deletion decreases counters if word exists.
KMP
KMP matches a pattern in text in O(n+m). It uses the LPS/prefix function to avoid restarting from scratch after
mismatch.
Prefix function
vector<int> prefix_function(string s) {
int n = [Link]();
vector<int> pi(n);
for(int i = 1; i < n; i++) {
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
Pattern search idea
Build string pattern + '#' + text. Wherever prefix value equals pattern length, a match ends at that position.
Chapter 15: Range Queries
Static vs dynamic
If array does not change, prefix sums and sparse table are strong. If updates are required, segment tree or Fenwick
tree is needed.
Sparse table
Sparse table precomputes answers for intervals of length powers of two. For idempotent operations like min, max,
gcd, query is O(1).
Sparse table min query
int queryMin(int l, int r) {
int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
Segment tree
Segment tree supports range query and point update in O(log n). Each node stores answer for an interval.
Build segment tree
void build(int id, int L, int R) {
if(R - L == 1) {
seg[id] = arr[L];
return;
}
int mid = (L + R) / 2;
build(2*id, L, mid);
build(2*id+1, mid, R);
seg[id] = min(seg[2*id], seg[2*id+1]);
}
Query segment tree
int query(int x, int y, int id, int L, int R) {
if(L >= x && R <= y) return seg[id];
if(L >= y || R <= x) return INF;
int mid = (L + R) / 2;
return min(query(x, y, 2*id, L, mid),
query(x, y, 2*id+1, mid, R));
}
Point update
void update(int pos, int val, int id, int L, int R) {
if(R - L == 1) {
seg[id] = val;
return;
}
int mid = (L + R) / 2;
if(pos < mid) update(pos, val, 2*id, L, mid);
else update(pos, val, 2*id+1, mid, R);
seg[id] = min(seg[2*id], seg[2*id+1]);
}
Chapter 16: Practice and Revision Plan
How to study each chapter
Read the theory, write the template without looking, solve examples, then solve mixed problems so you learn when
to apply the idea.
Practice ladder
Level 1: Understand template and dry run
Level 2: Solve direct implementation problems
Level 3: Solve problems where topic is hidden
Level 4: Mix two topics, e.g. binary search + prefix sum
Level 5: Solve timed contests and upsolve
Common mixed patterns
Binary search + greedy, binary search + prefix sums, DP + bitmasking, graph + DP, tree + gcd, trie + bit
manipulation, segment tree + coordinate compression.
Final checklist
Before submitting, check overflow, indexing, modulo, empty containers, recursion depth, disconnected
components, and whether order matters.