Recover Red and Blue Balls
National Olympiad — National round (2024 season)
Submission name: balls.cpp
Problem summary
A row contains red and blue balls. For every position i, S[i] is the parity of the number of blue balls from i through the end (0 even, 1 odd). Recover the ball colors.
Input
N, then a binary string S of length N.
Output
A length-N string using r for red and b for blue.
Constraints
1 ≤ N < 600000; memory limit 1 MB.
Worked example
An independently prepared example for this explanation.
Input
8 01110100
Output
brrbbbrr
Solution analysis
- Compare the parity of the suffix starting at i with the suffix starting at i+1. Their blue counts differ only by whether ball i is blue.
- Different parities mean a blue ball; equal parities mean a red ball. The empty suffix after the last position has parity zero, so the last ball is blue exactly when the last input bit is one.
- For 01110100, the first two suffix bits differ, producing b; the next pair are equal, producing r. Continuing these comparisons gives brrbbbrr. Stream with one character of lookahead to stay comfortably within the small memory bound.
Why it works
Removing a red ball leaves the blue count unchanged, while removing a blue ball changes it by one and flips parity. Each adjacent suffix-parity comparison therefore uniquely identifies its ball, including the final comparison with the empty suffix.
Watch out. These are suffix parities, so compare with the next bit, not the previous bit. Treat the missing final suffix as zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
char current;
cin >> current;
for (int i = 0; i < n; i++) {
// The empty suffix after the last ball has even blue parity.
char next = '0';
if (i + 1 < n) {
cin >> next;
}
cout << (current == next ? 'r' : 'b');
current = next;
}
cout << '\n';
}