PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: dauzanbeketov5
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
PROBLEM:
Two players play a game on an N\times M rectangle.
Initially, a certain cell (x, y) is marked.
Then, the game proceeds as follows:
- On their turn, a player cuts the rectangle into two pieces either horizontally or vertically.
Then, whichever part doesn’t have the marked cell is discarded.
Whoever cannot make a move loses.
There are N\times M possible cells to mark. How many of them result in a win for the first player?
EXPLANATION:
As a first, simple observation, note that the game will only end when we’re left with a single cell: the marked one.
Let’s try to solve a simple instance of the game first.
Suppose N = 1, and cell (1, x) is marked.
Observe that in this case, we start out with (x-1) ‘extra’ columns to the left of the marked cell, and (M-x) extra columns to its right, which all need to be removed.
Each move, a player will reduce the number of extra columns on either the left side or the right side; but not both. Further, the left and right sides are completely independent (in the sense that making a move on one side doesn’t affect which future moves are possible on the other).
You might notice that this is essentially just the game of nim played with two piles, of sizes (x-1) and (M-x).
So, the first player wins if (x-1)\oplus (M-x) \neq 0 (which is simpler written as x-1\neq M-x).
\oplus here denotes bitwise XOR.
Similarly, if M = 1, we end up with a two-pile game of nim with the number of rows above and below the marked cell.
Now, we try to extend this idea to the general case.
There are four quantities to worry about now: the number of rows above/below the marked cell, and the number of columns to the left/right of the marked cell.
It’s not hard to see that they are all independent: that is, any move will reduce exactly one of these four quantities, and at any stage, a player is able to choose any one of the four quantities and reduce it by as much as they like.
In other words, if cell (x, y) is marked, we essentially have a game of nim with the pile sizes
[x-1, N-x, y-1, M-y].
It’s well-known that the second player wins if and only if the bitwise XOR of the pile sizes is zero, which in our case means
So, all we need to do is count the number of pairs (x, y) that satisfy this condition.
Note that equivalently, we want the number of pairs (x, y) such that
That’s fairly easy to do with just a bit of preprocessing:
- Create a frequency table F, where F_k denotes the number of integers x (1\leq x\leq N) such that (x-1)\oplus (N-x) = k.
F can be a map, or even just an array of length 2N; since the bitwise XOR of two integers is at most twice the larger one. - Then, for each y between 1 and M, add F_{(y-1)\oplus (M-y)} to the answer.
Now you have the number of situations where the second player wins; subtract this from N\times M to obtain the number of situations where the first player wins.
TIME COMPLEXITY:
\mathcal{O}(N + M) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, m; cin >> n >> m;
vector <int> f(2 * max(n, m) + 1, 0);
for (int i = 1; i <= n; i++){
f[(i - 1) ^ (n - i)]++;
}
int ans = 0;
for (int i = 1; i <= m; i++){
ans += f[(i - 1) ^ (m - i)];
}
ans = n * m - ans;
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input_checker inp;
int T = inp.readInt(1, (int)1e4); inp.readEoln();
int NN = 0, MM = 0;
while(T-- > 0) {
int N = inp.readInt(1, (int)1e6); inp.readSpace(); NN += N;
int M = inp.readInt(1, (int)1e6); inp.readEoln(); MM += M;
if(N > M) swap(N, M);
vector<int> F(2 * M + 2);
long long ans = N * 1ll * M;
for(int i = 1 ; i <= M ; ++i)
F[(i - 1) ^ (M - i)] += 1;
for(int i = 1 ; i <= N ; ++i)
ans -= F[(i - 1) ^ (N - i)];
cout << ans << '\n';
}
assert(max(NN, MM) <= (int)1e6);
inp.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
# for (x, y), (x-1) ^ (n-x) ^ (y-1) ^ (m-y) == 0 is bad
ct = [0]*(2*n + 5)
for i in range(1, n+1): ct[(i-1) ^ (n-i)] += 1
ans = 0
for i in range(1, m+1):
x = (i-1) ^ (m-i)
if x < 2*n + 5: ans += ct[x]
print(n*m - ans)