Problem Bank and Progression

Organize problems by:

Topic and subtopic.

Difficulty: introductory, easy, medium, hard, expert.

Company/interview relevance where verifiable.

Status: unseen, attempted, solved, needs review.

Personal notes and spaced-repetition review.

Every problem entry should contain a statement, constraints, examples, edge cases, hints, expected approach, proof, code, complexity, alternate approach, and related problems. Do not publish copied proprietary problem statements without permission; use original statements or appropriately licensed material.

The three entries below are original and follow the full format.

Problem 1 (easy) — Longest calm streak

Statement. A sensor logs integer readings. A *calm streak* is a contiguous run in which every two consecutive readings differ by at most k. Return the length of the longest calm streak.

Constraints. 1 ≤ n ≤ 2·10⁵, |reading| ≤ 10⁹, 0 ≤ k ≤ 10⁹. Example. [3, 5, 4, 10, 11, 9], k = 2 → 3 (10, 11, 9; also 3, 5, 4).

Edge cases. n = 1 → 1; all equal → n; differences up to 2·10⁹ need long long.

Hint. You only need to know whether each adjacent pair is calm.

Approach and proof. Scan once, extending the current streak while |aᵢ − aᵢ₋₁| ≤ k and restarting at 1 otherwise. Invariant: cur is the length of the longest calm streak ending at i. O(n) time, O(1) space.

Problem 2 (medium) — Cheapest repaint

Statement. A fence has n boards, each painted one of c colours. Repainting board i to colour j costs cost[i][j] (0 if it already has colour j). No two adjacent boards may share a colour. Find the minimum total cost.

Constraints. 1 ≤ n ≤ 10⁵, 2 ≤ c ≤ 20. Hint. The best choice for board i depends only on board i − 1's colour.

Approach. DP: dp[i][j] = cost[i][j] + min over j' ≠ j of dp[i−1][j']. Keeping the smallest and second-smallest values of the previous row makes each row O(c), so O(n·c) total. Proof by induction on i.

Problem 3 (hard) — Bridges that matter

Statement. A road network has n towns and m two-way roads (parallel roads allowed). For each query town q, report how many roads are *critical* for q: removing the road disconnects q from town 0.

Constraints. n, m ≤ 2·10⁵, many queries. Hint. Only bridges can be critical; contract 2-edge-connected components into a tree.

Approach. Find bridges with low-links (handling parallel edges by edge id, Module 33); contract components to get the bridge tree; root it at town 0's component. The answer for q is the depth of q's component. O(n + m) preprocessing, O(1) per query.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

In the example network, towns 0–2 form a cycle, towns 3 and 4 are joined by two parallel roads (neither is a bridge), and roads 2–3 and 4–5 are bridges — so town 5 depends on two critical roads.

#include <bits/stdc++.h>
using namespace std;

int calmStreak(const vector<long long>& a, long long k) {
    int best = 1, cur = 1;
    for (size_t i = 1; i < a.size(); ++i) { cur = llabs(a[i] - a[i - 1]) <= k ? cur + 1 : 1; best = max(best, cur); }
    return best;
}
long long repaint(const vector<vector<long long>>& cost) {
    int c = (int)cost[0].size(); vector<long long> prev = cost[0];
    for (size_t i = 1; i < cost.size(); ++i) {
        long long m1 = LLONG_MAX, m2 = LLONG_MAX; int arg = -1;
        for (int j = 0; j < c; ++j) { if (prev[j] < m1) { m2 = m1; m1 = prev[j]; arg = j; } else if (prev[j] < m2) m2 = prev[j]; }
        vector<long long> cur(c);
        for (int j = 0; j < c; ++j) cur[j] = cost[i][j] + (j == arg ? m2 : m1);
        prev = cur;
    }
    return *min_element(prev.begin(), prev.end());
}
long long repaintBrute(const vector<vector<long long>>& cost) {
    int n = (int)cost.size(), c = (int)cost[0].size(); long long best = LLONG_MAX; vector<int> col(n, 0);
    while (true) {
        bool ok = true; long long s = 0;
        for (int i = 0; i < n; ++i) { s += cost[i][col[i]]; if (i && col[i] == col[i - 1]) ok = false; }
        if (ok) best = min(best, s)
…

calm streak: 3, single reading: 1
cheapest repaint matches brute force over all colourings on 300 random fences
critical roads per town: 0 0 0 1 1 2
bridge-tree answers match brute-force road removal on 200 random networks

Quiz

? Why are the two parallel roads between towns 3 and 4 not critical?
+ Removing either one leaves the other, so the towns stay connected :: Edge ids make the bridge test handle this.
- They are longer :: Lengths are irrelevant.
- Town 4 is a leaf :: It is not.
- Parallel roads are always bridges :: The opposite.

? Problem 2's DP keeps the smallest and second-smallest previous costs. Why?
+ For colour j, the best previous colour must differ from j; if j is the argmin, use the second-smallest :: O(c) per row instead of O(c²).
- To sort the colours :: No.
- To handle negative costs :: Not the reason.
- It is an approximation :: It is exact; the brute force agrees.

? What should every problem-bank entry contain? (select all that apply)
+ An original or licensed statement with constraints and examples :: Do not copy proprietary statements.
+ Hints and the expected approach with a proof :: Progressive help.
+ Complexity and related problems :: Context.
- The author's ranking on contest sites :: Not needed.