Appearance
Mock Contest 2 -- The Technique Gauntlet
Time limit: 2.5 hoursTarget audience: Codeforces 1400-1800
This contest tests your technique toolkit. Each problem deliberately isolates a core algorithmic skill so the result is diagnostic: if D is the wall, you need data-structure work; if E is the wall, graph modeling; if F is unreachable, that is the stretch goal of this set.
Set a timer. No editorials until time is up. No template lookups mid-contest — if you cannot write a BIT or topo-sort from memory, that result is part of the diagnostic.
Quick Revisit
- Six-problem technique diagnostic (rated ~1400 to ~1900) — each problem is selected to isolate one technique.
- Use the Technique Diagnostic table afterwards to map each unsolved problem to a study area.
- Prerequisite: Data Structure Selection Guide.
Problems
| # | Problem | Expected Difficulty | Time Target | Core Technique |
|---|---|---|---|---|
| A | CF 1623C -- Balanced Stone Heaps | 1400 | 15 min | Binary search on answer -- reverse simulation |
| B | CF 1579E2 -- Array Optimization by Deque (Hard) | 1500 | 20 min | Greedy + BIT/merge sort -- inversion counting |
| C | CF 1498C -- Planar Reflections | 1600 | 25 min | DP -- model particle decay across planes |
| D | CF 1354D -- Multiset | 1700 | 30 min | Binary Indexed Tree -- k-th element query |
| E | CF 1385E -- Directing Edges | 1800 | 30 min | Topological sort -- orient undirected edges in DAG |
| F | CF 1175E -- Minimal Segment Cover | 1900 | 30 min | Sparse table / binary lifting on intervals |
Diagnostic Read-out
A single mock cannot reliably estimate rating, but it can locate the next gap. Use the table below as a diagnostic, then drill the specific area below.
| Problems Solved | Diagnostic | Where to focus next |
|---|---|---|
| A only | Comfortable with one technique (binary search on answer); breadth still missing | Drill BIT and basic DP on the practice ladders |
| A + B | Good fundamentals; struggling with DP modeling | Push into DP territory — Mock 2's C and Chapter 4 |
| A + B + C | Solid mid-range; data structures are the next ceiling | BIT and segment tree drills, then attempt D |
| A + B + C + D | Strong toolkit; combining techniques is the bottleneck | Multi-technique problems (graph + DP, sweep + BIT) |
| A through E | Broad technique coverage at this band | Move on to harder problems and Div 1 attempts |
| All 6 | This set no longer diagnoses you | Try Mock 3 (speed) or Educational Round virtuals |
Technique Diagnostic
Use your results to identify gaps:
| Problem | If You Couldn't Solve It | Study Area |
|---|---|---|
| A | Binary search on answer | Complexity Cheatsheet -- look for monotonic properties |
| B | Inversion counting with BIT | Data Structure Selection Guide |
| C | DP state design | DP vs Greedy Guide |
| D | BIT operations | Data Structure Selection Guide |
| E | Topological sort + construction | BFS vs DFS Guide |
| F | Sparse table / binary lifting | Advanced -- study interval covering with jump pointers |
Post-Contest Reflection
After the timer ends, answer in your Mistake Journal:
- Technique gaps: Which techniques did you know in theory but fail to implement? Those are your highest-ROI study targets.
- Modeling time: How long did it take you to see what technique each problem needed? Fast recognition = fast solves.
- Code from memory: Could you write BIT/topo-sort/segment tree without looking anything up? If not, drill those templates.
- Partial progress: For unsolved problems, how far did you get? Did you have the right idea but wrong implementation?
- Ordering strategy: Did you solve them in order? Would skipping a hard problem and coming back have helped?
Detailed Walkthrough (read after attempting)
Problem A -- Balanced Stone Heaps
Binary search on the minimum value of the final array. For a candidate answer mid, simulate the process in reverse (from last pile to first). Each pile with value > mid can distribute stones backward to earlier piles (undo the forward operation). If all piles can reach >= mid, the answer is feasible.
Key insight: processing in reverse lets you "undo" the giving operation. Common mistake: processing forward instead of backward, or integer overflow on stone counts.
Problem B -- Array Optimization by Deque
For each element, you choose to push_front or push_back. To minimize inversions, count how many existing elements are greater (push_front cost) vs. smaller (push_back cost). Pick the cheaper side. Use a BIT/Fenwick tree for efficient counting.
Key insight: each decision is locally optimal -- greedy works because future elements don't affect past inversion counts. Common mistake: not compressing coordinates before using BIT.
Problem C -- Planar Reflections
DP where state = (remaining planes, current decay countdown). A particle hitting a plane splits: one continues forward with same countdown, one reflects backward with countdown-1. Track how many particles are alive. Since countdown <= k <= 1000 and planes <= 1000, the DP table is manageable.
Key insight: particles with countdown = 1 don't split further, which bounds the state space. Common mistake: trying to simulate all particles explicitly (exponential blowup).
Problem D -- Multiset
Maintain a BIT over values 1..n. For additions, update BIT at position a_i. For deletions (k-th smallest), binary search on the BIT prefix sums to find the k-th element, then remove it.
Key insight: BIT prefix sum = count of elements <= x, so binary search on prefix sums finds k-th smallest in O(log^2 n) or O(log n) with BIT walk. Common mistake: using a slow k-th element query (nested binary search instead of BIT descent).
Problem E -- Directing Edges
First, build a graph with only the directed edges. If it has a cycle, output "NO". Otherwise, topologically sort the directed graph. Then orient each undirected edge from earlier to later in the topological order -- this guarantees no cycles.
Key insight: undirected edges oriented along topological order can never create cycles. Common mistake: forgetting that the directed-only graph might already have cycles.
Problem F -- Minimal Segment Cover
Preprocess: for each left endpoint x, find the farthest right endpoint reachable by any segment starting at or before x. Then build a binary lifting table: jump[k][x] = farthest right reachable from x using 2^k segments. To answer a query [l, r], greedily jump from l using the largest powers of 2 first, counting segments.
Key insight: this is the classic "minimum intervals to cover a range" problem, accelerated from O(n) per query to O(log n) with sparse table. Common mistake: off-by-one in the lifting table boundaries, or not merging overlapping initial segments correctly.
See also: Mock Contest 1 | Mock Contest 3 (Speed) | Mistake Journal | Practice Ladder 1400-1700