Old Wives' Game

Without all the glory details, in her turn, a player chooses an index $i$ such that $v_i > 0$, then chooses a positive integer $k$ smaller than $v_i$, and does the following operation: $v_i’ \equiv v_i \pmod k$.

We can think of the gameplay on each container as independent nim games. Thus, if we can compute the grundy values of the nim game played on each container, we can eventually find out the winner. If $g_i$ is the grundy value of the nim game played on the $i^{th}$ container, then if $g_1 \oplus g_2 \oplus \cdots \oplus g_n$ is non-zero, first player wins.

For a container of size $x$, we can choose different cup sizes $k$ such that the new size $x’$ ranges in $[0, \text{ceil}(\frac{x}{2}) - 1]$. So, grundy value $g(x) = \text{mex}(g(0), g(1), \cdots, g(\text{ceil}(\frac{x}{2}) - 1))$. As container sizes range upto $10^7$, we can precompute the grundy value for each size in a ‘prefix mex array’-ish approach. However, it can be proven by induction that $g(x)$ equals to the index of the most significant bit in $x + 1$.

Source Code (C++)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 7;

int g[N], pg[N];
bool mark[N];

void precompute() {
    g[0] = 0, pg[0] = 1, mark[0] = true;
    int mex = 0;

    for(int i=1; i<N; ++i) {
        g[i] = pg[(i + 1) / 2 - 1];
        mark[g[i]] = true;
        while(mex < N and mark[mex]) ++mex;
        pg[i] = mex;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    precompute();

    int t, tc = 0;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for(int& x : a) cin >> x;

        int res = 0;
        for(int x : a) res ^= g[x];
        cout << (res ? "Mrinalini" : "Kadambari") << "\n";
    }

    return 0;
}