SyntaxPilot
Courses/Competitive Programming/Lesson 89
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 89 of 90

Contest walkthrough: a hard Div 1 set

queued

These are the notes for Competitive Programming episode 89. After the Div 2 round of episodes 87 and 88, the level goes up to a hard Div 1 set. In Div 1 one trick is rarely enough: each problem needs two ideas from the course to meet. Problem A, Night Walks: crossings, streets with a darkness level, and 2·10^5 questions "from crossing v, using only streets with darkness ≤ k, how many crossings can you reach?" A BFS per question is correct but far too slow; answering the questions offline (sorted by k) while a DSU merges areas street by street answers all of them in one sweep. On the way we hit the answers-in-the-wrong-order bug. Problem B, Skyline Imbalance: the sum of (tallest − shortest) over every block of neighbouring buildings. Visiting 2·10^10 blocks is hopeless; the contribution technique asks each building how many blocks it wins, and a monotonic stack finds those counts in O(n). A tie bug that passes the sample is caught by a stress test with many equal heights. 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

Lighting up the town. On a festival night the organisers light the streets one by one, the least dark street first. With every new street, more of the town is walkable, and nothing that was walkable ever stops being walkable. A question "what can I reach on streets of darkness ≤ k?" is just a snapshot of the town at the moment the k-th level has been lit. So instead of answering questions in the order they arrive, collect them, sort them by k, and answer each one at its moment while the town lights up. Areas only ever merge, which is exactly what a DSU (disjoint set union) is built for.

Who wins each block? Instead of walking along the skyline and looking at every block, ask each tower: of how many blocks am I the tallest? A tower is the tallest of every block that starts after the nearest taller tower on its left and ends before the nearest taller tower on its right. Standing on a roof and looking left and right, shorter towers are hidden behind a taller one: that is the idea behind the monotonic stack.

How we attack a Div 1 problem

The same loop as episodes 87 and 88, with one extra question:

  1. Brute force first, typed straight from the statement. Slow, but obviously right: it is the referee.
  2. Which two ideas meet here? In Div 1, the slow part usually needs one idea to reorganise the problem (offline order, splitting a sum) and a second one to make it fast (a DSU, a monotonic stack).
  3. Prove the observation 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 (repeated k values; equal heights).
  5. Only then submit.

Problem A · Night Walks

  • n crossings, m streets, q questions; n, m, q ≤ 2·10^5.
  • Street i joins crossings u and v (both directions) and has a darkness d[i], 1 ≤ d[i] ≤ 10^9. Streets may repeat and may loop back to the same crossing.
  • Question (v, k): starting at crossing v and walking only on streets with darkness ≤ k, how many crossings can you reach (counting v itself)? 0 ≤ k ≤ 10^9.
  • Print the answers in the order the questions are given.

Sample. Input: n m q, then m lines u v d, then q lines v k.

5 5 4
1 2 3
2 3 5
3 4 2
4 5 8
1 5 6
1 4
3 5
5 1
2 10

Output 2 4 1 5 (one per line). From 1 with k = 4 only the street 1–2 (darkness 3) and 3–4 (darkness 2) are usable, and only 1–2 touches crossing 1: {1, 2}, so 2. From 3 with k = 5: streets 3–4, 1–2 and 2–3 give {1, 2, 3, 4}, so 4. From 5 with k = 1: no street is that light, so 1. With k = 10 every street is usable: 5.

A BFS per question (the referee)

Keep only the streets with d ≤ k and run a BFS (breadth-first search) from v, counting the crossings it reaches. One question costs O(n + m).

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

int reach(int n, vector<array<int, 3>>& st, int s, int k) {   // BFS on streets with darkness <= k
    vector<vector<int>> adj(n + 1);
    for (auto [d, u, v] : st)
        if (d <= k) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> qu;
    qu.push(s);
    seen[s] = 1;
    int cnt = 1;
    while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; cnt++; qu.push(y); }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> st(m);                    // {darkness, u, v}
    for (auto& [d, u, v] : st) cin >> u >> v >> d;
    vector<array<int, 3>> qs(q);                    // {k, v, index}
    for (int i = 0; i < q; i++) { cin >> qs[i][1] >> qs[i][0]; qs[i][2] = i; }
    for (auto [k, v, i] : qs) cout << reach(n, st, v, k) << "\n";   // one BFS per question
}

On the sample:

2
4
1
5

On the largest test (2·10^5 crossings, streets and questions), stopping after only 300 questions:

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

int reach(int n, vector<array<int, 3>>& st, int s, int k) {   // BFS on streets with darkness <= k
    vector<vector<int>> adj(n + 1);
    for (auto [d, u, v] : st)
        if (d <= k) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> qu;
    qu.push(s);
    seen[s] = 1;
    int cnt = 1;
    while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; cnt++; qu.push(y); }
    }
    return cnt;
}

int main() {
    mt19937 gen(89);
    int n = 200000, m = 200000, q = 200000;         // the largest test
    vector<array<int, 3>> st(m);
    for (auto& [d, u, v] : st) { u = gen() % n + 1; v = gen() % n + 1; d = gen() % 1000000000 + 1; }
    vector<array<int, 3>> qs(q);
    for (int i = 0; i < q; i++) qs[i] = {(int)(gen() % 1000000000) + 1, (int)(gen() % n) + 1, i};
    ll sum = 0;
    for (int i = 0; i < 300; i++) sum += reach(n, st, qs[i][1], qs[i][0]);
    cout << "only 300 questions answered\n";
}
only 300 questions answered

That already takes seconds. All 2·10^5 questions would be about 700 times more: q BFS runs of n + m each, around 8·10^10 steps. Time Limit Exceeded.

The observation: k only grows, so the town only joins up

Look at the usable streets as k grows: every street usable at k is still usable at any bigger k. The town's areas (connected components) only merge, never split. Two ideas meet:

  1. Offline order. An online problem must answer each question before seeing the next one. Here nothing stops us from reading all questions first and answering them in any order we like, as long as we print in the original order. That is called answering offline. Sort the questions by k.
  2. A DSU with sizes. Sort the streets by darkness. Sweep the sorted questions with a pointer j into the sorted streets: before answering a question with value k, open (unite) every street with darkness ≤ k. The answer is the size of v's set.

Each street is opened once and each question is answered once, so the whole sweep is two sorts plus m DSU operations.

The sweep on the sample, in order of k:

question (sorted) streets opened before it v's area answer
k = 1, v = 5 none {5} 1
k = 4, v = 1 3–4 (d 2), 1–2 (d 3) {1, 2} 2
k = 5, v = 3 2–3 (d 5) {1, 2, 3, 4} 4
k = 10, v = 2 1–5 (d 6), 4–5 (d 8) {1, 2, 3, 4, 5} 5

We answered them as 1, 2, 4, 5, but the questions were asked as 2, 4, 1, 5. Keep that in mind.

The DSU, and the order bug

The DSU uses union by size (attach the smaller tree under the bigger one) and path halving (p[x] = p[p[x]] while walking up), so every operation is close to constant time. The first version prints each answer as soon as it has it:

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

struct DSU {                                        // union by size
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> st(m);                    // {darkness, u, v}
    for (auto& [d, u, v] : st) cin >> u >> v >> d;
    vector<array<int, 3>> qs(q);                    // {k, v, index}
    for (int i = 0; i < q; i++) { cin >> qs[i][1] >> qs[i][0]; qs[i][2] = i; }
    sort(st.begin(), st.end());                     // streets by darkness
    sort(qs.begin(), qs.end());                     // questions by k: OFFLINE
    DSU dsu(n);
    int j = 0;
    for (auto [k, v, i] : qs) {
        while (j < m && st[j][0] <= k) { dsu.unite(st[j][1], st[j][2]); j++; }   // light every street <= k
        cout << dsu.sz[dsu.find(v)] << "\n";        // print as we go
    }
}
1
2
4
5

The right numbers in the wrong order: the judge expects 2 4 1 5, so this is Wrong Answer on test 1. Each question carries its original index for exactly this reason: store the answer at that index and print the array at the end.

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

struct DSU {                                        // union by size
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> st(m);                    // {darkness, u, v}
    for (auto& [d, u, v] : st) cin >> u >> v >> d;
    vector<array<int, 3>> qs(q);                    // {k, v, index}
    for (int i = 0; i < q; i++) { cin >> qs[i][1] >> qs[i][0]; qs[i][2] = i; }
    sort(st.begin(), st.end());                     // streets by darkness
    sort(qs.begin(), qs.end());                     // questions by k: OFFLINE
    DSU dsu(n);
    vector<int> ans(q);
    int j = 0;
    for (auto [k, v, i] : qs) {
        while (j < m && st[j][0] <= k) { dsu.unite(st[j][1], st[j][2]); j++; }   // light every street <= k
        ans[i] = dsu.sz[dsu.find(v)];               // store at the ORIGINAL index
    }
    for (int x : ans) cout << x << "\n";
}
2
4
1
5

The largest test, all 2·10^5 questions:

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

struct DSU {                                        // union by size
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    mt19937 gen(89);
    int n = 200000, m = 200000, q = 200000;         // the largest test
    vector<array<int, 3>> st(m);
    for (auto& [d, u, v] : st) { u = gen() % n + 1; v = gen() % n + 1; d = gen() % 1000000000 + 1; }
    vector<array<int, 3>> qs(q);
    for (int i = 0; i < q; i++) qs[i] = {(int)(gen() % 1000000000) + 1, (int)(gen() % n) + 1, i};
    sort(st.begin(), st.end());                     // streets by darkness
    sort(qs.begin(), qs.end());                     // questions by k: OFFLINE
    DSU dsu(n);
    vector<int> ans(q);
    int j = 0;
    for (auto [k, v, i] : qs) {
        while (j < m && st[j][0] <= k) { dsu.unite(st[j][1], st[j][2]); j++; }   // light every street <= k
        ans[i] = dsu.sz[dsu.find(v)];               // store at the ORIGINAL index
    }
    ll sum = 0;
    for (int x : ans) sum += x;
    cout << "all " << q << " answered, sum " << sum << "\n";
}
all 200000 answered, sum 6468918465

A fraction of a second.

Stress test against the BFS

A thousand random small towns (1 to 6 crossings, 0 to 7 streets with darkness 1..5, loops and repeated streets allowed), with k from 0 to 5, so repeated k values and k = 0 both happen:

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

int reach(int n, vector<array<int, 3>>& st, int s, int k) {   // BFS on streets with darkness <= k
    vector<vector<int>> adj(n + 1);
    for (auto [d, u, v] : st)
        if (d <= k) { adj[u].push_back(v); adj[v].push_back(u); }
    vector<char> seen(n + 1, 0);
    queue<int> qu;
    qu.push(s);
    seen[s] = 1;
    int cnt = 1;
    while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for (int y : adj[x]) if (!seen[y]) { seen[y] = 1; cnt++; qu.push(y); }
    }
    return cnt;
}

struct DSU {                                        // union by size
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

vector<int> fast(int n, vector<array<int, 3>> st, vector<array<int, 3>> qs) {
    int m = st.size(), q = qs.size();
    sort(st.begin(), st.end());                     // streets by darkness
    sort(qs.begin(), qs.end());                     // questions by k: OFFLINE
    DSU dsu(n);
    vector<int> ans(q);
    int j = 0;
    for (auto [k, v, i] : qs) {
        while (j < m && st[j][0] <= k) { dsu.unite(st[j][1], st[j][2]); j++; }   // light every street <= k
        ans[i] = dsu.sz[dsu.find(v)];               // store at the ORIGINAL index
    }
    return ans;
}

int main() {
    mt19937 gen(89);
    for (int it = 1; it <= 1000; it++) {
        int n = gen() % 6 + 1, m = gen() % 8, q = gen() % 5 + 1;
        vector<array<int, 3>> st(m), qs(q);
        for (auto& [d, u, v] : st) { u = gen() % n + 1; v = gen() % n + 1; d = gen() % 5 + 1; }
        for (int i = 0; i < q; i++) qs[i] = {(int)(gen() % 6), (int)(gen() % n) + 1, i};
        vector<int> f = fast(n, st, qs);
        for (int i = 0; i < q; i++)
            if (f[i] != reach(n, st, qs[i][1], qs[i][0])) { cout << "differs on test " << it; return 0; }
    }
    cout << "all 1000 tests agree";
}
all 1000 tests agree

Accepted.

Problem B · Skyline Imbalance

  • n ≤ 2·10^5 buildings in a row with heights 1 ≤ h[i] ≤ 10^6.
  • A block is any run of neighbouring buildings (a subarray). Its imbalance is its tallest height minus its shortest height.
  • Print the sum of the imbalance over all n(n + 1)/2 blocks.

Sample. 3 / 3 1 2 → 5. Single buildings give 0; 3 1 gives 2, 1 2 gives 1, 3 1 2 gives 3 − 1 = 2.

How big is the answer? About 2·10^10 blocks, each with imbalance below 10^6: up to about 2·10^16. That needs a long long (an int stops at about 2.1·10^9).

The brute force: grow every block

Fix the left end, grow the block to the right, and keep a running max and min. O(n²) blocks, O(1) each.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    ll total = 0;
    for (int i = 0; i < n; i++) {                   // every left end
        ll mx = h[i], mn = h[i];
        for (int j = i; j < n; j++) {               // grow to the right
            mx = max(mx, h[j]);
            mn = min(mn, h[j]);
            total += mx - mn;
        }
    }
    cout << total << "\n";
}
5

At half the limit (10^5 buildings):

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

int main() {
    mt19937 gen(89);
    int n = 100000;                                 // half the limit
    vector<ll> h(n);
    for (ll& x : h) x = gen() % 1000000 + 1;
    ll total = 0;
    for (int i = 0; i < n; i++) {                   // every left end
        ll mx = h[i], mn = h[i];
        for (int j = i; j < n; j++) {               // grow to the right
            mx = max(mx, h[j]);
            mn = min(mn, h[j]);
            total += mx - mn;
        }
    }
    cout << total << "\n";
}
4998122720665539

Seconds already; the full size has four times as many blocks. Time Limit Exceeded.

The observation: count what each building wins

Two ideas meet again.

  1. Split the sum. Σ (max − min) = Σ max − Σ min, and the min of h is minus the max of −h. So one function, wins(h) = the sum over all blocks of the max, answers both halves: wins(h) + wins(−h).
  2. Contribution technique. Instead of visiting blocks, count, for each building i, how many blocks it is the maximum of, and add h[i] times that count. If L is the nearest taller building on the left (or −1) and R the nearest taller one on the right (or n), building i is the tallest of every block that starts in (L, i] and ends in [i, R): that is (i − L) · (R − i) blocks.
  3. Monotonic stack. The nearest taller building on each side, for every i at once, comes from a stack of indices whose heights decrease from bottom to top: when a building arrives, pop every shorter one (they are hidden behind it). Each index is pushed and popped once, so it is O(n) (episode 70).

Example for 3 1 2: building 3 has L = −1, R = 3, so it wins 1 · 3 = 3 blocks (3, 3 1, 3 1 2) → 9. Building 1 has L = 0, R = 2 → 1 block → 1. Building 2 has L = 0, R = 3 → 2 blocks (2, 1 2) → 4. Σ max = 14. For the minimum, Σ min = 9 (3, 1, 2, 1, 1, 1 → 3 + 1 + 2 + 1 + 1 + 1). 14 − 9 = 5.

The tie bug

In the first version both stack loops stop at a building that is taller or equal:

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

ll wins(vector<ll> h) {                             // sum over subarrays of the max
    int n = h.size();
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {                   // nearest taller OR EQUAL on the left
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {              // nearest taller OR EQUAL on the right
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += h[i] * (i - L[i]) * (R[i] - i);   // i is the max of this many
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    ll mx = wins(h);
    for (ll& x : h) x = -x;                         // the min of h is minus the max of -h
    ll mn = -wins(h);
    cout << mx - mn << "\n";
}
5

The sample passes, but every height in it is different. The stress test against an O(n³) referee, with only three different heights so that ties are everywhere:

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

ll wins(vector<ll> h) {                             // sum over subarrays of the max
    int n = h.size();
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {                   // nearest taller OR EQUAL on the left
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {              // nearest taller OR EQUAL on the right
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += h[i] * (i - L[i]) * (R[i] - i);   // i is the max of this many
    return sum;
}

ll fast(vector<ll> h) {
    ll mx = wins(h);
    for (ll& x : h) x = -x;
    return mx + wins(h);
}

ll referee(vector<ll>& h) {                         // try every subarray, O(n^3)
    int n = h.size();
    ll total = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            ll mx = *max_element(h.begin() + i, h.begin() + j + 1);
            ll mn = *min_element(h.begin() + i, h.begin() + j + 1);
            total += mx - mn;
        }
    return total;
}

int main() {
    mt19937 gen(89);
    for (int it = 1; it <= 1000; it++) {
        int n = gen() % 6 + 1;
        vector<ll> h(n);
        for (ll& x : h) x = gen() % 3 + 1;           // few heights: many ties
        if (fast(h) != referee(h)) {
            cout << "differs on test " << it << ":";
            for (ll x : h) cout << " " << x;
            cout << "\nfast " << fast(h) << ", referee " << referee(h);
            return 0;
        }
    }
    cout << "all 1000 tests agree";
}
differs on test 1: 1 1 1 3
fast 8, referee 6

Why: in a block like 1 1 there are two shortest buildings. Each of them stops at the other, so neither claims the block, and it disappears from the sum. Ties make blocks vanish (and if both loops walked past equal buildings instead, the same block would be counted twice).

The fix is a tie-break: the leftmost tallest building owns the block. On the left, stop at taller or equal; on the right, walk past equal buildings and stop only at a strictly taller one. Then every block has exactly one owner. One character changes: < becomes <= in the right-hand loop.

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

ll wins(vector<ll> h) {                             // sum over subarrays of the max
    int n = h.size();
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {                   // nearest taller OR EQUAL on the left
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {              // nearest strictly taller on the right
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += h[i] * (i - L[i]) * (R[i] - i);   // i is the max of this many
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    ll mx = wins(h);
    for (ll& x : h) x = -x;                         // the min of h is minus the max of -h
    ll mn = -wins(h);
    cout << mx - mn << "\n";
}

The failing case, the sample and a single building:

6
5
0

The stress test again:

all 1000 tests agree

And the full size, 2·10^5 buildings:

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

ll wins(vector<ll> h) {                             // sum over subarrays of the max
    int n = h.size();
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {                   // nearest taller OR EQUAL on the left
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {              // nearest strictly taller on the right
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += h[i] * (i - L[i]) * (R[i] - i);   // i is the max of this many
    return sum;
}

int main() {
    mt19937 gen(89);
    int n = 200000;                                 // the largest test
    vector<ll> h(n);
    for (ll& x : h) x = gen() % 1000000 + 1;
    ll mx = wins(h);
    for (ll& x : h) x = -x;                         // the min of h is minus the max of -h
    ll mn = -wins(h);
    cout << mx - mn << "\n";
}
19996020908063641

Instant, and close to 2·10^16, safe in a long long. Accepted.

Complexity vs the constraints

Solution Time Memory Verdict at the limits
A: one BFS per question O(q · (n + m)) ≈ 8·10^10 O(n + m) TLE
A: offline + DSU O(m log m + q log q + (m + q) · α(n)) O(n + m + q) Accepted
B: every block with its own max and min O(n³) O(n) referee only
B: grow blocks with a running max/min O(n²) ≈ 2·10^10 O(n) TLE
B: contribution + monotonic stack O(n) O(n) Accepted

α(n) is the inverse Ackermann function: at most 4 or 5 for any n you will ever see, so DSU operations are effectively constant time.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
printing answers while sweeping the sorted questions 1 2 4 5 instead of 2 4 1 5 (Wrong Answer on test 1) sorted order is not the input order store ans[index], print at the end
going offline in an online problem impossible: the next question depends on your last answer online problems hide the next query read the statement; use a persistent or online structure (practice 2)
stopping at an equal height on both sides differs on test 1: 1 1 1 3, fast 8, referee 6 blocks with a tied max/min have no owner >= on one side, > on the other
multiplying (i - L) * (R - i) in int negative or wrong sums on big tests 10^5 · 10^5 overflows before h is even multiplied keep h and the product in long long
forgetting streets with d exactly k answers too small the statement says darkness ≤ k st[j][0] <= k in the pointer loop

Mini project: who wins each block?

A small tool that prints, for every building, its L, R and the number of blocks it is the tallest of, and checks that the counts add up to n(n + 1)/2 (every block has exactly one owner). Run it whenever you are unsure about a tie-break.

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

// Who wins each block? Prints, for every building, its L, R and how many blocks it is the tallest of.
int main() {
    int n;
    cin >> n;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && h[s.top()] < h[i]) s.pop();   // stop at taller OR EQUAL
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();  // stop only at strictly taller
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll blocks = 0;
    for (int i = 0; i < n; i++) {
        ll w = (ll)(i - L[i]) * (R[i] - i);
        blocks += w;
        printf("building %d (height %lld): L = %2d, R = %d, tallest of %lld blocks\n", i, h[i], L[i], R[i], w);
    }
    printf("total %lld = n(n+1)/2 = %d\n", blocks, n * (n + 1) / 2);
}

Input 4 / 2 1 2 2:

building 0 (height 2): L = -1, R = 4, tallest of 4 blocks
building 1 (height 1): L =  0, R = 2, tallest of 1 blocks
building 2 (height 2): L =  0, R = 4, tallest of 4 blocks
building 3 (height 2): L =  2, R = 4, tallest of 1 blocks
total 10 = n(n+1)/2 = 10

The three 2s share the blocks between them without overlap: the first 2 owns every block it is the leftmost tallest of.

Practice

1. Streets too. For every question of Problem A, also print how many streets lie inside the reachable area (streets with d ≤ k whose ends are both reachable).

Solution

Keep an extra counter ed per DSU root. Every opened street adds one to its area's counter, even when both ends are already in the same area (a loop or a second street). When two areas merge, the new root's counter is the sum of both plus one.

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

struct DSU {                                        // union by size, plus a street count per area
    vector<int> p, sz, ed;
    DSU(int n) : p(n + 1), sz(n + 1, 1), ed(n + 1, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) { ed[a]++; return; }            // a street inside one area still counts
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        ed[a] += ed[b] + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> st(m);
    for (auto& [d, u, v] : st) cin >> u >> v >> d;
    vector<array<int, 3>> qs(q);
    for (int i = 0; i < q; i++) { cin >> qs[i][1] >> qs[i][0]; qs[i][2] = i; }
    sort(st.begin(), st.end());
    sort(qs.begin(), qs.end());
    DSU dsu(n);
    vector<pair<int, int>> ans(q);
    int j = 0;
    for (auto [k, v, i] : qs) {
        while (j < m && st[j][0] <= k) { dsu.unite(st[j][1], st[j][2]); j++; }
        int r = dsu.find(v);
        ans[i] = {dsu.sz[r], dsu.ed[r]};
    }
    for (auto [c, e] : ans) cout << "crossings " << c << ", streets " << e << "\n";
}

Input: the sample with one extra street 2 4 1:

5 6 4
1 2 3
2 3 5
3 4 2
4 5 8
1 5 6
2 4 1
1 4
3 5
5 1
2 10
crossings 4, streets 3
crossings 4, streets 4
crossings 1, streets 0
crossings 5, streets 6

2. Online Night Walks. Answer Problem A online: each question must be answered before the next one is read (in real contests this is enforced by encoding the next question with your last answer).

Solution

Build a Kruskal reconstruction tree. Add the streets in order of darkness as in Kruskal's algorithm; every time two different areas a and b merge, create a new node x with value = that street's darkness and children a and b. The crossings are the leaves 1..n. Values never decrease towards the root, so "everything reachable from v on streets ≤ k" is exactly the set of leaves under the highest ancestor of v whose value is ≤ k. Find that ancestor with binary lifting (episode 53) and store the leaf count of every node. O((n + m) log n + q log n), fully online.

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

// Kruskal reconstruction tree: add streets by darkness; each union creates a NEW node whose value is that street's
// darkness and whose children are the two areas. Leaves 1..n are the crossings. Values grow towards the root, so
// "streets with darkness <= k from v" = the subtree of the highest ancestor of v with value <= k.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> st(m);
    for (auto& [d, u, v] : st) cin >> u >> v >> d;
    sort(st.begin(), st.end());
    int N = 2 * n;
    vector<int> dsu(N), val(N, 0), leaves(N, 0);
    vector<array<int, 2>> ch(N, {0, 0});
    iota(dsu.begin(), dsu.end(), 0);
    function<int(int)> find = [&](int x) { while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]]; return x; };
    for (int i = 1; i <= n; i++) leaves[i] = 1;
    int cnt = n;
    for (auto [d, u, v] : st) {
        int a = find(u), b = find(v);
        if (a == b) continue;
        int x = ++cnt;                              // a new node for this merge
        val[x] = d;
        ch[x] = {a, b};
        leaves[x] = leaves[a] + leaves[b];
        dsu[a] = dsu[b] = x;
    }
    const int LOG = 20;
    vector<array<int, LOG>> up(cnt + 1);
    for (int x = 1; x <= cnt; x++) up[x].fill(x);   // a root points to itself
    for (int x = cnt; x > n; x--)                   // parents have bigger ids, so fill from the top down
        for (int c : ch[x]) up[c][0] = x;
    for (int x = cnt; x >= 1; x--)                  // up[x][0] > x, so up[x][0]'s table is ready first
        for (int j = 1; j < LOG; j++) up[x][j] = up[up[x][j - 1]][j - 1];
    while (q--) {                                   // online: answer each question before reading the next
        int v, k;
        cin >> v >> k;
        for (int j = LOG - 1; j >= 0; j--)
            if (up[v][j] != v && val[up[v][j]] <= k) v = up[v][j];
        cout << leaves[v] << "\n";
    }
}
2
4
1
5

The same answers as the offline sweep, and a stress test of this program against A_OK on 300 random towns agreed on every test.

3. Only the tallest, blocks of 2 or more. Print the sum of the tallest height over all blocks with at least two buildings.

Solution

That is wins(h) minus the blocks of length 1, whose tallest is the building itself: wins(h) − Σ h.

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

ll wins(vector<ll> h) {                             // sum over subarrays of the max (episode 89)
    int n = h.size();
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += h[i] * (i - L[i]) * (R[i] - i);
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    ll singles = accumulate(h.begin(), h.end(), 0LL);   // a block of one building: its own height
    cout << wins(h) - singles << "\n";
}

Input 3 / 3 1 2:

8

(3 1 → 3, 1 2 → 2, 3 1 2 → 3: total 8.)

4. Calm blocks. Count the blocks whose imbalance is at most k (n ≤ 2·10^5).

Solution

If a block is calm, every smaller block inside it is calm too, so two pointers work: for each right end r, the calm blocks ending at r are exactly those starting in [l, r], where l is the smallest calm start. Keep the max and min of the window with two monotonic deques (a decreasing one for the max, an increasing one for the min), each index pushed and popped once: O(n).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    deque<int> mx, mn;                              // indices; heights decreasing in mx, increasing in mn
    ll count = 0;
    int l = 0;
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && h[mx.back()] <= h[r]) mx.pop_back();
        mx.push_back(r);
        while (!mn.empty() && h[mn.back()] >= h[r]) mn.pop_back();
        mn.push_back(r);
        while (h[mx.front()] - h[mn.front()] > k) { // too wild: drop the left end
            l++;
            if (mx.front() < l) mx.pop_front();
            if (mn.front() < l) mn.pop_front();
        }
        count += r - l + 1;                         // every block ending at r and starting in [l, r]
    }
    cout << count << "\n";
}

Input 4 1 / 3 1 2 2:

7

(The four single buildings, plus 1 2, 2 2 and 1 2 2.)

Quick quiz

// heights: 2 2
// blocks: [2], [2], [2 2]
// sum of the tallest building of every block?

A) 4 · B) 6 · C) 8 · D) 2

Answer: B, 6. Three blocks, each with tallest 2. With the tie-break (stop at ≥ on the left, at > on the right), the left 2 has L = −1, R = 2 and owns 2 blocks; the right 2 has L = 0, R = 2 and owns 1. If you got 4, both buildings stopped at each other and the block 2 2 vanished: the tie bug.

Interview questions

  1. What does "answering queries offline" mean, and when is it allowed? Reading all queries first and answering them in a convenient order (usually sorted), then printing in the original order. It is allowed whenever the queries do not depend on earlier answers.
  2. Why does Night Walks suit a DSU but not "remove a street" queries? A DSU only merges. Removing edges would split components, which a plain DSU cannot undo (that needs offline reversal, rollback, or dynamic connectivity).
  3. What do union by size and path compression give you? Together, near-constant time per operation: O(α(n)) amortised.
  4. Explain the contribution technique. Rewrite a sum over many objects (blocks, pairs, subsets) as a sum over small pieces (elements) of "piece × number of objects where it plays a role", then count those objects with a formula.
  5. How does a monotonic stack find the nearest greater element in O(n)? Keep indices with decreasing values; each new element pops all smaller ones, and the top that remains is its nearest greater. Every index is pushed and popped at most once.
  6. How do you break ties in contribution counting? Make the comparison non-strict on one side and strict on the other, so each object has exactly one owner (for example, the leftmost maximum).
  7. How would you find a tie bug before submitting? Stress test against a brute force with a small value range so that equal values are frequent.

Glossary

Term Meaning
Div 1 The harder division of a Codeforces round, for higher-rated participants; problems usually combine several ideas
BFS Breadth-first search: explores a graph level by level from a start vertex using a queue
connected component (area) A maximal set of vertices that can all reach each other
online queries Queries that must be answered one at a time, before the next is known
offline queries Queries read in advance and answered in any convenient order, then printed in the original order
DSU / union-find A structure that keeps disjoint sets under merges: find gives a set's representative, unite merges two sets
union by size Attach the smaller set's tree under the larger one, keeping trees shallow
path halving While walking up in find, point each visited node to its grandparent; a form of path compression
α(n) The inverse Ackermann function; grows so slowly it is at most about 5 in practice
sweep Processing events (here streets and questions) in sorted order with a moving pointer
Kruskal reconstruction tree A tree built during Kruskal's algorithm where every merge becomes a new node holding the edge weight
binary lifting Jump tables up[x][j] = the 2^j-th ancestor, used to climb a tree in O(log n)
block / subarray A contiguous run of elements
imbalance Here: the maximum minus the minimum of a block
contribution technique Summing over elements "value × how many objects it is responsible for" instead of over the objects
monotonic stack A stack whose values stay sorted; used to find the nearest greater or smaller element of every position
nearest greater element For position i, the closest index on one side with a larger value
tie-break A rule that decides which of several equal candidates owns an object
stress test Comparing a fast solution with a slow, trusted one on many random small inputs
referee The slow, obviously correct solution used in a stress test
long long A 64-bit signed integer in C++, up to about 9.2·10^18
Wrong Answer (WA) The verdict when the program's output differs from the expected output
Time Limit Exceeded (TLE) The verdict when the program runs longer than the time limit

Summary

  • A, Night Walks: as k grows the usable streets only grow, so areas only merge. Answer the questions offline in order of k, open streets with a pointer, let a DSU with sizes count each area, and store every answer at its original index. O((m + q) log) for the sorts, near-constant per DSU operation.
  • B, Skyline Imbalance: Σ (max − min) = Σ max + Σ max of −h. Each building is the max of (i − L) · (R − i) blocks; a monotonic stack finds L and R in O(n). Break ties with ≥ on one side and > on the other.
  • In both problems the samples passed with a bug inside. The stress test (repeated k values, few distinct heights) is what made them safe to submit.
  • Next episode, the last of the course: the road from Pupil to Expert and beyond, a practice plan.

Solutions in C++, Java and Python

Problem A · Night Walks

C++

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

struct DSU {                                        // union by size
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> st(m);                    // {darkness, u, v}
    for (auto& [d, u, v] : st) cin >> u >> v >> d;
    vector<array<int, 3>> qs(q);                    // {k, v, index}
    for (int i = 0; i < q; i++) { cin >> qs[i][1] >> qs[i][0]; qs[i][2] = i; }
    sort(st.begin(), st.end());                     // streets by darkness
    sort(qs.begin(), qs.end());                     // questions by k: OFFLINE
    DSU dsu(n);
    vector<int> ans(q);
    int j = 0;
    for (auto [k, v, i] : qs) {
        while (j < m && st[j][0] <= k) { dsu.unite(st[j][1], st[j][2]); j++; }   // light every street <= k
        ans[i] = dsu.sz[dsu.find(v)];               // store at the ORIGINAL index
    }
    for (int x : ans) cout << x << "\n";
}

Java

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

public class Main {
    static int[] p, sz;

    static int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }

    static void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
        p[b] = a;
        sz[a] += sz[b];
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = next(in), m = next(in), q = next(in);
        int[][] st = new int[m][];
        for (int i = 0; i < m; i++) { int u = next(in), v = next(in), d = next(in); st[i] = new int[]{d, u, v}; }
        int[][] qs = new int[q][];
        for (int i = 0; i < q; i++) { int v = next(in), k = next(in); qs[i] = new int[]{k, v, i}; }
        Arrays.sort(st, (x, y) -> Integer.compare(x[0], y[0]));     // streets by darkness
        Arrays.sort(qs, (x, y) -> Integer.compare(x[0], y[0]));     // questions by k: offline
        p = new int[n + 1]; sz = new int[n + 1];
        for (int i = 0; i <= n; i++) { p[i] = i; sz[i] = 1; }
        int[] ans = new int[q];
        int j = 0;
        for (int[] qu : qs) {
            while (j < m && st[j][0] <= qu[0]) { unite(st[j][1], st[j][2]); j++; }
            ans[qu[2]] = sz[find(qu[1])];                            // store at the original index
        }
        StringBuilder sb = new StringBuilder();
        for (int x : ans) sb.append(x).append('\n');
        System.out.print(sb);
    }

    static int next(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

def main():
    data = sys.stdin.buffer.read().split()
    n, m, q = int(data[0]), int(data[1]), int(data[2])
    pos = 3
    st = []
    for _ in range(m):
        u, v, d = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]); pos += 3
        st.append((d, u, v))
    qs = []
    for i in range(q):
        v, k = int(data[pos]), int(data[pos + 1]); pos += 2
        qs.append((k, v, i))
    st.sort()                                 # streets by darkness
    qs.sort()                                 # questions by k: offline
    p = list(range(n + 1))
    sz = [1] * (n + 1)

    def find(x):
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x

    ans = [0] * q
    j = 0
    for k, v, i in qs:
        while j < m and st[j][0] <= k:
            a, b = find(st[j][1]), find(st[j][2])
            if a != b:
                if sz[a] < sz[b]:
                    a, b = b, a
                p[b] = a
                sz[a] += sz[b]
            j += 1
        ans[i] = sz[find(v)]                  # store at the original index
    sys.stdout.write("\n".join(map(str, ans)) + "\n")

main()

All three print 2 4 1 5 on the sample, and they agreed with the BFS referee on 150 random towns.

Problem B · Skyline Imbalance

C++

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

ll wins(vector<ll> h) {                             // sum over subarrays of the max
    int n = h.size();
    vector<int> L(n), R(n);
    stack<int> s;
    for (int i = 0; i < n; i++) {                   // nearest taller OR EQUAL on the left
        while (!s.empty() && h[s.top()] < h[i]) s.pop();
        L[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for (int i = n - 1; i >= 0; i--) {              // nearest strictly taller on the right
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();
        R[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += h[i] * (i - L[i]) * (R[i] - i);   // i is the max of this many
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> h(n);
    for (ll& x : h) cin >> x;
    ll mx = wins(h);
    for (ll& x : h) x = -x;                         // the min of h is minus the max of -h
    ll mn = -wins(h);
    cout << mx - mn << "\n";
}

Java

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

public class Main {
    // sum over all blocks of the maximum: building i wins (i - L) * (R - i) blocks
    static long wins(long[] h) {
        int n = h.length;
        int[] L = new int[n], R = new int[n], s = new int[n];
        int top = 0;
        for (int i = 0; i < n; i++) {                       // nearest taller OR EQUAL on the left
            while (top > 0 && h[s[top - 1]] < h[i]) top--;
            L[i] = top == 0 ? -1 : s[top - 1];
            s[top++] = i;
        }
        top = 0;
        for (int i = n - 1; i >= 0; i--) {                  // nearest strictly taller on the right
            while (top > 0 && h[s[top - 1]] <= h[i]) top--;
            R[i] = top == 0 ? n : s[top - 1];
            s[top++] = i;
        }
        long sum = 0;
        for (int i = 0; i < n; i++) sum += h[i] * (long) (i - L[i]) * (R[i] - i);
        return sum;
    }

    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[] h = new long[n];
        for (int i = 0; i < n; i++) { st.nextToken(); h[i] = (long) st.nval; }
        long mx = wins(h);
        for (int i = 0; i < n; i++) h[i] = -h[i];           // the min of h is minus the max of -h
        long mn = -wins(h);
        System.out.println(mx - mn);
    }
}

Python

import sys

def wins(h):
    """Sum over all blocks of the maximum: building i wins (i - L) * (R - i) blocks."""
    n = len(h)
    L, R, s = [0] * n, [0] * n, []
    for i in range(n):                        # nearest taller OR EQUAL on the left
        while s and h[s[-1]] < h[i]:
            s.pop()
        L[i] = s[-1] if s else -1
        s.append(i)
    s = []
    for i in range(n - 1, -1, -1):            # nearest strictly taller on the right
        while s and h[s[-1]] <= h[i]:
            s.pop()
        R[i] = s[-1] if s else n
        s.append(i)
    return sum(h[i] * (i - L[i]) * (R[i] - i) for i in range(n))

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    h = list(map(int, data[1:1 + n]))
    print(wins(h) + wins([-x for x in h]))   # sum of max minus sum of min

main()

All three print 5 on 3 1 2, 6 on 1 1 1 3 and 0 on a single building, and they agreed with the O(n²) brute force on 150 random skylines (Python ints never overflow; in Java the counts are multiplied as long).