DSA sheet / Introductory
Coin Piles
The problem in brief
There are t test cases (up to 100 000). Each gives two pile sizes a and b (up to 10^9). A move removes exactly 2 coins from one pile and exactly 1 coin from the other, your choice of which. For each test, print YES if some sequence of moves empties both piles exactly, otherwise NO.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1754.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Ignore which pile you pick for a moment. How many coins disappear in total per move? What does that say about a + b?
-
That gives one necessary condition on a + b. Is it enough? Try (1, 5): the sum passes but something else breaks.
-
Each move takes at least 1 from each pile. If the small pile is very small compared to the big one, what goes wrong?
-
Suppose you do x moves that take 2 from pile A and y moves that take 2 from pile B. Write the two equations for how many coins leave each pile and solve for x and y. When are they non-negative integers?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
For “can this be reduced to zero” problems, the fastest route is to look for invariants and then check whether the necessary conditions are also sufficient. Every move removes 3 coins, so a + b must be divisible by 3. That is necessary, not sufficient.
Next, model the moves algebraically instead of simulating. Let x be the number of moves that take 2 from A (and 1 from B) and y the number that take 2 from B (and 1 from A). Then a = 2x + y and b = x + 2y. Solving gives x = (2a - b)/3 and y = (2b - a)/3. You need both to be non-negative integers, which is exactly: a + b divisible by 3, and 2a >= b and 2b >= a, i.e. the larger pile is at most twice the smaller.
The habit: when you can write the process as a linear system, existence questions become inequalities you can check in O(1). Confirm the closed form against a brute-force search on small piles.
Intuition
Each move drains the piles in a 2:1 ratio, one way or the other. Mixing the two directions gives you overall drain ratios anywhere between 2:1 and 1:2. So the piles can only be emptied together if their sizes sit between those two ratios, and the total must be a multiple of 3 so that the coin count matches.
Approach
For each test, answer YES if and only if (a + b) % 3 == 0 and max(a, b) <= 2 * min(a, b). Otherwise print NO.
Edge cases: (0, 0) is YES (nothing to do). (0, k) with k > 0 is NO because the larger pile cannot be at most twice zero. Values are up to 10^9, so 2 * min fits in 32 bits but use 64-bit anyway to be safe. Read the input with fast I/O; there can be 100 000 lines.
Complexity
O(1) per test, O(t) overall.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long a, b;
cin >> a >> b;
bool ok = (a + b) % 3 == 0 && max(a, b) <= 2 * min(a, b);
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.read().split()
t = int(data[0])
out = []
for i in range(t):
a = int(data[1 + 2 * i])
b = int(data[2 + 2 * i])
ok = (a + b) % 3 == 0 and max(a, b) <= 2 * min(a, b)
out.append("YES" if ok else "NO")
print("\n".join(out))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(in.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
StringTokenizer st = new StringTokenizer(in.readLine());
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
boolean ok = (a + b) % 3 == 0 && Math.max(a, b) <= 2 * Math.min(a, b);
sb.append(ok ? "YES" : "NO").append('\n');
}
System.out.print(sb);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const t = data[0];
const out = [];
for (let i = 0; i < t; i++) {
const a = data[1 + 2 * i];
const b = data[2 + 2 * i];
const ok = (a + b) % 3 === 0 && Math.max(a, b) <= 2 * Math.min(a, b);
out.push(ok ? 'YES' : 'NO');
}
console.log(out.join('\n'));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).