These are the notes for Competitive Programming episode 16. An original problem, Two Hands, asks whether a waiter who can only flip two neighbouring cups at once can turn every cup on his tray upright. No textbook algorithm fits: it is an ad-hoc problem. A brute force over every set of moves is correct but gets Time Limit Exceeded on just 40 cups. Instead of throwing it away, we print its answers for every tiny tray, spot a pattern (YES exactly when the number of upside-down cups is even), and prove it with an invariant, the way a chess bishop can never change colour. Then the O(n) solution, a stress test, the fewest-moves version, and three bugs with real outputs. 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.
The real-life hook: the waiter with two hands
A waiter at a chai stall holds a long tray of cups. Some are upright, some upside down. With the tray in his arms he can only use both hands together: one move flips two cups that sit side by side. Fixing one cup often turns its neighbour over. Can he ever get every cup upright, or is the tray hopeless?
The problem: Two Hands
Problem P · Two Hands (written for this course). A tray is a string
sofncharacters:1is an upright cup,0is upside down. In one move you picki(0 ≤ i < n − 1) and flip boths[i]ands[i + 1](0 ↔ 1). Can all cups become1, using any number of moves? PrintYESorNO.
1 ≤ t ≤ 10^4test cases,1 ≤ n ≤ 2·10^5, the sum ofnover all tests is at most2·10^5.
| Sample input | Sample output |
|---|---|
430104110111500000 |
YESNOYESNO |
"Sum of n ≤ 2·10^5" is the usual Codeforces way to allow many test cases: the total work over all tests must be about O(sum of n).
Brute force: every set of moves (Time Limit Exceeded)
Two facts make the search finite:
- Order doesn't matter. Each cup ends up flipped once for every move that touches it, whatever the order.
- Twice cancels. Doing the same move twice changes nothing.
So each of the n − 1 positions is used 0 or 1 times: there are 2^(n−1) sets of moves, and the bits of mask say which positions are used.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool brute(string s) {
int n = s.size();
for (ll mask = 0; mask < (1LL << (n - 1)); mask++) {
string t = s;
for (int i = 0; i + 1 < n; i++)
if (mask >> i & 1) {
t[i] ^= 1;
t[i + 1] ^= 1;
}
if (count(t.begin(), t.end(), '0') == 0) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
cout << (brute(s) ? "YES" : "NO") << "\n";
}
return 0;
}
Why does t[i] ^= 1 flip a cup? The character '0' is code 48 (binary 110000) and '1' is 49 (110001): they differ only in the last bit, so XOR with 1 swaps them.
| Input | Output |
|---|---|
| the sample | YES NO YES NO |
1 / 40 / thirty-nine 1s then 0 |
Time Limit Exceeded (2^39 sets × 40 steps ≈ 2·10^13) |
The method for ad-hoc problems
An ad-hoc problem (Latin ad hoc, "for this one thing") has no standard algorithm: no sorting, DP or graph template. It needs one observation about this exact problem. The method:
- Write a brute force that is slow but surely correct.
- Print its answers for every tiny input, in a table.
- Guess the pattern, then prove it.
- Code the fast rule and stress-test it against the brute force on random inputs.
Step 2: print the small answers
int main() {
int n = 3;
for (int m = 0; m < (1 << n); m++) {
string s;
for (int i = 0; i < n; i++) s += (m >> i & 1) ? '1' : '0';
int zeros = count(s.begin(), s.end(), '0');
cout << s << " zeros=" << zeros << " "
<< (brute(s) ? "YES" : "NO") << "\n";
}
return 0;
}
Real output (with the same brute above it):
000 zeros=3 NO
100 zeros=2 YES
010 zeros=2 YES
110 zeros=1 NO
001 zeros=2 YES
101 zeros=1 NO
011 zeros=1 NO
111 zeros=0 YES
The guess: YES exactly when the number of zeros is even. It also fits the sample (2 zeros → YES, 1 → NO, 0 → YES, 5 → NO).
Step 3: the proof, with an invariant
| On a chessboard | In our problem |
|---|---|
| A bishop moves diagonally | a move flips s[i] and s[i + 1] |
| It always stays on its colour | an invariant: something no move can change |
| A white-square bishop never reaches a black square | if the target has a different invariant value → impossible |
What does one move do to the number of zeros? The chosen pair can only be one of four things:
| Before | After | Zeros change |
|---|---|---|
0 0 |
1 1 |
−2 |
0 1 |
1 0 |
0 |
1 0 |
0 1 |
0 |
1 1 |
0 0 |
+2 |
The count always changes by an even number, so its parity (whether it is even or odd) never changes.
- Odd zeros → NO. The goal (all
1) has 0 zeros, which is even. Parity is invariant, so you can never get there. - Even zeros → YES (construction). Sweep
i = 0 … n − 2: whenevers[i] = '0', flip(i, i + 1). After the sweep, cups0 … n − 2are all1. Only the last cup can be0, but the number of zeros is still even, so it is 0: the last cup is1too. Example:010 → 100 → 111.
Conclusion: YES ⇔ the number of 0s is even. (The sweep is a constructive proof, the idea of episode 15.)
Step 4: the O(n) solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int zeros = count(s.begin(), s.end(), '0');
cout << (zeros % 2 == 0 ? "YES" : "NO") << "\n";
}
return 0;
}
| Input | Output | Why |
|---|---|---|
| the sample | YES NO YES NO |
2, 1, 0, 5 zeros |
3 / 1 0 / 2 00 / 6 011110 |
NO YES YES |
one cup has no neighbour; far-apart zeros still pair up |
40 cups, one 0 |
NO (instantly) |
1 zero, odd |
Stress test
bool fast(string s) {
return count(s.begin(), s.end(), '0') % 2 == 0;
}
int main() {
mt19937 rng(16);
for (int it = 1; it <= 1000; it++) {
int n = rng() % 12 + 1;
string s;
for (int i = 0; i < n; i++) s += char('0' + rng() % 2);
if (brute(s) != fast(s)) {
cout << "DIFF on " << s << "\n";
return 0;
}
}
cout << "OK: 1000 random tests agree\n";
return 0;
}
Real output: OK: 1000 random tests agree.
Part 2: the fewest flips
Variant: if it is possible, print the minimum number of moves, else -1.
- In a shortest plan no position is used twice (two uses cancel).
- Cup 0 is touched only by move 0, so cup 0 decides move 0. Then cup 1 is touched only by moves 0 and 1, so move 1 is forced too, and so on. There is exactly one valid set of moves.
- The left-to-right sweep finds that set, so its count is the minimum. Equivalently: pair the zeros 1st with 2nd, 3rd with 4th…, and add the gaps.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int ops = 0;
for (int i = 0; i + 1 < n; i++)
if (s[i] == '0') {
s[i] = '1';
s[i + 1] ^= 1;
ops++;
}
if (s[n - 1] == '0') cout << -1 << "\n";
else cout << ops << "\n";
}
return 0;
}
| Input | Output |
|---|---|
| the sample | 2 -1 0 -1 |
0, 00, 011110 |
-1 1 5 |
0011010 |
3 (zeros at 0, 1, 4, 6: (1 − 0) + (6 − 4)) |
Solutions in C++, Java and Python
The full solution (fewest flips, -1 if impossible; the YES/NO version is "answer ≠ −1").
C++: the program above.
Java (tested with the same inputs: 2 -1 0 -1 and -1 1 5):
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder out = new StringBuilder();
while (t-- > 0) {
int n = Integer.parseInt(br.readLine().trim());
char[] s = br.readLine().trim().toCharArray();
int ops = 0;
for (int i = 0; i + 1 < n; i++)
if (s[i] == '0') {
s[i] = '1';
s[i + 1] = (s[i + 1] == '0') ? '1' : '0';
ops++;
}
out.append(s[n - 1] == '0' ? -1 : ops).append('\n');
}
System.out.print(out);
}
}
Python (same outputs):
import sys
def main():
data = sys.stdin.read().split()
t = int(data[0])
out = []
pos = 1
for _ in range(t):
n = int(data[pos]); s = list(data[pos + 1]); pos += 2
ops = 0
for i in range(n - 1):
if s[i] == '0':
s[i] = '1'
s[i + 1] = '1' if s[i + 1] == '0' else '0'
ops += 1
out.append(str(-1 if s[n - 1] == '0' else ops))
print("\n".join(out))
main()
Brute force vs optimal
| Brute force (all move sets) | Parity rule | Sweep (fewest flips) | |
|---|---|---|---|
| Time per test | O(2^(n−1) · n) | O(n) | O(n) |
| n = 40 | ≈ 2·10^13 steps: TLE | 40 steps | 40 steps |
| Sum of n = 2·10^5 | impossible | 2·10^5 steps | 2·10^5 steps |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Sweep without the last-cup check (cout << ops) |
2 1 0 2 instead of 2 -1 0 -1 |
the sweep always finishes; it just leaves the last cup down | if (s[n - 1] == '0') print -1 |
s[i + 1] = '1'; instead of toggling |
-1 1 0 -1 instead of 2 -1 0 -1 |
a flip toggles, it does not fix | s[i + 1] ^= 1; |
mask < (1 << (n - 1)) in the brute force |
NO instead of YES for 32 cups ending in 00 |
1 << 31 overflows int (negative), so the loop never runs |
1LL << (n - 1) |
| Submitting a guessed pattern | Wrong answer on a later test | eight cases are not a proof | prove it, then stress-test |
The third bug is nasty: a wrong brute force makes a stress test useless.
Mini project
Write a generic pattern finder: a brute-force BFS over all states of a small string puzzle (state = bitmask, moves = XOR with fixed masks), which prints the solvable/unsolvable table for every string of length 1…8. Use it on the homework variants below and on any ad-hoc problem with flip moves.
Practice
-
A move flips
s[i]ands[i + 2]. When is the answer YES?Answer
Moves never mix even and odd positions, so the parity of zeros on even positions and the parity of zeros on odd positions are both invariant. For n ≥ 3: YES ⇔ both counts are even (the sweep works on each class). For n ≤ 2 no move exists: YES only if all are 1. Checked by BFS for every string up to length 9. -
A move flips three neighbouring cups
s[i], s[i + 1], s[i + 2]. Find the invariant.Answer
Let c0, c1, c2 be the numbers of zeros at positions ≡ 0, 1, 2 (mod 3). Each move changes every one of them by ±1, so the parities of c0 + c1 and c1 + c2 never change. For n ≥ 3: YES ⇔ c0, c1, c2 have the same parity (checked by BFS up to length 10). Example: <code>000</code> → YES, <code>0111</code> → NO. -
A move adds 1 to three different numbers
a[i]. Show thatsum mod 3never changes.Answer
Each move adds exactly 3 to the sum, and 3 ≡ 0 (mod 3). -
Why was the brute force allowed to try each move at most once?
Answer
Moves commute (the result depends only on how many times each cup is flipped) and a move done twice cancels, so only "used an odd number of times or not" matters. -
Fewest flips for
0110?Answer
Zeros at 0 and 3: 3 moves (<code>0110 → 1010 → 1100 → 1111</code>).
Quick quiz
s = "0011010". Possible? Fewest flips?
A) NO · B) YES, 2 flips · C) YES, 3 flips · D) YES, 4 flips
Answer
C. Four zeros (even) → YES. Zeros at 0, 1, 4, 6: (1 − 0) + (6 − 4) = 3. The program above prints 3.
Interview questions
- What is an invariant? A quantity that no allowed move changes. If the start and the goal have different values, the goal is unreachable.
- How do you find a pattern in an ad-hoc problem? Brute force on all tiny inputs, print a table, look at what YES cases share (counts, parities, sums mod k, positions).
- Why is a pattern not enough? It may fail on larger inputs; prove it (invariant for NO, construction for YES) and stress-test it.
- Why does the order of flips not matter? XOR is commutative and associative; each cup's final state depends only on how many moves touched it.
- Why is the greedy sweep optimal here? The first cup forces the first move, and so on: exactly one move set works, so there is nothing to optimise.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Ad-hoc problem | A problem with no standard algorithm; needs an observation about this exact problem | Two Hands |
| Observation | A fact about the problem that makes it easy | "only the parity of zeros matters" |
| Brute force | Try every possibility; slow but surely correct | all 2^(n−1) move sets |
| Invariant | A quantity no move can change | the bishop's colour; parity of zeros |
| Parity | Whether a number is even or odd | 5 zeros: odd |
| Constructive proof | Proving YES by building the answer | the left-to-right sweep |
| Stress test | Compare a fast solution with a brute force on many random inputs | 1000 random trays |
mask |
An integer whose bits mark which moves are used | bit i = use move i |
XOR (^) |
Bitwise "exclusive or": 1 when bits differ | '0' ^ 1 == '1' |
1LL << k |
2^k as a 64-bit number | 1LL << 39 |
| Integer overflow | A value too big for its type wraps around | 1 << 31 is negative |
| Sum of n constraint | A limit on the total size of all test cases | sum n ≤ 2·10^5 |
mt19937 |
C++ random number generator | mt19937 rng(16) |
Summary
- Ad-hoc problems need one observation; find it with a method: brute force → print tiny answers → guess → prove → stress-test.
- The brute force over
2^(n−1)move sets is correct but got TLE at n = 40. - One flip changes the zero count by −2, 0 or +2: the parity is invariant → odd zeros means NO.
- The left-to-right sweep proves even zeros means YES, and it is the only move set, so its count is the minimum.
- O(n) per test; 1000 random trays agreed with the brute force.
- Real bugs: no last-cup check (
2 1 0 2),= '1'instead of toggling (-1 1 0 -1),1 << 31overflow (NOinstead ofYES).
Next episode: bit tricks: XOR properties, masks and __builtin functions.