Click any module to expand. This is NOT a repeat of DSA with harder problems — it covers entirely new algorithms, data structures, and optimisation techniques not found in the standard module. Each topic includes competitive programming applications and hard interview problem examples.
Optimisation patterns that turn TLE into AC — the techniques that separate rated coders from beginners
Split input in half, enumerate each half, combine. Converts O(2ⁿ) to O(2^(n/2)). Classic: subset sum with n≤40, closest pair sum to target. When brute force is too slow but DP doesn't apply — MITM fills the gap.
Divide array into √n blocks for O(√n) range queries and point updates. Simpler than segment tree for certain problems. Mo's algorithm for offline range queries in O((N+Q)√N). When sqrt decomposition beats log-based structures.
Offline processing of range queries by sorting them cleverly. Answer queries on [L,R] by maintaining a running answer and adding/removing elements. Applications: distinct elements in range, frequency of frequencies. The block-size trick for optimal complexity.
When values are large but count is small — map values to [0, n) for use with BIT/segment tree. Applied in: count inversions with large values, rectangle union area, sweep line problems. A preprocessing technique, not an algorithm itself.
When merging information from child subtrees, always merge the smaller set into the larger one — O(n log n) total. Applications: distinct colours in subtree, kth smallest in subtree. Also called "heavy-light" trick in simpler form.
Sometimes processing queries in a different order than given is dramatically faster. Offline sorting of queries by right endpoint. Online vs offline — recognising when offline is possible. Introduction to persistent data structures (conceptual).
Range queries and updates at O(log n) — the most powerful interview/contest data structure
Range update + range query in O(log n). Lazy tag propagation: deferring updates until needed. Building from basic segment tree. Applications: range add + range sum, range set + range min. The most frequently needed advanced data structure in contests.
Combining different lazy operations (add + set, multiply + add). Order of operations matters — composing lazy tags correctly. Range assignment with range sum query. When two operations interfere — resolving conflicts.
Each segment tree node stores a sorted list of elements in its range. Count of elements in [L,R] less than K in O(log²n). Kth smallest in range. Space O(n log n). When segment tree + binary search combines.
2D segment tree for matrix range queries. Persistent segment tree: preserving all historical versions after updates. Kth smallest in range [L,R] using persistent + coordinate compression. Functional updates — O(log n) per version.
Segment tree where leaves represent compressed coordinates, not array indices. Rectangle union area (sweep line + segment tree). Interval scheduling with segment tree. Dynamic coordinate insertion.
LCA, Euler tour, HLD, centroid decomposition — techniques for tree query problems
Precompute 2^k-th ancestors for every node. Answer LCA queries in O(log n). Sparse table approach. Distance between two nodes = depth[u] + depth[v] - 2*depth[LCA(u,v)]. The foundation for most tree query optimisations.
Convert a tree to an array using Euler tour (tin/tout timestamps). Subtree queries become range queries on the array — solvable with BIT/segment tree. Path queries via Euler tour + LCA. The bridge between tree and array problems.
Decompose tree into heavy and light chains. Path queries/updates in O(log²n) using segment tree on each chain. Sum/max/min on path from u to v. Update all nodes on a path. When you need segment tree operations ON tree paths.
Recursively find centroid, build centroid tree. Answer path-related queries efficiently. Count paths of length k, closest marked node, distance queries. O(n log n) preprocessing, O(log n) per query. Powerful technique for distance-based tree problems.
DP on tree with rerooting technique (compute answer for every node as root in O(n)). DP on tree with knapsack-like combining. Tree diameter via DP. Matching on trees. Independent set on trees. Counting subtree structures.
Network flow, matching, advanced shortest paths, and graph decomposition
Maximum flow problem. Ford-Fulkerson method (augmenting paths, BFS = Edmonds-Karp O(VE²)). Dinic's algorithm (blocking flows, O(V²E)). Min-cut max-flow theorem. Applications: bipartite matching, project selection, baseball elimination.
Hungarian algorithm. Hopcroft-Karp for O(E√V). König's theorem (min vertex cover = max matching in bipartite). Applications: job assignment, task scheduling, tiling problems. Reducing problems to bipartite matching.
Dijkstra with potentials (Johnson's algorithm for all-pairs with negative edges). A* search (heuristic-guided Dijkstra). Shortest path DAG reconstruction. K shortest paths. Bidirectional Dijkstra. 0-1 BFS with deque.
Euler path/circuit: visit every EDGE exactly once (Hierholzer's algorithm O(E)). Existence conditions for directed and undirected graphs. Hamiltonian path: visit every VERTEX exactly once (NP-complete, bitmask DP for small n). De Bruijn sequences.
Kosaraju's (two-pass DFS) and Tarjan's (single-pass with stack) algorithms for SCC. Condensation graph (DAG of SCCs). 2-SAT problem reduction to SCC. Applications: reachability in directed graphs, dependency resolution.
Weighted Union-Find (track distance/relationship to root). Rollback Union-Find (undo operations for offline problems). Union-Find with complementary sets. Applications: dynamic connectivity, Kruskal's with constraints.
DP optimisations and patterns beyond standard memoisation/tabulation
State = subset represented as bitmask. TSP in O(n²·2ⁿ). Assignment problem. Counting Hamiltonian paths. Profile DP for tiling (broken profile). Subset-sum optimisation with bitmasks. SOS DP (Sum over Subsets).
Count numbers in [L,R] satisfying a property. State: (position, tight constraint, property value). Classic: count numbers with digit sum = S, numbers without consecutive equal digits, numbers divisible by K. Template pattern for all digit DP problems.
Optimise DP transitions of the form dp[i] = min(dp[j] + cost(j,i)) where cost has a special structure. Maintain a convex hull of lines. Li Chao tree for online queries. Applications: USACO/IOI problems, sequence partitioning. Reduces O(n²) to O(n log n).
When the optimal split point is monotonic: opt(i,j) ≤ opt(i,j+1). Solve in O(n log n) instead of O(n²). Applications: optimal matrix partitioning, minimum cost to merge. Recognising monotonicity in the transition.
Specialised optimisation for interval DP where cost function satisfies the quadrangle inequality. Reduces O(n³) to O(n²). Applications: optimal BST construction, matrix chain multiplication variants. Proving the quadrangle inequality condition.
Topological order DP on directed acyclic graphs. Expected value DP: what's the expected number of coin flips to get heads? Probability of reaching a state. Random walk on graphs. Applications: game theory, stochastic processes in competitive programming.
Suffix structures, automata, and multi-pattern matching beyond KMP
Z-array: Z[i] = length of longest substring starting at i that matches a prefix. Applications beyond matching: counting occurrences, period of string. KMP failure function deep dive. Automaton construction from KMP.
Find ALL palindromic substrings in O(n). Longest palindromic substring without DP. Odd and even length palindromes. Count of palindromic substrings. The mirror trick that makes it linear.
Suffix array construction in O(n log n) or O(n log² n). LCP (Longest Common Prefix) array from suffix array using Kasai's algorithm. Applications: count distinct substrings, longest repeated substring, pattern matching. The most versatile string data structure.
Multi-pattern matching: search for ALL patterns simultaneously in O(text + patterns + matches). Build a trie of patterns + failure links (KMP on trie). Applications: censoring words, counting pattern occurrences, DNA sequence matching. When you have multiple patterns — Aho-Corasick, not KMP.
Polynomial rolling hash for O(1) substring comparison. Double hashing to reduce collision probability. Rabin-Karp with multiple patterns. Hash-based palindrome checking. Anti-hash tests (adversarial inputs). When hashing is practical vs when exact algorithms are needed.
The mathematical foundation for hard competitive programming and interview problems
Properties of modular operations. Modular inverse (using Fermat's little theorem for prime mod, extended Euclidean for general). Modular exponentiation (binary exponentiation). nCr mod p using Lucas' theorem. Handling large numbers with mod 10⁹+7.
Euler's totient function φ(n): count of numbers coprime to n. Euler's theorem: a^φ(n) ≡ 1 (mod n). Chinese Remainder Theorem for solving simultaneous congruences. Applications: RSA basics, cyclic group theory.
Sieve of Eratosthenes (standard + segmented for large ranges). Smallest prime factor sieve. Euler's sieve (linear). Mobius function and Mobius inversion. Multiplicative function sieving. Applications: counting coprime pairs, GCD sums.
Represent linear recurrences as matrix multiplication. Compute n-th Fibonacci in O(log n) using matrix power. Generalise to any linear recurrence. Applications: counting paths of length k in a graph, tiling problems. The "log n trick" for recurrences.
Inclusion-exclusion principle. Burnside's lemma (counting under symmetry). Catalan numbers (parenthesisations, BST counts, polygon triangulations). Stirling numbers. Derangements. Generating functions (conceptual). Stars and bars.
Nim game and Nim value (XOR of pile sizes). Sprague-Grundy theorem: every impartial game is equivalent to a Nim game. Computing Grundy numbers for game positions. Multi-game composition. Applications: stone games, moving on grids. The theory behind "Game" problems on Codeforces.
Points, lines, polygons, and convex hulls — geometry problems in competitive programming
Point representation, vector operations (dot product, cross product). Line segment intersection test. Point-in-polygon test (ray casting). Orientation of three points (clockwise/counterclockwise/collinear). Area of polygon using cross product (Shoelace formula).
Graham scan O(n log n), Andrew's monotone chain. Upper hull and lower hull. Applications: farthest pair (rotating calipers), smallest enclosing circle. Convex hull trick for DP (connecting geometry to optimisation).
Line sweep for closest pair of points (O(n log n) with balanced BST). Rectangle union area (sweep + segment tree). Count of intersection points. Event-based processing: sort events, maintain active set. The general sweep line framework.
Half-plane intersection. Voronoi diagram (conceptual). Rotating calipers for diameter/width. Polygon clipping (Sutherland-Hodgman). Point location. Common problem types in ICPC: geometric queries, polygon operations, coordinate transforms.
Fenwick trees in 2D, sparse tables, treaps, and specialised structures for specific problem patterns
2D BIT for matrix point updates and rectangle sum queries. BIT with range update + point query, range update + range query. Order-statistic tree using BIT. Count inversions with BIT. When BIT suffices vs when segment tree is needed.
Preprocess in O(n log n), answer range min/max (idempotent operations) in O(1). No updates supported — static only. Comparison: sparse table (static O(1) query) vs segment tree (dynamic O(log n) query) vs BIT (dynamic O(log n)).
Balanced BST using randomised priorities (expected O(log n) operations). Implicit treap (index-based): split and merge operations. Applications: rope data structure, array with arbitrary insertions/deletions in O(log n). More flexible than segment tree for some problems.
Bitwise trie for maximum XOR pair. Persistent trie for versioned prefix queries. Trie + DP combinations. Counting distinct substrings using trie/suffix automaton. Compressed trie (Patricia trie). Memory optimisation for large alphabets.
order_of_key() and find_by_order() in O(log n) — the indexed set. Useful in competitive programming for "count of elements less than X" queries. Implementation using __gnu_pbds::tree. When to use pbds vs BIT vs segment tree.
Winning contests and cracking hard interviews isn't just about algorithms — it's about strategy
Read all problems first. Estimate difficulty. Start with the easiest, not the first. When to skip vs when to invest time. Managing nervousness. The "2-minute rule": if you don't see an approach in 2 minutes, move on. Penalty-aware submission strategy.
ios_base::sync_with_stdio(false), cin.tie(nullptr). Pre-built templates: modular arithmetic, segment tree, DSU, graph input. Custom debugging macros (#define debug(x)). Contest-ready environment setup. The "judge will TLE your solution" problems where I/O matters.
Stress testing: generate random small inputs, compare brute force vs optimised. Finding counter-examples systematically. Common bug patterns: off-by-one, integer overflow, uninitialised variables, wrong MOD. "My solution works on samples but fails on judge" — systematic debugging approach.
The meta-skill: reading a problem statement and identifying which algorithm/technique applies within 2 minutes. Tag-based thinking: "this looks like a graph problem... connectivity... Union-Find." Building a mental index of 200+ problem archetypes through practice volume.
After a contest, solve the problems you couldn't during the contest — this is where growth happens. Editorial reading technique. Implementing solutions you only understood conceptually. Tracking weak areas (DP? graphs? math?) and targeting them. Moving from Pupil → Specialist → Expert on Codeforces.
| DSA (Standard Module) | Advanced DSA (This Module) | |
|---|---|---|
| Prerequisite | One programming language | DSA module completed |
| Duration | 50–80 hours | 40–60 hours |
| Data Structures | Arrays, linked lists, stacks, queues, trees, heaps, hash maps, basic trie | Segment trees (lazy), persistent DS, BIT 2D, treap, sparse table, Aho-Corasick automaton |
| Graph Algorithms | BFS, DFS, Dijkstra, Bellman-Ford, MST, topological sort, Union-Find | Network flow, bipartite matching, SCC in-depth, 2-SAT, advanced Union-Find, Euler path |
| DP Level | Standard patterns (1D, 2D, knapsack, LCS, LIS) | Bitmask DP, digit DP, convex hull trick, D&C DP optimisation, Knuth's optimisation, probability DP |
| Math | GCD, primes, basic modular arithmetic | Modular inverse, CRT, Euler's totient, matrix exponentiation, Mobius function, game theory |
| Strings | KMP, Z-algorithm, Rabin-Karp | Suffix array, Aho-Corasick, Manacher's, advanced hashing, suffix automaton |
| Techniques | Two pointers, sliding window, binary search on answer, prefix sum | Meet in the middle, Mo's algorithm, sqrt decomposition, coordinate compression, sweep line |
| Trees | Traversals, BST, AVL concepts | LCA (binary lifting), Euler tour, HLD, centroid decomposition, rerooting DP |
| Geometry | Not covered | Convex hull, sweep line, cross product, polygon operations |
| Target Audience | All placement-facing students | Product company aspirants, competitive programmers, ICPC/IOI contestants |
| Target Rating | LeetCode Medium / Codeforces Div 2 | LeetCode Hard / Codeforces Div 1 / ICPC Regional |
LeetCode Hard + Codeforces 1600+ rated problems. Tracked with topic-wise breakdowns on the platform.
Participate in Codeforces/LeetCode virtual contests weekly. Simulate real contest conditions. Track rating progression.
Segment tree, lazy propagation, BIT, trie, treap, sparse table — built from scratch, not copy-pasted.
Bitmask, digit, convex hull trick, D&C, Knuth's, probability — solve 5+ problems per technique.
After every contest, solve 2+ problems you couldn't during the contest. Document the approach. Build your problem archive.
Target: Codeforces Expert (1600+) or LeetCode contest rating 2000+. Measurable, trackable, achievable within this module.
Trainers with Codeforces Expert/Master ratings solve hard problems live — explaining the thought process, dead ends, and how they arrive at the right technique. 4–5 sessions per week.
2–3 hard problems daily on the coding platform. Company-tagged and contest-tagged. Automated testing with time tracking. AI hints guide technique selection, not solution.
4–5 problems in 2 hours, rated. Leaderboard tracks improvement. Post-contest editorial and upsolving session. Simulates Codeforces rounds and product company coding tests.
Dashboard shows problems solved per technique (segment tree: 8/15, digit DP: 3/10). Identifies which techniques need more practice. Rating progression graphed over time.
Google, Amazon, Microsoft, Flipkart, DE Shaw — their hardest interview problems require segment trees, advanced DP, and graph algorithms beyond Dijkstra. Standard DSA gets you through Round 1. Advanced DSA gets you through the final round where other candidates fail.
Codeforces, CodeChef, LeetCode Weekly, Google Code Jam, ICPC — contests where the problems START at standard DSA difficulty. To solve problems C, D, and E, you need advanced techniques. This module targets Codeforces Expert (1600+) rating.
Companies offering ₹15L+ packages (DE Shaw, Goldman Sachs, Uber, Flipkart) ask harder problems than companies offering ₹5L packages. The difficulty premium directly maps to compensation. Advanced DSA is the investment in higher-package placement outcomes.
Students targeting ICPC regionals/world finals, Google Code Jam, or algorithmic research need this depth. The module covers the complete competitive programming syllabus — sufficient for ICPC regional qualification and advanced algorithmic thinking.
E-305, Industrial Area, Sahibzada Ajit Singh Nagar, Punjab 160055, IN
