These are the notes for Competitive Programming episode 87. No new algorithm this time: a whole contest. Three original problems, written for this course in the style of a Div 2 round, solved the way you would solve them with the clock running: read the statement fully, write a slow but sure brute force, find the observation, prove it, stress test the fast idea against the brute force, and only then submit. A · Tea Top-Up looks like a simulation and is really an invariant (the remainder mod k). B · Prefix Lamps is a greedy from the right whose first version passes every sample and is still Wrong Answer: the stress test finds it on a one-lamp row. C · Ribbon Cuts counts segments with a sum divisible by m using prefix remainders, and falls into C++'s negative remainder trap (-7 % 3 is -1) and needs long long for an answer near 2.9 billion. 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. Timings are given as the compiler showed them in kind ("a blink", "seconds"), since they depend on the machine.
The real-life hook
A tea stall: n cups, each with some tea, and a jug that pours exactly k ml at a time. Can every cup end up with the same amount? Pouring into the emptiest cup again and again works on small cases, but it is slow and it can never prove a NO.
The picture that solves it is a 12-hour clock. Add 12 hours and the clock shows exactly the same time; 3 o'clock stays 3 o'clock. Pouring k ml is the same: the remainder of a cup's amount divided by k never changes. Two clocks showing 3 and 5 never agree by adding 12s. Two clocks showing the same time can both be wound up to the latest one.
The same clock comes back in problem C, read with m hours: two prefix sums that show the same time on an m-hour clock are exactly the ends of a segment whose sum is divisible by m.
How to attack a round
- A Div 2 round lasts 2 hours; problems A, B, C, ... get harder and most people solve them in order.
- Read the problem fully: statement, constraints, samples. Most early mistakes are reading mistakes.
- The constraints tell you the complexity you need: n ≤ 2·10^5 means O(n) or O(n log n); 2·10^10 steps is far too many for a 2-second limit.
- Every wrong submission adds a penalty (on many judges, 10 minutes or a few points), so test before you submit.
- Our loop for every problem: brute force → observation → proof → stress test → submit.
- The brute force is slow but sure: it is the referee for the fast idea.
| Problem | Brute force (referee) | Observation | Fast solution |
|---|---|---|---|
| A · Tea Top-Up | simulate pours | a[i] mod k never changes | O(n): compare remainders |
| B · Prefix Lamps | BFS over all 2^n rows | only the longest flips touch the far end | O(n): count the changes |
| C · Ribbon Cuts | every segment, O(n²) | sum(l+1..r) = p[r] − p[l] | O(n log n): count equal remainders |
Problem A · Tea Top-Up
t tests. A tea stall has n cups (1 ≤ n ≤ 2·10^5 in total), cup i holds a[i] ml (1 ≤ a[i] ≤ 10^9). One move: pour exactly k ml (1 ≤ k ≤ 10^9) into any cup. You may make any number of moves, but you can only add tea. Can all cups end with the same amount? Print YES or NO.
Sample input
3
3 5
2 12 7
2 3
1 5
1 100
42
Sample output
YES
NO
YES
Test 1: pour twice into the first cup (2 + 5 + 5 = 12) and once into the third (7 + 5 = 12): all hold 12. Test 2: with k = 3, cups 1 and 5 never meet. Test 3: a single cup is always equal to itself.
Attempt 1: simulate the pours
Keep pouring k into the emptiest cup until all cups are equal; if that hasn't happened after a million pours, give up and say NO.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool simulate(vector<ll> a, ll k) { // pour k into the emptiest cup until equal
for (int step = 0; step < 1000000; step++) {
auto [lo, hi] = minmax_element(a.begin(), a.end());
if (*lo == *hi) return true;
*lo += k;
}
return false; // gave up: probably never equal
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
ll k;
cin >> n >> k;
vector<ll> a(n);
for (ll& x : a) cin >> x;
cout << (simulate(a, k) ? "YES" : "NO") << "\n";
}
}
On the sample:
YES
NO
YES
All three samples pass. Now two cups, 1 and 1000000000, with k = 1 (input 1 / 2 1 / 1 1000000000):
NO
That is wrong: pouring 1 ml at a time into the first cup, they do meet, after 999999999 pours. The simulation gave up too early. Raise the limit and it becomes Time Limit Exceeded instead. A simulation with a step limit is either wrong or slow; and it can never prove a NO.
The invariant
An invariant is something that never changes, whatever moves you make.
- Pouring k ml changes a[i] to a[i] + k, and (a[i] + k) mod k = a[i] mod k. The remainder of every cup mod k never changes.
- If two cups have different remainders, they can never hold the same amount (equal amounts have equal remainders). Answer NO.
- If all remainders are equal, let M be the fullest cup. For every cup, M − a[i] is a multiple of k (same remainder) and ≥ 0, so pour (M − a[i]) / k times into it. All cups hold M. Answer YES.
That is a proof in both directions, so the check is exact: YES iff all a[i] mod k are equal.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool same_rest(vector<ll>& a, ll k) { // adding k never changes a[i] % k
for (ll x : a)
if (x % k != a[0] % k) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
ll k;
cin >> n >> k;
vector<ll> a(n);
for (ll& x : a) cin >> x;
cout << (same_rest(a, k) ? "YES" : "NO") << "\n";
}
}
On the sample:
YES
NO
YES
On the case that fooled the simulation (1 / 2 1 / 1 1000000000):
YES
Instantly.
Stress test against the simulation
On tiny cups (values 1..20, k ≤ 5) the simulation always finishes on a YES within its million pours, so there it is a correct referee:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool simulate(vector<ll> a, ll k) { // pour k into the emptiest cup until equal
for (int step = 0; step < 1000000; step++) {
auto [lo, hi] = minmax_element(a.begin(), a.end());
if (*lo == *hi) return true;
*lo += k;
}
return false; // gave up: probably never equal
}
bool same_rest(vector<ll>& a, ll k) { // adding k never changes a[i] % k
for (ll x : a)
if (x % k != a[0] % k) return false;
return true;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 2000; it++) {
int n = gen() % 4 + 1;
ll k = gen() % 5 + 1;
vector<ll> a(n);
for (ll& x : a) x = gen() % 20 + 1;
if (simulate(a, k) != same_rest(a, k)) { cout << "differs on test " << it; return 0; }
}
cout << "all 2000 tests agree";
}
all 2000 tests agree
(This takes a moment: every NO test runs the full million pours.) Submit. O(n) per test, O(1) extra memory.
Problem B · Prefix Lamps
t tests. A row of n lamps along a corridor (sum of n ≤ 2·10^5), given as a string s: s[i] =
1if lamp i is on. One move: pick i and flip lamps 1..i (on ↔ off). Print the fewest moves that switch every lamp off.
Sample input
3
4
1100
5
10110
3
000
Sample output
1
3
0
1100: flip lamps 1..2, done. 10110 needs 3. 000 needs nothing.
The referee: BFS over all rows
Treat each row of lamps as a state (a bitmask of n bits). A move goes from one state to another; the fewest moves is a shortest path, found by breadth-first search (BFS) over all 2^n states. Fine for n ≤ 10, hopeless for 2·10^5, perfect as a referee.
The observation: work from the far end
Take 10110.
- Lamp 5 is off: no flip needs to touch it.
- Lamp 4 is on, and only flips that reach lamp 4 can fix it. Once lamps 4 and 5 are right, nothing we do later needs to touch them. Flip 1..4:
01000. - Now lamps 3, 4, 5 are off and lamp 2 is on: flip 1..2:
10000. - Lamp 1 is on: flip 1..1:
00000. Three flips.
Going right to left, we flip exactly where a lamp differs from the one on its right (each earlier flip flipped both, so their "difference" is what decides). Put an imaginary off lamp after the last one, and the answer is the number of neighbours that differ.
Why it is the minimum: one prefix flip 1..i changes only one neighbour pair, (i, i+1); every other pair is either flipped on both sides or untouched. All lamps off (with the extra off lamp) means zero differing pairs. So each move removes at most one difference, and the greedy removes exactly one per move: it is optimal.
The hidden Wrong Answer
My first submission counted the differing neighbours inside the string:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int greedy(string s) { // count neighbours that differ
int ops = 0;
for (int i = 0; i + 1 < (int)s.size(); i++)
if (s[i] != s[i + 1]) ops++;
return ops;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
cout << greedy(s) << "\n";
}
}
On the sample:
1
3
0
All three samples pass. In a contest, this is the moment people click submit. The stress test against the BFS first:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int bfs(string s) { // fewest prefix flips, by trying everything
int n = s.size(), start = 0;
for (int i = 0; i < n; i++) if (s[i] == '1') start |= 1 << i;
vector<int> dist(1 << n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int m = q.front();
q.pop();
for (int i = 1; i <= n; i++) { // flip lamps 1..i
int nm = m ^ ((1 << i) - 1);
if (dist[nm] == -1) { dist[nm] = dist[m] + 1; q.push(nm); }
}
}
return dist[0];
}
int greedy(string s) { // count neighbours that differ
int ops = 0;
for (int i = 0; i + 1 < (int)s.size(); i++)
if (s[i] != s[i + 1]) ops++;
return ops;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 1000; it++) {
int n = gen() % 10 + 1;
string s(n, '0');
for (char& c : s) c = '0' + gen() % 2;
if (bfs(s) != greedy(s)) {
cout << "differs on " << s << ": bfs " << bfs(s) << ", greedy " << greedy(s);
return 0;
}
}
cout << "all 1000 tests agree";
}
differs on 1: bfs 1, greedy 0
The simplest row of all: a single lamp that is on. The greedy forgot the imaginary off lamp after the last one, so a lit last lamp is never counted. Samples passing is not proof.
The fix: one line
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int bfs(string s) { // fewest prefix flips, by trying everything
int n = s.size(), start = 0;
for (int i = 0; i < n; i++) if (s[i] == '1') start |= 1 << i;
vector<int> dist(1 << n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int m = q.front();
q.pop();
for (int i = 1; i <= n; i++) { // flip lamps 1..i
int nm = m ^ ((1 << i) - 1);
if (dist[nm] == -1) { dist[nm] = dist[m] + 1; q.push(nm); }
}
}
return dist[0];
}
int greedy(string s) { // count neighbours that differ
s += '0'; // the lamp after the last one is off
int ops = 0;
for (int i = 0; i + 1 < (int)s.size(); i++)
if (s[i] != s[i + 1]) ops++;
return ops;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 1000; it++) {
int n = gen() % 10 + 1;
string s(n, '0');
for (char& c : s) c = '0' + gen() % 2;
if (bfs(s) != greedy(s)) {
cout << "differs on " << s << ": bfs " << bfs(s) << ", greedy " << greedy(s);
return 0;
}
}
cout << "all 1000 tests agree";
}
all 1000 tests agree
The real program:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int greedy(string s) { // count neighbours that differ
s += '0'; // the lamp after the last one is off
int ops = 0;
for (int i = 0; i + 1 < (int)s.size(); i++)
if (s[i] != s[i + 1]) ops++;
return ops;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
cout << greedy(s) << "\n";
}
}
On the sample:
1
3
0
On the single lit lamp (1 / 1 / 1):
1
Submit. O(n) per test.
Problem C · Ribbon Cuts
A ribbon of n pieces (1 ≤ n ≤ 2·10^5) with values a[i], −10^9 ≤ a[i] ≤ 10^9, and an integer m (1 ≤ m ≤ 10^9). Count the segments [l, r] (1 ≤ l ≤ r ≤ n) whose sum is divisible by m.
Sample input
5 3
-1 3 2 -1 4
Sample output
3
The three segments: [3], [-1 3 2 -1] (sum 3) and [-1 4] (sum 3).
Note the size of the answer: up to n(n+1)/2 ≈ 2·10^10 segments, which does not fit in an int (at most 2147483647). The count must be a long long.
Brute force: every segment
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll m;
cin >> n >> m;
vector<ll> a(n);
for (ll& x : a) cin >> x;
ll ways = 0;
for (int l = 0; l < n; l++) {
ll sum = 0;
for (int r = l; r < n; r++) { // every segment [l, r]
sum += a[r];
if (sum % m == 0) ways++;
}
}
cout << ways << "\n";
}
On the sample:
3
With only half the maximum length, 100000 random pieces made inside the program:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(87);
int n = 100000; // only HALF the limit
ll m = 7;
vector<ll> a(n);
for (ll& x : a) x = (ll)(gen() % 2000000001) - 1000000000;
ll ways = 0;
for (int l = 0; l < n; l++) {
ll sum = 0;
for (int r = l; r < n; r++) { // every segment [l, r]
sum += a[r];
if (sum % m == 0) ways++;
}
}
cout << ways << "\n";
}
714287109
It takes seconds at half the size: about n²/2 = 5·10^9 additions. At the full 2·10^5 it is four times worse. Time Limit Exceeded.
The observation: prefix remainders
Let p[0] = 0 and p[r] = a[1] + ... + a[r] (the prefix sums). The segment l+1..r sums to p[r] − p[l], and
p[r] − p[l] is divisible by m ⇔ p[r] mod m = p[l] mod m.
So read every prefix sum on an m-hour clock and count the pairs of equal remainders.
| p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | |
|---|---|---|---|---|---|---|
| piece | −1 | 3 | 2 | −1 | 4 | |
| prefix sum | 0 | −1 | 2 | 4 | 3 | 7 |
| mod 3 | 0 | 2 | 2 | 1 | 0 | 1 |
Pairs: (0, 4) → pieces 1..4 = -1 3 2 -1; (1, 2) → piece 2 = 3; (3, 5) → pieces 4..5 = -1 4. Three pairs, three segments.
Counting pairs is one pass: keep a map from remainder to how many prefixes had it so far, starting with the empty prefix (remainder 0). Each new prefix pairs with every earlier prefix with the same remainder.
The negative remainder trap
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll m;
cin >> n >> m;
vector<ll> a(n);
for (ll& x : a) cin >> x;
map<ll, ll> seen; // remainder -> how many prefixes had it
seen[0] = 1; // the empty prefix
ll p = 0, ways = 0;
for (ll x : a) {
p = (p + x) % m;
ways += seen[p]; // pair with every earlier equal remainder
seen[p]++;
}
cout << ways << "\n";
}
On the sample:
2
The answer is 3. Ask C++ directly:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cout << 7 % 3 << " " << -7 % 3 << " " << ((-7 % 3) + 3) % 3 << "\n";
}
1 -1 2
7 % 3 is 1, but -7 % 3 is −1, not 2: in C++ (and Java) the remainder takes the sign of the left side. So the prefix −1 got key −1 while the prefix 2 got key 2: the same position on the clock, two different keys in the map, and the pair (1, 2) was lost.
The fix: add m and take the remainder again, so the key is always in [0, m):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll m;
cin >> n >> m;
vector<ll> a(n);
for (ll& x : a) cin >> x;
map<ll, ll> seen; // remainder -> how many prefixes had it
seen[0] = 1; // the empty prefix
ll p = 0, ways = 0;
for (ll x : a) {
p = ((p + x) % m + m) % m; // always in [0, m)
ways += seen[p]; // pair with every earlier equal remainder
seen[p]++;
}
cout << ways << "\n";
}
On the sample:
3
Stress test, with negatives in every test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll slow(vector<ll>& a, ll m) {
ll ways = 0;
for (int l = 0; l < (int)a.size(); l++) {
ll sum = 0;
for (int r = l; r < (int)a.size(); r++) { sum += a[r]; ways += sum % m == 0; }
}
return ways;
}
ll fast(vector<ll>& a, ll m) {
map<ll, ll> seen;
seen[0] = 1;
ll p = 0, ways = 0;
for (ll x : a) { p = ((p + x) % m + m) % m; ways += seen[p]; seen[p]++; }
return ways;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 2000; it++) {
int n = gen() % 10 + 1;
ll m = gen() % 6 + 1;
vector<ll> a(n);
for (ll& x : a) x = (ll)(gen() % 21) - 10; // negatives too
if (slow(a, m) != fast(a, m)) { cout << "differs on test " << it; return 0; }
}
cout << "all 2000 tests agree";
}
all 2000 tests agree
And the full size, 2·10^5 pieces:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(87);
int n = 200000; // the largest test
ll m = 7;
vector<ll> a(n);
for (ll& x : a) x = (ll)(gen() % 2000000001) - 1000000000;
map<ll, ll> seen; // remainder -> how many prefixes had it
seen[0] = 1; // the empty prefix
ll p = 0, ways = 0;
for (ll x : a) {
p = ((p + x) % m + m) % m; // always in [0, m)
ways += seen[p]; // pair with every earlier equal remainder
seen[p]++;
}
cout << ways << "\n";
}
2857194450
In a blink. 2857194450 is bigger than an int can hold (2147483647), which is why ways is a long long. Submit. O(n log n) with map (an unordered_map with a safe hash, from episode 85, makes it expected O(n)).
Complexity vs the constraints
n = 2·10^5, time limit 2 s (about 10^8 to 10^9 simple steps).
| Problem | Method | Work | Verdict |
|---|---|---|---|
| A | simulate pours | up to 10^9 pours | WA (gave up) or TLE |
| A | compare remainders | O(n) | Accepted |
| B | BFS over rows | O(2^n · n) | referee only |
| B | count changes | O(n) | Accepted |
| C | every segment | O(n²) ≈ 2·10^10 | TLE |
| C | prefix remainders + map | O(n log n) | Accepted |
Memory: A and B O(1) extra (B copies the string once), C O(n) for the map.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| simulate with a step limit (A) | NO on 2 1 / 1 1000000000 |
the true answer needs 999999999 pours | find the invariant |
| trusting the samples (B) | samples pass; stress test: differs on 1: bfs 1, greedy 0 |
samples miss edge cases | stress test against a brute force |
| forgetting the lamp after the last one (B) | 0 for the row 1 |
the last pair is never counted | s += '0' |
(p + x) % m with negatives (C) |
2 instead of 3 on the sample; -7 % 3 prints -1 |
C++ keeps the sign of the left side | ((p + x) % m + m) % m |
| forgetting the empty prefix (C) | segments starting at piece 1 are lost | p[0] = 0 is a prefix too | seen[0] = 1 |
int ways (C) |
overflow on the big test (true answer 2857194450) | the answer can reach about 2·10^10 | long long |
| submitting the brute force (C) | TLE: seconds already at n = 10^5 | O(n²) | prefix remainders |
Mini project: a reusable stress runner
The stress tests in the video put the brute force and the fast solution in one file. In a contest it is often quicker to keep two separate programs (the brute force you already wrote, and the solution you want to submit) and a small script that feeds both the same random tests and stops at the first difference, printing the input. This one is written for problem C; only gen changes from problem to problem.
# stress.py: run a slow, sure program and a fast one on many random tests; stop at the first difference.
# python3 stress.py ./brute ./fast [tests]
import random, subprocess, sys
def gen(rng): # a random test for problem C (Ribbon Cuts)
n, m = rng.randint(1, 8), rng.randint(1, 6)
a = [rng.randint(-10, 10) for _ in range(n)]
return f"{n} {m}\n{' '.join(map(str, a))}\n"
def run(exe, test):
return subprocess.run([exe], input=test, capture_output=True, text=True, timeout=5).stdout.strip()
brute, fast = sys.argv[1], sys.argv[2]
tests = int(sys.argv[3]) if len(sys.argv) > 3 else 500
rng = random.Random(87)
for it in range(1, tests + 1):
test = gen(rng)
want, got = run(brute, test), run(fast, test)
if want != got:
print(f"test {it} differs\n--- input ---\n{test}--- brute: {want} fast: {got}")
sys.exit(1)
print(f"all {tests} tests agree")
Compile the brute force and the first (negative-remainder) version of C, then run it:
$ python3 stress.py ./brute ./c_bad
test 2 differs
--- input ---
5 3
10 7 0 -7 1
--- brute: 4 fast: 1
It found the bug on the second random test, and handed us a small input to debug by hand. With the fixed version:
$ python3 stress.py ./brute ./c_ok 300
all 300 tests agree
Ideas to extend it: take the generator as a third program (./gen SEED), add a time limit per run to catch infinite loops, and shrink a failing test automatically (try deleting elements while it still fails).
Practice
These are the homework problems from the episode, written for this course. Each solution comes with a stress test; all outputs are real.
1. A': you may also pour k OUT of a cup (a cup can never go below 0). Does the answer change?
Solution
No. Pouring out also keeps a[i] mod k unchanged, so different remainders are still NO; and equal remainders were already YES using only pours in. The referee below is a BFS over all cup states (amounts kept in [0, 60] for the search, plenty for values below 20).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// A': a move may also pour k OUT of a cup (a cup can never go below 0).
// BFS over all reachable cup states with small bounds is the referee.
bool brute(vector<int> a, int k) {
const int CAP = 60; // amounts stay in [0, CAP] for the search
set<vector<int>> seen{a};
queue<vector<int>> q;
q.push(a);
while (!q.empty()) {
auto v = q.front();
q.pop();
if (count(v.begin(), v.end(), v[0]) == (int)v.size()) return true;
for (int i = 0; i < (int)v.size(); i++)
for (int d : {k, -k}) {
auto w = v;
w[i] += d;
if (w[i] < 0 || w[i] > CAP || seen.count(w)) continue;
seen.insert(w);
q.push(w);
}
}
return false;
}
bool fast(vector<int>& a, int k) { // same rule as problem A
for (int x : a) if (x % k != a[0] % k) return false;
return true;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 500; it++) {
int n = gen() % 3 + 1, k = gen() % 5 + 1;
vector<int> a(n);
for (int& x : a) x = gen() % 20;
if (brute(a, k) != fast(a, k)) { cout << "differs on test " << it; return 0; }
}
cout << "all 500 tests agree";
}
all 500 tests agree
2. B': the flips are suffixes (flip lamps i..n) instead of prefixes.
Solution
The mirror image of B: put an imaginary off lamp before the first one and count differing neighbours. A suffix flip i..n changes only the pair (i−1, i). The check is in the program under question 3.
3. B'': you may flip ANY segment l..r. Fewest flips?
Solution
The number of blocks of consecutive 1s. Each block can be switched off with one flip, so that many is enough. Why not fewer: with off lamps added at both ends, the number of differing neighbour pairs is 2 × (number of blocks), and one segment flip changes only the two pairs at its ends, so it removes at most one block.
Both answers, checked against a BFS that tries every allowed flip:
#include <bits/stdc++.h>
using namespace std;
// B': a move flips a SUFFIX i..n. B'': a move flips ANY segment l..r.
int bfs(string s, bool anySegment) {
int n = s.size(), start = 0;
for (int i = 0; i < n; i++) if (s[i] == '1') start |= 1 << i;
vector<int> dist(1 << n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int m = q.front();
q.pop();
for (int l = 0; l < n; l++)
for (int r = l; r < n; r++) {
if (!anySegment && r != n - 1) continue; // suffixes only
int nm = m ^ (((1 << (r + 1)) - 1) ^ ((1 << l) - 1));
if (dist[nm] == -1) { dist[nm] = dist[m] + 1; q.push(nm); }
}
}
return dist[0];
}
int suffixFlips(string s) { // mirror of problem B
s = "0" + s; // the lamp BEFORE the first one is off
int ops = 0;
for (int i = 0; i + 1 < (int)s.size(); i++) if (s[i] != s[i + 1]) ops++;
return ops;
}
int segmentFlips(string s) { // one flip per block of 1s
int blocks = 0;
for (int i = 0; i < (int)s.size(); i++)
if (s[i] == '1' && (i == 0 || s[i - 1] == '0')) blocks++;
return blocks;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 1000; it++) {
int n = gen() % 10 + 1;
string s(n, '0');
for (char& c : s) c = '0' + gen() % 2;
if (bfs(s, false) != suffixFlips(s)) { cout << "suffix differs on " << s; return 0; }
if (bfs(s, true) != segmentFlips(s)) { cout << "segment differs on " << s; return 0; }
}
cout << "all 1000 tests agree (suffixes and segments)";
}
all 1000 tests agree (suffixes and segments)
4. C': count segments with sum divisible by m AND length ≥ 2.
Solution
Count all divisible segments as before, then subtract the segments of length 1, which are exactly the pieces with a[i] mod m = 0. (Equivalently: insert each prefix into the map one step late.) On the sample, the single piece 3 is removed: 3 − 1 = 2.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// C': count segments with sum divisible by m AND length >= 2.
ll slow(vector<ll>& a, ll m) {
ll ways = 0;
for (int l = 0; l < (int)a.size(); l++) {
ll sum = 0;
for (int r = l; r < (int)a.size(); r++) { sum += a[r]; if (r > l && sum % m == 0) ways++; }
}
return ways;
}
ll fast(vector<ll>& a, ll m) {
map<ll, ll> seen;
seen[0] = 1;
ll p = 0, ways = 0, single = 0;
for (ll x : a) {
p = ((p + x) % m + m) % m;
ways += seen[p];
seen[p]++;
if (x % m == 0) single++; // the length-1 segments that were counted
}
return ways - single;
}
int main() {
mt19937 gen(87);
for (int it = 1; it <= 2000; it++) {
int n = gen() % 10 + 1;
ll m = gen() % 6 + 1;
vector<ll> a(n);
for (ll& x : a) x = (ll)(gen() % 21) - 10;
if (slow(a, m) != fast(a, m)) { cout << "differs on test " << it; return 0; }
}
vector<ll> s = {-1, 3, 2, -1, 4};
cout << "all 2000 tests agree; sample answer " << fast(s, 3);
}
all 2000 tests agree; sample answer 2
Quick quiz
// lamps: 0110110
// flip 1..i, fewest flips to switch all off?
A) 3 · B) 4 · C) 5 · D) 6
Answer
B. Add an off lamp at the end: 01101100. Neighbours differ at four places (0|1, 1|0, 0|1, 1|0), so 4 flips.
Interview questions
- What is an invariant, and how do you use one? A quantity that no move can change. If the start and the goal have different values of it, the goal is unreachable; here a[i] mod k.
- Why is a simulation with a step limit dangerous? When it gives up it answers NO without proof; on a big input the true answer may need more steps (problem A: 999999999 pours).
- How do you prove a greedy is optimal? Find a lower bound every solution must pay (each prefix flip removes at most one differing pair) and show the greedy meets it.
- Why write a brute force if it is too slow to submit? It is a referee: run it against the fast solution on thousands of small random tests (a stress test) to find bugs before the judge does.
- The samples pass. Is the solution correct? Not necessarily; problem B passed all three samples and failed on the one-lamp row
1. - How do you count subarrays with sum divisible by m? Prefix sums mod m; a pair of equal remainders is one such subarray; count pairs with a hash map, starting with remainder 0 for the empty prefix.
- What is
-7 % 3in C++, Java and Python? −1 in C++ and Java (the sign follows the dividend), 2 in Python. In C++ write((x % m) + m) % m. - When must a count be
long long? Whenever it can exceed 2147483647: the number of segments of an array of 2·10^5 can reach about 2·10^10. - How do you turn constraints into a target complexity? About 10^8 to 10^9 simple steps per 2 seconds: n = 2·10^5 allows O(n log n), not O(n²).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Div 2 round | A contest for lower-rated contestants, about 2 hours, problems A, B, C, ... | today's round |
| Verdict | The judge's result for a submission | Accepted, WA, TLE |
| Accepted | Correct on every test within the limits | A after the fix |
| Wrong Answer (WA) | The output differs on some test | B without the last lamp |
| Time Limit Exceeded (TLE) | The program runs too long | C's brute force |
| Penalty | Extra cost for each wrong submission | 10 minutes on many judges |
| Constraints | The limits on the input sizes and values | n ≤ 2·10^5 |
| Sample | The example tests in the statement | 1100 → 1 |
| Brute force | The simplest correct solution, usually slow | every segment |
| Referee | A brute force used to check the fast solution | the BFS in B |
| Stress test | Many random small tests comparing two solutions | all 1000 tests agree |
| Simulation | Doing the moves one by one | pour into the emptiest cup |
| Invariant | Something no move can change | a[i] mod k |
| Remainder (mod) | What is left after division | 12 mod 5 = 2 |
| Greedy | Make the locally best choice at each step | flip at every change from the right |
| Lower bound | An amount every solution must pay | one flip per differing pair |
| BFS | Breadth-first search: shortest paths by layers | fewest flips over 2^n rows |
| State | One configuration in a search | a row of lamps as a bitmask |
| Bitmask | An integer whose bits store yes/no values | lamp i on ↔ bit i set |
| Prefix | The first i elements | lamps 1..i |
| Suffix | The last elements, from i to n | lamps i..n |
| Segment (subarray) | Consecutive elements l..r | [-1 4] |
| Prefix sum | p[r] = a[1] + ... + a[r] | 0, −1, 2, 4, 3, 7 |
| Empty prefix | p[0] = 0, the sum of no elements | seen[0] = 1 |
| Negative modulo | In C++ the remainder has the sign of the left side | -7 % 3 == -1 |
map |
A sorted key → value container, O(log n) per access | remainder → count |
| Overflow | A value too big for its type wraps around | int max 2147483647 |
long long |
A 64-bit integer, up to about 9.2·10^18 | ll ways |
minmax_element |
Returns iterators to the smallest and largest element | the emptiest cup |
mt19937 |
C++'s Mersenne Twister random generator | mt19937 gen(87) |
Summary
- A contest is a loop: read fully → brute force → observation → proof → stress test → submit. The brute force is the referee.
- A: pouring k never changes a[i] mod k (an invariant): YES iff all remainders are equal. O(n).
- B: from the right, flip wherever neighbours differ, with an off lamp after the last; each flip fixes at most one pair, so it is optimal. The samples passed without the extra lamp; the stress test caught it.
- C: segment sums are differences of prefix sums; divisible ⇔ equal prefix remainders. Count pairs with a map from the empty prefix. In C++ use
((p + x) % m + m) % m, and count in long long.
Solutions in C++, Java and Python
Every solution below was run on the samples; the outputs are real. Java was compiled with javac and run with java; Python with python3.
Problem A · Tea Top-Up
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool same_rest(vector<ll>& a, ll k) { // adding k never changes a[i] % k
for (ll x : a)
if (x % k != a[0] % k) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
ll k;
cin >> n >> k;
vector<ll> a(n);
for (ll& x : a) cin >> x;
cout << (same_rest(a, k) ? "YES" : "NO") << "\n";
}
}
Java
import java.util.*;
import java.io.*;
public class A {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int t = (int) st.nval;
StringBuilder out = new StringBuilder();
while (t-- > 0) {
st.nextToken(); int n = (int) st.nval;
st.nextToken(); long k = (long) st.nval;
long first = -1; boolean ok = true;
for (int i = 0; i < n; i++) {
st.nextToken(); long x = (long) st.nval;
if (i == 0) first = x % k;
else if (x % k != first) ok = false;
}
out.append(ok ? "YES" : "NO").append('\n');
}
System.out.print(out);
}
}
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0]); pos = 1; out = []
for _ in range(t):
n, k = int(data[pos]), int(data[pos + 1]); pos += 2
a = data[pos:pos + n]; pos += n
rests = {int(x) % k for x in a} # adding k never changes x % k
out.append("YES" if len(rests) == 1 else "NO")
print("\n".join(out))
main()
Sample output (all three languages):
YES
NO
YES
Problem B · Prefix Lamps
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int greedy(string s) { // count neighbours that differ
s += '0'; // the lamp after the last one is off
int ops = 0;
for (int i = 0; i + 1 < (int)s.size(); i++)
if (s[i] != s[i + 1]) ops++;
return ops;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
cout << greedy(s) << "\n";
}
}
Java
import java.io.*;
import java.util.*;
public class B {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tk = new StringTokenizer("");
StringBuilder all = new StringBuilder();
String line;
while ((line = br.readLine()) != null) all.append(line).append(' ');
tk = new StringTokenizer(all.toString());
int t = Integer.parseInt(tk.nextToken());
StringBuilder out = new StringBuilder();
while (t-- > 0) {
int n = Integer.parseInt(tk.nextToken());
String s = tk.nextToken() + "0"; // the lamp after the last one is off
int ops = 0;
for (int i = 0; i + 1 < s.length(); i++)
if (s.charAt(i) != s.charAt(i + 1)) ops++;
out.append(ops).append('\n');
}
System.out.print(out);
}
}
Python
import sys
def main():
data = sys.stdin.read().split()
t = int(data[0]); pos = 1; out = []
for _ in range(t):
s = data[pos + 1] + "0" # the lamp after the last one is off
pos += 2
out.append(str(sum(s[i] != s[i + 1] for i in range(len(s) - 1))))
print("\n".join(out))
main()
Sample output (all three languages):
1
3
0
Problem C · Ribbon Cuts
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll m;
cin >> n >> m;
vector<ll> a(n);
for (ll& x : a) cin >> x;
map<ll, ll> seen; // remainder -> how many prefixes had it
seen[0] = 1; // the empty prefix
ll p = 0, ways = 0;
for (ll x : a) {
p = ((p + x) % m + m) % m; // always in [0, m)
ways += seen[p]; // pair with every earlier equal remainder
seen[p]++;
}
cout << ways << "\n";
}
Java (Java's % keeps the sign too, so the same fix is needed)
import java.io.*;
import java.util.*;
public class C {
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;
st.nextToken(); long m = (long) st.nval;
HashMap<Long, Long> seen = new HashMap<>();
seen.put(0L, 1L); // the empty prefix
long p = 0, ways = 0;
for (int i = 0; i < n; i++) {
st.nextToken(); long x = (long) st.nval;
p = ((p + x) % m + m) % m; // Java's % keeps the sign too
long c = seen.getOrDefault(p, 0L);
ways += c;
seen.put(p, c + 1);
}
System.out.println(ways);
}
}
Python (Python's % already returns a value in [0, m), and its integers never overflow)
import sys
from collections import defaultdict
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
seen = defaultdict(int)
seen[0] = 1 # the empty prefix
p = ways = 0
for x in data[2:2 + n]:
p = (p + int(x)) % m # Python's % is already in [0, m)
ways += seen[p]
seen[p] += 1
print(ways)
main()
Sample output (all three languages):
3