SyntaxPilot
Courses/Competitive Programming/Lesson 16

Competitive Programming · Lesson 16 of 90 · 12 min

Ad-hoc and observation problems

queued

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 s of n characters: 1 is an upright cup, 0 is upside down. In one move you pick i (0 ≤ i < n − 1) and flip both s[i] and s[i + 1] (0 ↔ 1). Can all cups become 1, using any number of moves? Print YES or NO.

1 ≤ t ≤ 10^4 test cases, 1 ≤ n ≤ 2·10^5, the sum of n over all tests is at most 2·10^5.

Sample input Sample output
4
3
010
4
1101
1
1
5
00000
YES
NO
YES
NO

"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:

  1. Order doesn't matter. Each cup ends up flipped once for every move that touches it, whatever the order.
  2. 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:

  1. Write a brute force that is slow but surely correct.
  2. Print its answers for every tiny input, in a table.
  3. Guess the pattern, then prove it.
  4. 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: whenever s[i] = '0', flip (i, i + 1). After the sweep, cups 0 … n − 2 are all 1. Only the last cup can be 0, but the number of zeros is still even, so it is 0: the last cup is 1 too. 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

  1. A move flips s[i] and s[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.

  2. 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.

  3. A move adds 1 to three different numbers a[i]. Show that sum mod 3 never changes.

    Answer Each move adds exactly 3 to the sum, and 3 ≡ 0 (mod 3).

  4. 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.

  5. 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

  1. What is an invariant? A quantity that no allowed move changes. If the start and the goal have different values, the goal is unreachable.
  2. 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).
  3. Why is a pattern not enough? It may fail on larger inputs; prove it (invariant for NO, construction for YES) and stress-test it.
  4. 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.
  5. 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 << 31 overflow (NO instead of YES).

Next episode: bit tricks: XOR properties, masks and __builtin functions.