SyntaxPilot
Courses/Competitive Programming/Lesson 88
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 88 of 90

Contest walkthrough: a Div 2 D-E set

queued

These are the notes for Competitive Programming episode 88. The original Div 2 round from episode 87 continues with the two problems that usually separate ratings. Problem D, Heavy Truck: towns, roads with weight limits, and the heaviest truck that can drive from town 1 to town n. Trying every limit with a BFS is correct but needs m BFS runs; the observation that the answer is monotonic (if W tons get through, every lighter truck does too) turns it into a binary search on the answer with about 30 BFS runs. On the way we hit the classic stuck binary search (mid rounded down while lo = mid). Problem E, Rising Tunes: count strictly increasing subsequences modulo 10^9 + 7. A quadratic DP counts tunes by their last note; a Fenwick tree over compressed values turns its inner loop into a prefix sum, and the equal-values bug (sum(r) instead of sum(r − 1)) is caught on the second sample and by a stress test. Both problems were written for this course. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real. Where a run was slow, the notes say "seconds" instead of quoting a stopwatch: timings depend on the machine.

The real-life hook

The weighbridge on the highway. If a 12-ton truck got through every road of a route, then a 10-ton truck on the same roads surely gets through too: same roads, lighter load. So "does a W-ton truck get through?" is true, true, true, ..., false, false as W grows. That shape is called monotonic, and a monotonic yes/no question can be answered by binary search: a few test drives, each one halving the range of possible answers.

The running tally on a staircase. Picture a staircase where each step is a pitch. On every step you keep a tally: how many tunes so far ended on that pitch. When a new note arrives, the tunes it can finish are the ones ending on lower steps, so you add up the tallies below it (a prefix sum over pitches), then write the new count on its own step for later notes. A prefix sum that also needs updates is exactly what a Fenwick tree does, in O(log n) each.

How we attack D and E in a contest

The same loop as episode 87, for every problem:

  1. Brute force first, typed straight from the statement. Slow, but obviously right: it is the referee.
  2. Find the observation that removes the slow part (here: monotonic answer; prefix sum over values).
  3. Prove it in one or two sentences.
  4. Stress test the fast solution against the referee on many small random tests, aimed at where the bug can live (no-route maps; equal notes).
  5. Only then submit.

Problem D · Heavy Truck

  • n towns and m roads, n, m ≤ 2·10^5. Road i joins towns u and v (both directions) and holds at most c[i] tons, 1 ≤ c[i] ≤ 10^9.
  • Print the heaviest truck (in whole tons) that can drive from town 1 to town n, or −1 if there is no route at all.
  • A route works for a W-ton truck if every road on it has c ≥ W: the weakest road decides (this is called a bottleneck path).

Sample.

5 6
1 2 7
2 5 3
1 3 4
3 4 6
4 5 5
2 3 9

Answer 5. The short route 1 → 2 → 5 has a 3-ton road. 1 → 3 → 4 → 5 has limits 4, 6, 5: weakest 4. 1 → 2 → 3 → 4 → 5 has limits 7, 9, 6, 5: weakest 5, and no route does better.

The tool we use twice: check(W). Keep only the roads with c ≥ W and run a BFS (breadth-first search) from town 1. If town n is reached, a W-ton truck gets through. One check is O(n + m).

Try every weight (the referee)

The answer is always one of the road limits (the weakest road of the best route), so the brute force tries every limit as the truck weight and keeps the heaviest that gets through.

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    roads.resize(m);
    for (auto& [u, v, c] : roads) cin >> u >> v >> c;
    int best = -1;
    for (auto [u, v, c] : roads)                    // try every limit as the truck weight
        if (c > best && gets_through(c)) best = c;
    cout << best << "\n";
}

On the sample:

5

When town 3 cannot be reached at all (3 1 / 1 2 10):

-1

Now a big test made inside the program: 100000 towns and 200000 roads (a chain 1-2-...-n, then random roads, random limits up to 10^9). We stop after just 600 of the 200000 weights:

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int main() {
    mt19937 gen(88);
    n = 100000;
    m = 200000;                                     // the largest test
    roads.resize(m);
    for (int i = 0; i < m; i++) {
        int u = i < n - 1 ? i + 1 : gen() % n + 1;      // a chain 1-2-...-n, then random roads
        int v = i < n - 1 ? i + 2 : gen() % n + 1;
        roads[i] = {u, v, (int)(gen() % 1000000000) + 1};
    }
    int best = -1, tried = 0;
    for (auto [u, v, c] : roads) {
        if (++tried > 600) { cout << "only 600 weights tried\n"; return 0; }
        if (c > best && gets_through(c)) best = c;
    }
}
only 600 weights tried

It already took a second or two for 600 of 200000 weights; all of them would take minutes. That is m BFS runs: O(m · (n + m)), about 8·10^10 steps at the limits. Time Limit Exceeded.

Monotonic answer: binary search on the answer

Claim. If check(W) is true, then check(W') is true for every W' < W. Proof. The roads with c ≥ W are a subset of the roads with c ≥ W'. The route that worked for W uses only those roads, so it also works for W'.

So check is true ... true false ... false as W grows, and we binary search for the last true. Weights go up to 10^9, so about ⌈log2 10^9⌉ = 30 checks: 30 BFS runs instead of 200000.

We keep the invariant "lo always gets through": lo = 0 means "no truck", which trivially works. hi = 10^9 is the largest possible answer.

My first version rounds mid down. A round counter is added only to watch what happens:

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    roads.resize(m);
    for (auto& [u, v, c] : roads) cin >> u >> v >> c;
    int lo = 0, hi = 1000000000;                    // lo always gets through (0 = no truck)
    int rounds = 0;
    while (lo < hi) {
        if (++rounds > 100) { cout << "stuck: lo = " << lo << ", hi = " << hi << "\n"; return 0; }
        int mid = (lo + hi) / 2;
        if (gets_through(mid)) lo = mid;            // mid works: the answer is mid or more
        else hi = mid - 1;
    }
    cout << (gets_through(lo) && lo > 0 ? lo : -1) << "\n";
}

On the sample:

stuck: lo = 4, hi = 5

With lo = 4 and hi = 5, mid = (4 + 5) / 2 = 4. A 4-ton truck gets through, so lo = mid = 4 again: nothing changes, for ever. Without the counter that is an infinite loop, so Time Limit Exceeded.

Rule. If one branch does lo = mid, mid must round up: mid = lo + (hi − lo + 1) / 2. Then mid > lo whenever lo < hi, and every round shrinks the range. (If the branches are hi = mid and lo = mid + 1, round down instead.) Writing lo + (hi − lo + 1) / 2 rather than (lo + hi + 1) / 2 also avoids overflow when lo and hi are near the top of int.

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    roads.resize(m);
    for (auto& [u, v, c] : roads) cin >> u >> v >> c;
    int lo = 0, hi = 1000000000;                    // lo always gets through (0 = no truck)
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;            // round UP, so lo = mid always moves
        if (gets_through(mid)) lo = mid;            // mid works: the answer is mid or more
        else hi = mid - 1;
    }
    cout << (gets_through(lo) && lo > 0 ? lo : -1) << "\n";
}

Sample: 5. No-route case: -1.

The big test (every weight in play, n = 100000, m = 200000):

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int main() {
    mt19937 gen(88);
    n = 100000;
    m = 200000;                                     // the largest test
    roads.resize(m);
    for (int i = 0; i < m; i++) {
        int u = i < n - 1 ? i + 1 : gen() % n + 1;      // a chain 1-2-...-n, then random roads
        int v = i < n - 1 ? i + 2 : gen() % n + 1;
        roads[i] = {u, v, (int)(gen() % 1000000000) + 1};
    }
    int lo = 0, hi = 1000000000;                    // lo always gets through (0 = no truck)
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;            // round UP, so lo = mid always moves
        if (gets_through(mid)) lo = mid;            // mid works: the answer is mid or more
        else hi = mid - 1;
    }
    cout << (gets_through(lo) && lo > 0 ? lo : -1) << "\n";
}
521784497

Well under a second.

Stress test against trying every weight

A thousand random small maps (2 to 7 towns, 0 to 7 roads, self-loops and repeated roads allowed, many with no route at all):

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int brute() {
    int best = -1;
    for (auto [u, v, c] : roads) if (c > best && gets_through(c)) best = c;
    return best;
}

int fast() {
    int lo = 0, hi = 1000000000;                    // lo always gets through (0 = no truck)
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;            // round UP, so lo = mid always moves
        if (gets_through(mid)) lo = mid;            // mid works: the answer is mid or more
        else hi = mid - 1;
    }
    return gets_through(lo) && lo > 0 ? lo : -1;
}

int main() {
    mt19937 gen(88);
    for (int it = 1; it <= 1000; it++) {
        n = gen() % 6 + 2;
        m = gen() % 8;
        roads.resize(m);
        for (auto& [u, v, c] : roads) { u = gen() % n + 1; v = gen() % n + 1; c = gen() % 10 + 1; }
        if (brute() != fast()) { cout << "differs on test " << it; return 0; }
    }
    cout << "all 1000 tests agree";
}
all 1000 tests agree

Submit. D: accepted.

Problem E · Rising Tunes

  • A melody of n ≤ 2·10^5 notes, pitches 1 ≤ a[i] ≤ 10^9.
  • A rising tune keeps some of the notes, in their original order, each one strictly higher than the one before (a strictly increasing subsequence).
  • Count the rising tunes with at least one note, modulo 10^9 + 7.

Samples. 1 3 2 4 → 11: four single notes; five pairs (1 3, 1 2, 1 4, 3 4, 2 4); two triples (1 3 4, 1 2 4). 5 5 5 → 3: equal notes don't rise, so only the three single notes.

The referee: try all 2^n subsets of positions and count the strictly increasing ones. Fine for n ≤ 12.

The n² DP: count tunes by their last note

dp[i] = the number of rising tunes whose last note is note i.

  • Note i alone is one tune.
  • Any tune ending at an earlier note j with a[j] < a[i] can be extended by note i.

So dp[i] = 1 + Σ dp[j] over j < i with a[j] < a[i], and the answer is Σ dp[i].

On the sample 1 3 2 4:

note 1 3 2 4
dp 1 1 + 1 = 2 1 + 1 = 2 1 + (1 + 2 + 2) = 6

Total 1 + 2 + 2 + 6 = 11.

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

const ll MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    vector<ll> dp(n);                               // dp[i]: rising tunes that END at note i
    ll total = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;                                  // note i on its own
        for (int j = 0; j < i; j++)
            if (a[j] < a[i]) dp[i] = (dp[i] + dp[j]) % MOD;   // extend a tune ending at j
        total = (total + dp[i]) % MOD;
    }
    cout << total << "\n";
}

Sample: 11. 5 5 5: 3.

A test with only 30000 notes, far below the limit:

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

const ll MOD = 1000000007;

int main() {
    mt19937 gen(88);
    int n = 30000;                                  // far below the limit
    vector<ll> a(n);
    for (ll& x : a) x = gen() % 1000000000 + 1;
    vector<ll> dp(n);                               // dp[i]: rising tunes that END at note i
    ll total = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;                                  // note i on its own
        for (int j = 0; j < i; j++)
            if (a[j] < a[i]) dp[i] = (dp[i] + dp[j]) % MOD;   // extend a tune ending at j
        total = (total + dp[i]) % MOD;
    }
    cout << total << "\n";
}
513431750

It took seconds already; 200000 notes is about 44 times more work (n²/2 ≈ 2·10^10 pairs). Time Limit Exceeded.

Fenwick tree over values

The inner loop is "sum of dp over earlier notes with a smaller pitch". If we index by pitch instead of position, that is a prefix sum over pitches, and it changes as we go (each note adds its dp). A Fenwick tree (binary indexed tree, episode 63) supports both in O(log n):

  • add(i, v): add v at index i;
  • sum(i): the sum of indices 1..i.

Pitches go up to 10^9, so first compress them (episode 9): sort the distinct pitches, and the rank of a pitch is its position 1..k in that sorted list (lower_bound + 1). Equal pitches get equal ranks.

My first version:

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

const ll MOD = 1000000007;

struct Fenwick {                                    // prefix sums that also allow updates
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }   // 1..i
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    vector<ll> vals(a);                             // compress: value -> rank 1..k
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Fenwick fw(vals.size());
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll d = (1 + fw.sum(r)) % MOD;               // tunes ending at a value up to x
        fw.add(r, d);
        total = (total + d) % MOD;
    }
    cout << total << "\n";
}

Sample 1 3 2 4:

11

The sample passes. The second sample, 5 5 5:

7

Expected 3. fw.sum(r) includes tunes ending at the same pitch, so a 5 is allowed after a 5: dp values become 1, 2, 4 and 1 + 2 + 4 = 7. Strictly higher means ranks 1..r − 1:

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

const ll MOD = 1000000007;

struct Fenwick {                                    // prefix sums that also allow updates
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }   // 1..i
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    vector<ll> vals(a);                             // compress: value -> rank 1..k
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Fenwick fw(vals.size());
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll d = (1 + fw.sum(r - 1)) % MOD;           // tunes ending at a SMALLER value
        fw.add(r, d);
        total = (total + d) % MOD;
    }
    cout << total << "\n";
}

5 5 5: 3. 1 3 2 4: 11.

Stress test against all subsets

With pitches 1..6 and up to 12 notes, almost every test has equal notes, which is exactly where the bug lived:

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

const ll MOD = 1000000007;

struct Fenwick {                                    // prefix sums that also allow updates
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }   // 1..i
};

ll brute(vector<ll>& a) {                           // every subset of positions
    int n = a.size();
    ll cnt = 0;
    for (int s = 1; s < (1 << n); s++) {
        ll last = LLONG_MIN;
        bool ok = true;
        for (int i = 0; i < n; i++)
            if (s >> i & 1) { if (a[i] <= last) ok = false; last = a[i]; }
        cnt += ok;
    }
    return cnt % MOD;
}

ll fast(vector<ll>& a) {
    vector<ll> vals(a);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Fenwick fw(vals.size());
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll d = (1 + fw.sum(r - 1)) % MOD;
        fw.add(r, d);
        total = (total + d) % MOD;
    }
    return total;
}

int main() {
    mt19937 gen(88);
    for (int it = 1; it <= 1000; it++) {
        int n = gen() % 12 + 1;
        vector<ll> a(n);
        for (ll& x : a) x = gen() % 6 + 1;   // many equal notes
        if (brute(a) != fast(a)) { cout << "differs on test " << it; return 0; }
    }
    cout << "all 1000 tests agree";
}
all 1000 tests agree

The full size, 200000 notes:

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

const ll MOD = 1000000007;

struct Fenwick {                                    // prefix sums that also allow updates
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }   // 1..i
};

int main() {
    mt19937 gen(88);
    int n = 200000;                                 // the largest test
    vector<ll> a(n);
    for (ll& x : a) x = gen() % 1000000000 + 1;
    vector<ll> vals(a);                             // compress: value -> rank 1..k
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Fenwick fw(vals.size());
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll d = (1 + fw.sum(r - 1)) % MOD;           // tunes ending at a SMALLER value
        fw.add(r, d);
        total = (total + d) % MOD;
    }
    cout << total << "\n";
}
194949241

A blink. Submit. E: accepted, and that's the whole round.

Complexity vs the constraints

Limits: n, m ≤ 2·10^5, time limit 2 seconds (about 10^8 to 10^9 simple steps).

Method Time Memory Verdict
D: BFS for every weight O(m · (n + m)) ≈ 8·10^10 O(n + m) TLE
D: binary search + BFS O((n + m) · log C), log C ≈ 30 O(n + m) Accepted
D: DSU, strongest roads first (practice 1) O(m log m) O(n + m) Accepted
E: all subsets O(2^n · n) O(n) referee only
E: n² DP O(n²) ≈ 2·10^10 pairs O(n) TLE
E: Fenwick over compressed values O(n log n) O(n) Accepted

Common mistakes (and the real outputs)

Mistake What you see Why Fix
mid = (lo + hi) / 2 with lo = mid stuck: lo = 4, hi = 5 (infinite loop → TLE) mid rounds down to lo mid = lo + (hi − lo + 1) / 2
binary search on a check that is not monotonic Wrong Answer true/false must switch exactly once prove the monotonic shape first
fw.sum(r) when the statement says strictly 7 instead of 3 on 5 5 5 counts tunes ending at the same pitch fw.sum(r − 1)
Fenwick indexed by the raw pitch (up to 10^9) Memory Limit Exceeded an array of 10^9 entries compress to ranks 1..k
forgetting % MOD inside the Fenwick wrong numbers after overflow values grow past 2^63 take % MOD in add and sum
printing lo when there is no route 0 instead of -1 lo = 0 is the "no truck" start print −1 when lo = 0
trusting the first sample E passed 1 3 2 4 and was still wrong no equal notes in it stress test with tiny value ranges

Mini project: a reusable "binary search on the answer" helper

Most binary-search-on-the-answer problems look the same: a monotonic check and a range. Write the search once, with the rounding rule built in, and reuse it. last_true(lo, hi, check) returns the largest x in [lo, hi] with check(x) true, assuming check(lo) is true and the shape is true ... true false ... false. first_true is the mirror image.

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

// Largest x in [lo, hi] with check(x) true.  Needs: check(lo) true, shape true...true false...false.
ll last_true(ll lo, ll hi, const function<bool(ll)>& check) {
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1) / 2;              // lo = mid below: round UP
        if (check(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
}

// Smallest x in [lo, hi] with check(x) true.  Needs: check(hi) true, shape false...false true...true.
ll first_true(ll lo, ll hi, const function<bool(ll)>& check) {
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;                  // hi = mid below: round DOWN
        if (check(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

int main() {
    ll N = 1000000000000LL;                           // integer square root of 10^12
    cout << "isqrt(10^12) = " << last_true(0, 2000000, [&](ll x) { return x * x <= N; }) << "\n";
    vector<ll> s = {7, 2, 5, 10, 8};                  // tasks in order, at most k = 2 days
    int k = 2;
    auto days_ok = [&](ll X) {                        // greedy: close a day before it exceeds X
        int days = 1; ll cur = 0;
        for (ll x : s) {
            if (x > X) return false;
            if (cur + x > X) { days++; cur = 0; }
            cur += x;
        }
        return days <= k;
    };
    cout << "min largest day = " << first_true(1, 32, days_ok) << "\n";
}

Output:

isqrt(10^12) = 1000000
min largest day = 18

Practice

These are the homework problems from the episode, written for this course. All outputs are real.

1. D with a DSU. Solve Heavy Truck without binary search: add roads from the strongest down with a DSU (disjoint set union) until towns 1 and n are in the same group.

Solution

Sort roads by limit, largest first, and join their towns. The moment 1 and n become connected, the road just added is the weakest road on some route made only of roads at least as strong, so its limit is achievable; and no heavier truck works, because with only the strictly stronger roads (all added before) 1 and n were not connected. If they never connect, print −1. O(m log m) for the sort, almost O(1) per DSU operation.

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

vector<int> par;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> roads(m);                   // {limit, u, v}
    for (auto& [c, u, v] : roads) cin >> u >> v >> c;
    sort(roads.rbegin(), roads.rend());               // strongest road first
    par.resize(n + 1);
    iota(par.begin(), par.end(), 0);
    for (auto [c, u, v] : roads) {
        par[find(u)] = find(v);                       // this road joins two groups of towns
        if (find(1) == find(n)) { cout << c << "\n"; return 0; }   // the weakest road used so far
    }
    cout << -1 << "\n";
}

Sample: 5. No-route case (3 1 / 1 2 10): -1. A stress test against "try every weight" on 1000 random small maps:

all 1000 tests agree

2. Rising tunes of exactly three notes. Count strictly increasing subsequences of length exactly 3, modulo 10^9 + 7.

Solution

Keep one Fenwick tree per length. For each note with rank r: tunes of length 3 ending here = (length-2 tunes ending at a smaller pitch) = f2.sum(r − 1); tunes of length 2 ending here = f1.sum(r − 1); tunes of length 1 = 1. Add them to their trees after reading the sums, so a note never extends itself. O(n log n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;

struct Fenwick {
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    vector<ll> vals(a);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int k = vals.size();
    Fenwick f1(k), f2(k);                             // f1: tunes of length 1, f2: length 2, by last pitch
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll len3 = f2.sum(r - 1);                      // extend a length-2 tune ending lower
        ll len2 = f1.sum(r - 1);                      // extend a single lower note
        total = (total + len3) % MOD;
        f2.add(r, len2);
        f1.add(r, 1);
    }
    cout << total << "\n";
}

1 3 2 4: 2 (1 3 4 and 1 2 4). 1 2 3 4 5: 10 (= C(5, 3)).

3. Non-decreasing tunes. Same as E, but equal notes are allowed (each note ≥ the one before).

Solution

Now a tune may continue on the same pitch, so the prefix goes up to and including the rank: fw.sum(r). That is exactly the "bug" from the episode, which is the right answer to this different question.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;

struct Fenwick {
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    vector<ll> vals(a);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Fenwick fw(vals.size());
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll d = (1 + fw.sum(r)) % MOD;                 // equal pitches are allowed now: sum up to r
        fw.add(r, d);
        total = (total + d) % MOD;
    }
    cout << total << "\n";
}

5 5 5: 7 (three singles, three pairs, one triple). 1 3 2 4: 11 (no equal notes, so the same as E).

A stress test of practices 2 and 3 against all subsets (n ≤ 10, pitches 1..5):

all 1000 tests agree

4. The lightest truck that can't get through. Print the smallest W for which a W-ton truck cannot reach town n (or say that every truck fails because there is no route).

Solution

It is just answer + 1 from Problem D: check is true up to the answer and false from answer + 1 on. If D prints −1 (no route), then even a 1-ton truck fails, so the answer is 1. This is the "first false" of the same monotonic check.

5. Minimum days. n tasks with sizes s[i] must be done in order, and you split them into at most k consecutive days. Minimise the largest day's total.

Solution

check(X) = "a greedy split, closing a day just before it would exceed X, uses at most k days". It is monotonic (a bigger X never needs more days), so binary search the first true X in [max s, Σ s]. With hi = mid / lo = mid + 1, mid rounds down. O(n log Σ s).

Quick quiz

// notes: 2 1 2
// rising tunes (strictly higher each time), at least one note?

A) 3 · B) 4 · C) 5 · D) 6

Answer

B. Three single notes, plus the pair 1 → 2 (positions 2 and 3). 2 → 2 does not rise, and 2 → 1 goes down. Total 4.

Interview questions

  1. What is binary search on the answer? Instead of searching an array, you search the range of possible answers, using a yes/no check that is monotonic in the answer.
  2. How do you know a check is monotonic? Prove that a yes for x implies a yes for every smaller (or larger) x. For Heavy Truck: the roads allowed for W are a subset of those allowed for any lighter W'.
  3. Why does mid = (lo + hi) / 2 loop for ever with lo = mid? When hi = lo + 1, mid = lo; if check(mid) is true the range does not change. Round up instead.
  4. What is a bottleneck path, and two ways to find it? A route maximising its weakest edge. Binary search + BFS, or a DSU adding edges from strongest down (a maximum spanning tree idea).
  5. How do you count strictly increasing subsequences in O(n log n)? dp by last element, dp[i] = 1 + Σ dp over smaller earlier values, kept in a Fenwick tree over compressed values.
  6. What is coordinate compression and why is it needed here? Map each value to its rank among the distinct values, so a Fenwick tree needs only n slots instead of 10^9.
  7. sum(r − 1) or sum(r)? Strictly increasing: r − 1 (exclude equal values). Non-decreasing: r.
  8. Why take the result modulo 10^9 + 7? The count can be up to 2^n − 1, astronomically large; the modulus keeps numbers in 64 bits, and 10^9 + 7 is a prime the problem fixes so answers can be compared.
  9. Why write a brute force in a contest? It is a referee: a stress test against it finds bugs the samples miss, like the equal-notes bug here.

Glossary

Term Meaning Example
Div 2 round A contest for lower-rated participants, problems A, B, C, ... getting harder today: D and E
Brute force A slow solution typed straight from the statement try every weight
Referee A brute force used to check a fast solution brute() in the stress tests
Stress test Many random small tests comparing two solutions all 1000 tests agree
Graph Nodes joined by edges towns and roads
BFS (breadth-first search) Visit nodes in rings outward from a start, with a queue gets_through
Weight limit / capacity The most a road can carry c[i]
Bottleneck path A route whose weakest edge is as strong as possible 1-2-3-4-5, weakest 5
Monotonic check A yes/no that switches only once as x grows true ... true false ... false
Binary search on the answer Halve the range of possible answers with a monotonic check ~30 BFS runs
Invariant Something kept true every round "lo always gets through"
Round up / round down (hi − lo + 1) / 2 vs (hi − lo) / 2 for mid round up when lo = mid
Infinite loop A loop whose state never changes stuck: lo = 4, hi = 5
DSU (disjoint set union) Tracks groups of joined nodes with find/unite practice 1
Subsequence Some elements kept in their original order 1 3 4 from 1 3 2 4
Strictly increasing Each element bigger than the previous 1 < 3 < 4
Non-decreasing Each element at least the previous 5 5 5
DP (dynamic programming) Build answers from answers to smaller subproblems dp[i] by last note
Prefix sum The sum of the first i items fw.sum(r − 1)
Fenwick tree (BIT) Prefix sums with point updates, O(log n) each struct Fenwick
i & -i The lowest set bit of i, the Fenwick step size 12 & −12 = 4
Coordinate compression Replace values by their ranks among distinct values 10^9 → rank ≤ n
Rank A value's position 1..k in the sorted distinct list lower_bound(...) + 1
Modulo 10^9 + 7 Keep the remainder after division by this prime huge counts
TLE / MLE Time / Memory Limit Exceeded verdicts n² DP; Fenwick of size 10^9
Overflow A number too big for its type wraps around why % MOD everywhere

Summary

  • D: the weakest road decides. check(W) = BFS on the roads with c ≥ W. check is monotonic, so binary search the answer: ~30 BFS runs, O((n + m) log C). Or a DSU adding the strongest roads first.
  • With lo = mid in one branch, round mid up: mid = lo + (hi − lo + 1) / 2; otherwise the search gets stuck (we saw stuck: lo = 4, hi = 5).
  • E: count by the last note, dp[i] = 1 + Σ dp[j] over earlier smaller notes. The inner loop is a prefix sum over values: compress pitches, use a Fenwick tree, sum(r − 1) for strictly higher. O(n log n).
  • Samples are not proof: E passed 1 3 2 4 with the bug. Stress test where the bug can live (no-route maps, equal notes).

Solutions in C++, Java and Python

Accepted solutions for both problems. Each was run on the samples; the outputs are shown.

Problem D · Heavy Truck

C++

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

int n, m;
vector<array<int, 3>> roads;                       // {u, v, weight limit}

bool gets_through(int W) {                          // BFS on roads that hold a W-ton truck
    vector<vector<int>> adj(n + 1);
    for (auto [u, v, c] : roads)
        if (c >= W) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> q;
    q.push(1);
    seen[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; q.push(y); }
    }
    return seen[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    roads.resize(m);
    for (auto& [u, v, c] : roads) cin >> u >> v >> c;
    int lo = 0, hi = 1000000000;                    // lo always gets through (0 = no truck)
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;            // round UP, so lo = mid always moves
        if (gets_through(mid)) lo = mid;            // mid works: the answer is mid or more
        else hi = mid - 1;
    }
    cout << (gets_through(lo) && lo > 0 ? lo : -1) << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] U, V, Cap;

    static boolean getsThrough(int w) {               // BFS on roads that hold a w-ton truck
        int[] head = new int[n + 1], nxt = new int[2 * m], to = new int[2 * m];
        Arrays.fill(head, -1);
        int e = 0;
        for (int i = 0; i < m; i++) if (Cap[i] >= w) {
            to[e] = V[i]; nxt[e] = head[U[i]]; head[U[i]] = e++;
            to[e] = U[i]; nxt[e] = head[V[i]]; head[V[i]] = e++;
        }
        boolean[] seen = new boolean[n + 1];
        int[] q = new int[n];
        int qh = 0, qt = 0;
        q[qt++] = 1; seen[1] = true;
        while (qh < qt) {
            int x = q[qh++];
            for (int k = head[x]; k != -1; k = nxt[k]) if (!seen[to[k]]) { seen[to[k]] = true; q[qt++] = to[k]; }
        }
        return seen[n];
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        n = nextInt(in); m = nextInt(in);
        U = new int[m]; V = new int[m]; Cap = new int[m];
        for (int i = 0; i < m; i++) { U[i] = nextInt(in); V[i] = nextInt(in); Cap[i] = nextInt(in); }
        int lo = 0, hi = 1000000000;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;             // round up: lo = mid always moves
            if (getsThrough(mid)) lo = mid; else hi = mid - 1;
        }
        System.out.println(lo > 0 && getsThrough(lo) ? lo : -1);
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}

Python

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    roads = [(int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])) for i in range(m)]

    def gets_through(w):                     # BFS on roads that hold a w-ton truck
        adj = [[] for _ in range(n + 1)]
        for u, v, c in roads:
            if c >= w:
                adj[u].append(v)
                adj[v].append(u)
        seen = [False] * (n + 1)
        seen[1] = True
        q = deque([1])
        while q:
            x = q.popleft()
            for y in adj[x]:
                if not seen[y]:
                    seen[y] = True
                    q.append(y)
        return seen[n]

    lo, hi = 0, 10**9
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2        # round up
        if gets_through(mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo if lo > 0 and gets_through(lo) else -1)

main()

All three print 5 on the sample and -1 on 3 1 / 1 2 10. (Python's 30 BFS runs over 2·10^5 roads are slow on the largest tests; in a contest with Python, prefer the DSU version from practice 1, which sorts once.)

Problem E · Rising Tunes

C++

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

const ll MOD = 1000000007;

struct Fenwick {                                    // prefix sums that also allow updates
    vector<ll> t;
    Fenwick(int n) : t(n + 1, 0) {}
    void add(int i, ll v) { for (; i < (int)t.size(); i += i & -i) t[i] = (t[i] + v) % MOD; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }   // 1..i
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    vector<ll> vals(a);                             // compress: value -> rank 1..k
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Fenwick fw(vals.size());
    ll total = 0;
    for (ll x : a) {
        int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        ll d = (1 + fw.sum(r - 1)) % MOD;           // tunes ending at a SMALLER value
        fw.add(r, d);
        total = (total + d) % MOD;
    }
    cout << total << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    static long[] t;

    static void add(int i, long v) { for (; i < t.length; i += i & -i) t[i] = (t[i] + v) % MOD; }
    static long sum(int i) { long s = 0; for (; i > 0; i -= i & -i) s = (s + t[i]) % MOD; return s; }

    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int n = (int) st.nval;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) { st.nextToken(); a[i] = (long) st.nval; }   // pitches ≤ 10^9 are exact in a double
        long[] vals = a.clone();
        Arrays.sort(vals);
        int k = 0;
        for (int i = 0; i < n; i++) if (i == 0 || vals[i] != vals[i - 1]) vals[k++] = vals[i];   // unique
        t = new long[k + 1];
        long total = 0;
        for (long x : a) {
            int r = Arrays.binarySearch(vals, 0, k, x) + 1;   // rank 1..k
            long d = (1 + sum(r - 1)) % MOD;                  // tunes ending at a SMALLER pitch
            add(r, d);
            total = (total + d) % MOD;
        }
        System.out.println(total);
    }
}

Python

import sys
from bisect import bisect_left

MOD = 10**9 + 7

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    vals = sorted(set(a))                    # compress: pitch -> rank 1..k
    k = len(vals)
    t = [0] * (k + 1)
    total = 0
    for x in a:
        r = bisect_left(vals, x) + 1
        i, s = r - 1, 0                      # Fenwick sum over ranks 1..r-1 (SMALLER pitches)
        while i > 0:
            s += t[i]
            i -= i & -i
        d = (1 + s) % MOD
        i = r
        while i <= k:                        # Fenwick add d at rank r
            t[i] = (t[i] + d) % MOD
            i += i & -i
        total = (total + d) % MOD
    print(total)

main()

All three print 11 on 1 3 2 4 and 3 on 5 5 5.