Problem: dealing_decks (2023 finals)

Alice and Bob like to play cards on their lunch break. Their favorite card game starts with two decks on the table containing \(K_1\) and \(K_2\) cards. Players take turns, with Alice going first. Each turn is in two parts:

1. The player selects a deck of cards from the table. Let \(k\) be the number of cards in that deck. They then remove somewhere between \(A_k\) and \(B_k\) \((1 \le A_k \le B_k \le k)\), inclusive, cards from this deck.
2. The player then puts a new deck of exactly \(C_k\) \((0 \le C_k < k)\) cards on the table. Here, \(C_k = 0\) means no deck is added.

The player who takes the last card wins.

For each possible value of \(K_1\) from \(1\) to a given value \(N\), find the minimum possible value of \(K_2\) so that Bob wins the game if both players play optimally. If there is no such \(K_2\) between \(1\) and \(N\), then \(K_2 = -1\). Output the sum of \(K_2\) across every \(K_1 = 1..N\).

To reduce the input size, you will not be given \(A_{1..N}\), \(B_{1..N}\), and \(C_{1..N}\) directly. You must instead generate them using parameters \(X_a\), \(Y_a\), \(Z_a\), \(X_b\), \(Y_b\), \(Z_b\), \(X_c\), \(Y_c\), and \(Z_c\) and the algorithm below:

\(P_a[0] := 0\)
\(P_b[0] := 0\)
\(P_c[0] := 0\)
\(\text{for each } i := 1..N\):
\(\;\;\;\;\; P_a[i] := (P_a[i - 1] * X_a + Y_a) \text{ mod } Z_a\)
\(\;\;\;\;\; P_b[i] := (P_b[i - 1] * X_b + Y_b) \text{ mod } Z_b\)
\(\;\;\;\;\; P_c[i] := (P_c[i - 1] * X_c + Y_c) \text{ mod } Z_c\)
\(\;\;\;\;\; A[i] := \min(i, 1 + P_a[i])\)
\(\;\;\;\;\; B[i] := \max(A[i], i - P_b[i])\)
\(\;\;\;\;\; C[i] := \min(i - 1, P_c[i])\)

Note that for any \(i\), the algorithm guarantees \(1 \le A_i \le B_i \le i\) and \(0 \le C_i < i\).

# Constraints

\(1 \le T \le 45\)
\(1 \le N \le 2{,}000{,}000\)
\(1 \le X_a, Y_a, X_b, Y_b, X_c, Y_c \le 1{,}000{,}000{,}000\)
\(1 \le Z_a, Z_b, Z_c \le N\)

The sum of \(N\) across all test cases is at most \(50{,}000{,}000\).

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each case, first there is a line containing a single integer \(N\). Then, there is a line containing integers \(X_a\), \(Y_a\), \(Z_a\), \(X_b\), \(Y_b\), \(Z_b\), \(X_c\), \(Y_c\), and \(Z_c\).

# Output Format

For the \(i\)th case, output `"Case #i: "` followed by a single integer, the sum of the minimum \(K_2\) so that Bob has a guaranteed winning strategy, for every \(K_1 = 1..N\).

# Sample Explanation

In the first sample case:

\( \begin{array}{c|c|c|c|c}\underline{K_1}&\underline{A[K_1]}&\underline{B[K_1]}&\underline{C[K_1]}&\underline{K_2} \\ 1&1&1&0&1 \\ 2&1&2&0&2 \\ 3&1&3&2&1 \\ 4&1&4&0&4 \end{array} \)

When \(K_1 = 1\), Bob wins when \(K_2 = 1\) because Alice takes the first card, and Bob takes the last card.

When \(K_1 = 2\), Alice will win if \(K_2 = 1\) because she can start by taking \(1\) card from the first deck. Bob then takes \(1\) card from either deck (each of which have only \(1\) card left), and Alice takes the last card. But if \(K_2 = 2\) then Bob can always win regardless of whether Alice starts by taking \(1\) card or \(2\) cards.

When \(K_1 = 3\), Bob can always win when \(K_2 = 1\). If Alice takes the single card from the second deck, Bob takes \(1\) card from the first deck and adds a new deck of size \(2\) to the table. We now have two decks of size \(2\), and it's Alice's turn. That's a losing state for Alice as we saw previously.

If Alice takes \(1\) card from the first deck and adds a new deck of size \(2\), we now have decks of size \([2, 1, 2]\). Bob will pick up the pile of size \(1\) and again we're in the same losing state for Alice. If Alice takes \(2\) cards from the first deck, we'll have decks of size \([1, 1, 2]\). Bob now takes the whole deck of size \(2\). Alice gets the next card and Bob gets the last card. Finally, if Alice takes all \(3\) cards from the first deck, we'll have decks of size \([1, 2]\). Bob can take just \(1\) card from the deck of size \(2\) to win.

In the second sample case:

\( \begin{array}{c|c|c|c|c}\underline{K_1}&\underline{A[K_1]}&\underline{B[K_1]}&\underline{C[K_1]}&\underline{K_2} \\ 1&1&1&0&1 \\ 2&1&1&0&2 \end{array} \)

In the third sample case:

\( \begin{array}{c|c|c|c|c}\underline{K_1}&\underline{A[K_1]}&\underline{B[K_1]}&\underline{C[K_1]}&\underline{K_2} \\ 1&1&1&0&1 \\ 2&1&2&0&2 \\ 3&2&3&1&2 \end{array} \)

In the fourth sample case:

\( \begin{array}{c|c|c|c|c}\underline{K_1}&\underline{A[K_1]}&\underline{B[K_1]}&\underline{C[K_1]}&\underline{K_2} \\ 1&1&1&0&1 \\ 2&1&2&0&2 \\ 3&3&3&2&3 \\ 4&1&4&0&4 \\ 5&5&5&4&3 \\ 6&1&6&0&6 \\ 7&6&7&4&3 \\ 8&1&8&0&8 \end{array} \)


Sample input:
4
4
25 30 2 45 16 4 7 26 4
2
19 48 2 38 23 2 43 31 2
3
9 17 2 23 42 2 21 43 2
8
23 5 8 14 22 2 29 28 6


Sample output:
Case #1: 8
Case #2: 3
Case #3: 5
Case #4: 30


Solution: To start, let’s look at the Sprague-Grundy function for a deck of arbitrary size \(k\):

\[\displaystyle g(k) = \text{mex}(\{ g(k - i) \oplus g(C_k) \mid i \in [ k - B_i, k - A_i ] \}) \]

In other words, to compute the value of \(g(k)\), we can perform the following steps:

1. Construct a set \(S\) of all values \(g(i)\), where \(i = k - B_i, ..., k - A_i\).
2. XOR each value of \(S\) with \(C_k\).
3. Find a mex (minimum excluded value) of \(S\) and assign it to \(g(k)\).

Since we need to compute \(g(k)\) for each \(k = 1..N\), we need a data structure that supports all the listed operations with \(\mathcal{O}(\log N)\) complexity. Such data structure exists – it’s a simple trie. Let’s represent each value of \(g(k)\) in its binary form and store binary string representations in the trie. Each node will have no more than two edges (one edge corresponds to \(0\), the other to \(1\)). For each node of the trie, let’s store the last value of \(k\) for which it has been updated.

Suppose for a certain value of \(k\) we want to find the mex of all values \(g(x)\) from \(g(l)\) to \(g(k)\). We can descend from the root of the trie to some leaf, each time going to the child which hasn’t been updated after \(l - 1\). If both child nodes satisfy this condition, we pass through \(0\)-edge. At any moment, if there is no corresponding edge, that means the node has never been updated.

Now we can modify this approach for finding the mex of all values \(g(x) \oplus y\) from \(g(l)\) to \(g(k)\) (for any value of \(y\)). To do so when both child nodes haven’t been updated after \(l - 1\) we will pass through \(0\)-edge only if the corresponding bit in \(y\) is \(0\), otherwise we will pass through \(1\)-edge.

The only modification we need now is to make this approach correct for an arbitrary right border \(r \ge l\). It can be done by simply making the trie persistent. This way we can always perform the previously explained approach on the version of the trie we had right after adding the value of \(g(r)\). The only extra price we pay is \(\log N\) times more memory usage.

Since any descent on a trie takes \(\mathcal{O}(\log N)\) steps, the overall complexity of the described approach is \(\mathcal{O}(N \log N)\).

When all values are computed, we can use them to find the value of \(K_2\) for each \(K_1\). First, \(K_2\) always exists and \(K_2 \le K_1\). If \(K_2 = K_1\), Bob can always win by mirroring Alice’s turns. Since we need Bob to win, we are interested in states where \(g(K_1) \oplus g(K_2)\) is zero and \(K_2\) is as small as possible. So all we need to do is find the minimum \(K_2\) such that \(g(K_1) = g(K_2)\). This can be done in \(\mathcal{O}(N)\) time and doesn’t affect the final \(\mathcal{O}(N \log N)\) complexity of the solution.



Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int kBitCount = 22;

class PersistentTrie {
  vector<int> roots, last, last_rec;
  vector<vector<int>> nodes;

  inline int get_root(int ind) {
    return ind == -1 ? 0 : roots[ind];
  }

  vector<int> get_bits(int val) {
    vector<int> bits(kBitCount, 0);
    for (int i = 0; i < kBitCount; i++) {
      if (val & (1 << i)) {
        bits[kBitCount - i - 1] = 1;
      }
    }
    return bits;
  }

 public:
  void reset(int n) {
    last.assign(1, -1);
    last_rec.assign(1, -1);
    nodes.assign(2, vector<int>(1, -1));
    roots.clear();
    roots.reserve(n + 1);
    last.reserve((n + 1) * (kBitCount + 1));
    last_rec.reserve((n + 1) * (kBitCount + 1));
    nodes[0].reserve((n + 1) * (kBitCount + 1));
    nodes[1].reserve((n + 1) * (kBitCount + 1));
  }

  void add(int val, int ind) {
    vector<int> bits = get_bits(val);
    int r = roots.size(), node_id = nodes[0].size();
    roots.push_back(node_id);
    int root_id = get_root(r - 1);
    nodes[0].push_back(nodes[0][root_id]);
    nodes[1].push_back(nodes[1][root_id]);
    last.push_back(ind);
    vector<int> visited_nodes(1, node_id);
    visited_nodes.reserve(kBitCount + 1);
    for (int i = 0; i < kBitCount; ++i) {
      int next_node_id = nodes[bits[i]][node_id];
      if (next_node_id == -1) {
        nodes[0].push_back(-1);
        nodes[1].push_back(-1);
      } else {
        nodes[0].push_back(nodes[0][next_node_id]);
        nodes[1].push_back(nodes[1][next_node_id]);
      }
      last.push_back(ind);
      next_node_id = (int)nodes[0].size() - 1;
      nodes[bits[i]][node_id] = next_node_id;
      node_id = next_node_id;
      visited_nodes.push_back(node_id);
    }
    last_rec.resize(last.size());
    last_rec[visited_nodes.back()] = last[visited_nodes.back()];
    for (int i = (int)visited_nodes.size() - 2; i >= 0; i--) {
      const int node_id = visited_nodes[i];
      last_rec[node_id] = last[node_id];
      for (int j = 0; j < 2; ++j) {
        const int child_node_id = nodes[j][node_id];
        if (child_node_id == -1) {
          last_rec[node_id] = -1;
        } else {
          last_rec[node_id] = min(last_rec[node_id], last_rec[child_node_id]);
        }
      }
    }
  }

  int get_mex(int l, int r, int val) {
    if (!r) {
      return val ? 0 : 1;
    }
    int res = 0;
    vector<int> bits = get_bits(val);
    int node_id = get_root(r);
    for (int i = 0; i < kBitCount; ++i) {
      if (node_id == -1) {
        break;
      }
      for (int j = 0; j < 2; ++j) {
        const int bit_val = bits[i] ^ j;
        const int child_node_id = nodes[bit_val][node_id];
        if (child_node_id == -1) {
          node_id = child_node_id;
          res |= (j << (kBitCount - i - 1));
          break;
        }
        if (last_rec[child_node_id] < l) {
          node_id = child_node_id;
          res |= (j << (kBitCount - i - 1));
          break;
        }
      }
    }
    return res;
  }
};

PersistentTrie trie;

long long solve() {
  int N, x1, y1, z1, x2, y2, z2, x3, y3, z3;
  cin >> N >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> x3 >> y3 >> z3;
  vector<int> A(N), B(N), C(N);
  long long pa = 0LL, pb = 0LL, pc = 0LL;
  for (int i = 0; i < N; i++) {
    pa = (pa * x1 + y1) % z1;
    pb = (pb * x2 + y2) % z2;
    pc = (pc * x3 + y3) % z3;
    A[i] = min(i + 1, (int)(1 + pa));
    B[i] = max(A[i], (int)(i + 1 - pb));
    C[i] = min(i, (int)pc);
  }
  A.insert(A.begin(), 0);
  B.insert(B.begin(), 0);
  C.insert(C.begin(), 0);
  trie.reset(N);
  trie.add(0, 0);
  vector<int> f(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
    f[i] = trie.get_mex(i - B[i], i - A[i], f[C[i]]);
    trie.add(f[i], i);
  }
  vector<int> lnk(1 << kBitCount, -1);
  long long ans = 0LL;
  for (int i = 1; i <= N; i++) {
    if (lnk[f[i]] == -1) {
      lnk[f[i]] = i;
    }
    ans += lnk[f[i]];
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}