PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: shanu_singroha
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
easy
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game on an N\times M grid. On Alice’s turn, she chooses an uncolored cell and colors everything in its row/column red; on Bob’s turn he does the same but with blue.
The players move according to a cyclic string S, till no more moves are possible.
Find the winner, who is the person with more cells of their color.
EXPLANATION:
Recall from the solution to the easy version that the actual moves made don’t matter at all to the final count of reds and blues.
For simplicity, we can make moves at (1, 1), (2, 2), (3, 3), \ldots which makes analyzing the process a bit cleaner.
Now that N, M \leq 10^9, we can’t simulate the entire process.
Let’s fix a move i, and see how many red cells this move will give to Alice.
Only cells (x, y) such that x = i or y = i will be affected.
- For cells (x, i) and (i, x) such that x \leq i, they’ll turn red - and remain red, because no future move can affect them; after all any future move will affect only cells with at least one coordinate greater than i.
- This is 2i-1 cells in total that will become red (and remain red), no matter what they used to be.
- For (x, i) and (i, x) with x \gt i, we again have two possibilities:
- i \lt x \leq \min(N, M).
For such x, the cell in consideration will be changed by the move made at (x, x). So, it being set to red now doesn’t matter at all; and we can ignore such cells entirely. - x \gt \min(N, M).
For such x, no future move will ever affect them, so they will become red and remain red.
There are \max(N, M) - \min(N, M) = |N-M| such cells, which will add to Alice’s count.
- i \lt x \leq \min(N, M).
So, if Alice chooses (i, i), the number of cells added to her total that won’t be changed by future moves is exactly 2i - 1 + |N-M|.
This means, to find the final number of red cells, all we need to do is sum this up across all i that Alice operates on!
Let’s consider an index i (1 \leq i \leq K) of the string S.
If S_i = \text{'A'}, then it will be Alice’s turn on moves i, i+K, i+2K, \ldots due to the cyclic nature of the string.
In particular, Alice will move on turn i+x\cdot K for all x \geq 0 such that i + x\cdot K \leq \min(N, M).
The largest such x is then x = \left\lfloor \frac{\min(N, M) - i}{K} \right\rfloor.
Let C denote this maximum.
To compute the total number of cells obtained from all these moves, note that we essentially want to compute the value
Here, (|N-M| - 1) is a constant and appears x+1 times, so we just add (x+1)\cdot (|N-M|-1) to the total and remove it from the summation.
The remaining part is the sum of 2\cdot (i + x\cdot K) across a range of x.
Note that this is an arithmetic progression starting from 2i and with step size 2K, so its sum can be computed in \mathcal{O}(1) time as well by directly applying the formula, to obtain
So, we’re able to calculate the number of red cells Alice obtains from all the moves i, i+K, i+2K, \ldots in constant time.
Do this for every index i of the string, adding the count to either Alice’s or Bob’s total, and we obtain the red/blue counts of both players in \mathcal{O}(K) time, hence solving the problem.
TIME COMPLEXITY:
\mathcal{O}(K) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int t;
cin>>t;
while(t--){
int n, m, k;
cin>>n>>m>>k;
string s;
cin>>s;
int a = 0;
int b = 0;
int mn = min(n, m);
for(int i = 0; i < k; i++){
int cnt = mn / k;
if(i < mn % k){
cnt++;
}
int temp = cnt * (2 * i + (cnt - 1) * k);
temp += cnt * (abs(m - n) + 1);
if(s[i] == 'A'){
a += temp;
}else{
b += temp;
}
}
if(a > b){
cout<<"Alice\n";
}else if(b > a){
cout<<"Bob\n";
}else{
cout<<"Draw\n";
}
}
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m, k; cin >> n >> m >> k;
string s; cin >> s;
auto ap_sum = [&] (ll a, ll n, ll d) {
return n * (2*a + (n-1)*d)/2;
};
auto solve = [&] () {
ll alice = 0, bob = 0;
for (int i = 0; i < k and i < min(n, m); ++i) {
// How many times does this appear?
// i, i+k, i+2k, ..., i+xk
// i+xk < min(n, m)
// xk < min(n, m) - i -> x <= (min(n, m) - i - 1)/k
int ct = (min(n, m) - i - 1)/k + 1;
// appears at i, i+k, i+2k, ...
// so, gives 2i+1, 2*(i+k)+1, 2*(i+2k)+1, ... cells
// 2i+1, 2i+1+2k, 2i+1+4k, ...
if (s[i] == 'A') {
alice += ap_sum(2*i+1, ct, 2*k) + 1ll*ct*abs(n - m);
}
else {
bob += ap_sum(2*i+1, ct, 2*k) + 1ll*ct*abs(n - m);
}
}
if (alice > bob) return "Alice";
if (bob > alice) return "Bob";
return "Draw";
};
cout << solve() << '\n';
}
}