Appearance
Speed Implementation Drills
Timed implementation practice for contest warm-up. Code each from scratch -- no references, no copy-paste. Track your times and watch them shrink.
Quick Revisit
- SKILL FOCUS: timed implementation -- muscle memory for contest templates
- DIFFICULTY: Tier 1 (easy) to Tier 3 (advanced)
- PROBLEMS: 30 drills across 3 tiers
- PREREQUISITE: Common Templates
How to Use
- Pick a drill matching your current practice focus
- Start a timer (use your phone or codeforces custom invocation)
- Code the solution from scratch in your contest IDE
- Test on 2-3 small inputs
- Compare against the target time
- If over target: practice daily until you hit it consistently
The goal isn't memorization -- it's muscle memory. When segment tree setup takes 2 minutes instead of 8, you have 6 extra minutes for thinking during a contest.
Tier 1: Foundations (Target: Under 3 Minutes)
These are the bread and butter. If any of these take more than 3 minutes, drill them daily.
| # | Drill | Target | What to Code |
|---|---|---|---|
| 1 | Sieve of Eratosthenes | 1:30 | Prime sieve up to N, output count of primes |
| 2 | Binary Search | 1:00 | lower_bound and upper_bound on sorted array |
| 3 | Prefix Sums (1D) | 1:00 | Build prefix array, answer L..R sum queries |
| 4 | Prefix Sums (2D) | 2:30 | Build 2D prefix, answer submatrix sum queries |
| 5 | DFS (recursive) | 1:30 | Count connected components in undirected graph |
| 6 | BFS (shortest path) | 2:00 | Shortest path on unweighted graph, print distance |
| 7 | BFS on Grid | 2:30 | Shortest path in grid with obstacles |
| 8 | Sorting + Custom Comparator | 1:00 | Sort structs by multiple fields |
| 9 | Two Pointers | 1:30 | Count pairs with sum <= K in sorted array |
| 10 | Sliding Window | 2:00 | Maximum sum subarray of length K |
Tier 2: Intermediate (Target: Under 5 Minutes)
These show up in Div2 C/D problems. Fluency here is the difference between solving in-contest vs. upsolving.
| # | Drill | Target | What to Code |
|---|---|---|---|
| 11 | DSU (Union-Find) | 2:30 | Path compression + union by rank, count components |
| 12 | BIT / Fenwick Tree | 3:00 | Point update + prefix sum query |
| 13 | Segment Tree (point update) | 4:00 | Build + point update + range sum query |
| 14 | Dijkstra | 4:00 | Shortest path with priority queue, print distances |
| 15 | Topological Sort (Kahn's) | 3:00 | BFS-based topo sort, detect cycle |
| 16 | 0/1 Knapsack | 3:30 | Space-optimized 1D DP |
| 17 | LIS (O(n log n)) | 3:00 | Longest increasing subsequence with lower_bound |
| 18 | Modular Inverse | 2:00 | Fermat's little theorem, mod exponentiation |
| 19 | Combinatorics Setup | 3:00 | Precompute factorials + inverse factorials, nCr queries |
| 20 | String Hashing | 3:30 | Polynomial hash with prefix array, substring comparison |
Tier 3: Advanced (Stretch Goal — Under 8 Minutes)
These separate 1700+ from 2000+. Each one saves massive time when it appears in a contest.
Stretch-goal note. The targets in this tier — 5-8 minutes for Dinic, centroid decomposition, suffix array — are aspirational benchmarks, not pass/fail bars. Hitting them consistently puts you at strong-division-1 implementation speed. If you are at 12-15 minutes after honest practice, that is normal and not a sign you are failing the drill.
| # | Drill | Target | What to Code |
|---|---|---|---|
| 21 | Lazy Segment Tree | 7:00 | Range add + range sum query |
| 22 | LCA with Binary Lifting | 6:00 | Preprocess in O(n log n), query in O(log n) |
| 23 | Centroid Decomposition | 7:00 | Find centroids, build centroid tree |
| 24 | Convex Hull | 6:00 | Andrew's monotone chain algorithm |
| 25 | KMP | 4:00 | Build failure function, find all occurrences |
| 26 | Z-Function | 3:30 | Build Z-array, find all pattern occurrences |
| 27 | SCC (Kosaraju's) | 6:00 | Two-pass DFS, output components |
| 28 | Max Flow (Dinic's) | 8:00 | BFS layering + DFS blocking flow |
| 29 | Suffix Array (O(n log^2 n)) | 7:00 | Rank-based construction with sorting |
| 30 | Matrix Exponentiation | 5:00 | Matrix multiply + fast power for linear recurrence |
My Times
Track your progress here. Date each attempt. Speed without correctness is not contest fluency — record the bug type if your code did not pass, and whether you wrote it from memory or had to peek.
Columns:
- Time — wall-clock minutes:seconds.
- From memory? Y/N — were references closed for the entire attempt?
- Bug type —
clean,off-by-one,overflow,init,transition,IO,other. Blank if AC on first run.
| Drill | Attempt 1 (time / mem? / bug) | Attempt 2 | Attempt 3 | Attempt 4 | Attempt 5 |
|---|---|---|---|---|---|
| Sieve | |||||
| Binary Search | |||||
| Prefix Sums 1D | |||||
| Prefix Sums 2D | |||||
| DFS | |||||
| BFS | |||||
| BFS Grid | |||||
| Custom Sort | |||||
| Two Pointers | |||||
| Sliding Window | |||||
| DSU | |||||
| BIT | |||||
| Segment Tree | |||||
| Dijkstra | |||||
| Topo Sort | |||||
| 0/1 Knapsack | |||||
| LIS | |||||
| Mod Inverse | |||||
| Combinatorics | |||||
| String Hash | |||||
| Lazy Seg Tree | |||||
| LCA | |||||
| Centroid | |||||
| Convex Hull | |||||
| KMP | |||||
| Z-Function | |||||
| SCC | |||||
| Max Flow | |||||
| Suffix Array | |||||
| Matrix Exp |
Weekly Drill Schedule
For maximum improvement, follow this rotation:
| Day | Focus | Drills |
|---|---|---|
| Monday | Foundations | #1-5 (all Tier 1) |
| Tuesday | Data Structures | #11-13 (DSU, BIT, SegTree) |
| Wednesday | Graphs | #6, #14, #15 (BFS, Dijkstra, TopoSort) |
| Thursday | DP + Math | #16-19 (Knapsack, LIS, Mod, Combinatorics) |
| Friday | Advanced | Pick 2 from Tier 3 |
| Weekend | Weak spots | Repeat any drill where you're over target |
After 2 weeks of daily drilling, most people cut their implementation time in half. That's 10-15 extra minutes per contest -- often the difference between solving D or not.
See also: Common Templates | Data Structure Selection Guide | Practice Ladders