CRCOLEZ - Editorial

editorial
, ,
1

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:

The key observation here is the fact that the cells chosen by the players don’t matter at all - the final result will always be the same! (In terms of counts of red and blue cells, that is).

Why?

Each move essentially boils down to “choose a row that hasn’t been chosen before, and a column that hasn’t chosen before, and color both this row and this column fully”.

Suppose k moves are made, with the rows chosen on these k moves being r_1, r_2, \ldots, r_k and the columns chosen being c_1, c_2, \ldots, c_k.
Let S_i be the color of the i-th move.

Let’s analyze which color various cells are.

  • First, with the last move being (r_k, c_k), any cells in that row/column will have color S_k.
    That’s N+M-1 cells.
  • Then, we look at (r_{k-1}, c_{k-1}).
    All cells in this row/column will have color S_{k-1}, except for possibly two: namely (r_k, c_{k-1}) and (r_{k-1}, c_k).
    These two cells would’ve been overwritten by the move (r_k, c_k) later, so they can be ignored.
    That means N+M-3 additional cells will have color S_{k-1}.
  • Similarly, when looking at (r_{k-2}, c_{k-2}), everything in that row/column is valid except the four cells (r_{k-2}, c_k), (r_{k-2}, c_{k-1}), (r_{k}, c_{k-2}), (r_{k-1}, c_{k-2}).
    So, N+M-5 additional cells will have color S_{k-2}.
  • It’s easy to see that this repeats for every i: there will be N+M-1 - 2\cdot (k-i) additional cells with color S_i, because exactly 2\cdot (k-i) cells in row r_i or column c_i will be overwritten by future moves.

Notice that the counts don’t depend on what the values r_i and c_i are at all!
The only thing that mattered is that the rows were distinct, and the columns were distinct, so that every following move removed two cells from consideration.

This proves our claim that literally any cells can be operated on, and the final count of red/blue will remain.

In this version of the problem, where N\cdot M \leq 2\cdot 10^5, that observation leads to an extremely simple solution: simply simulate the process.
That is, repeatedly choose a cell that hasn’t been colored yet, and then color everything in its row and column red/blue depending on who the current player is.
For ease of implementation, you can choose the cells (1, 1), (2, 2), (3, 3), \ldots

This will happen \min(N, M) times, because after the first i moves, exactly i rows and i columns will be fully colored - and so after \min(N, M) moves, the entire grid will be fully colored.
Simulating a single move will take \mathcal{O}(N + M) time, to just iterate through the row/column and mark everything, so the overall complexity is \mathcal{O}(\min(N, M)\cdot (N+M)), which is really just \mathcal{O}(N\cdot M) and so fast enough.

Once the entire grid is colored, simply count red and blue cells to finish.

TIME COMPLEXITY:

\mathcal{O}(N\cdot M + K) per testcase.

CODE:

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 brute = [&] () {
            vector a(n, vector(m, 0));
            for (int i = 0; i < min(n, m); ++i) {
                int x = s[i%k] == 'A' ? 1 : 2;
                for (int j = 0; j < n; ++j) a[j][i] = x;
                for (int j = 0; j < m; ++j) a[i][j] = x;
            }

            int alice = 0, bob = 0;
            for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
                alice += a[i][j] == 1;
                bob += a[i][j] == 2;
            }

            if (alice > bob) return "Alice";
            if (bob > alice) return "Bob";
            return "Draw";
        };

        cout << brute() << '\n';
    }
}