Official

F - Interval Game 2 Editorial by en_translator

We will provide you some step-by-step hints as an editorial. Before advancing the next hint, consider the information you have obtained so far.

PrerequisitesIn order to solve this problem, the knowledge of "Grundy number" in game theory. The problem related to Grundy number is frequently found in competitive programming, so the necessary knowledge can be obtained by referring to the materials on the Internet.
Hereinafter we assume you already know about Grundy number. Before you advance the editorial, understand the knowledge of Grundy number as much as possible and consider the problem again.
hint 1First, we can assume that the game is played on the segment $[1,100)$. Here, let us consider what will happen when Alice choses a segment as the first move.
hint 2Assume that Alice chose the segment $[X, Y)$ as the first move. Then, the game is split into independent two games: one game is on the segment $[1,X)$, the other is on the $[Y,100)$ (of course, depending on the choice of the segment, one or both of the game is ceases). Here, remember a property of Grundy number.
hint 3As shown in hint 2, when a segment is chosen in a game, the original game is divided into two independent games.
Here, we can use the property of the Grundy number that the overall Grundy number consisting of some subgames are the XOR of Grundy number of each subgame.
Also, if the game has no choosable segment, its Grundy number is $0$.
Also, we can see that there are $100^2$ possible segments of games, and there are at most $100$ possible moves from each state.
Now you have enough information to come up with a solution.

SolutionConsider the following DP.
  • \(dp[X,Y)=\)(The Grundy number of the game on the segment \([X,Y)\))
The DP can be implemented with a memorized recursion.
Simulate every transition (division of game) caused by a choice of a segment within \([X,Y)\), and calculate the \(mex\) by the definition of Grundy number. The overall complexity is \(O(TNS^2)\) (where \(S\) is the initial size of the segment of the game, which this time we can treat as \(S=100\)), which is fast enough to solve this problem.
Sample code in C++

#include<bits/stdc++.h>
 
using namespace std;
using pi=pair<int,int>;
 
int grundy(int l,int r,vector<vector<int>> &dp,vector<pi> &seg){
  if(l>=r){return 0;}
  if(dp[l][r]!=-1){return dp[l][r];}
  vector<bool> kh(128,false);
  for(auto &nx : seg){
    if(l<=nx.first && nx.second<=r){
      kh[grundy(l,nx.first,dp,seg)^grundy(nx.second,r,dp,seg)]=true;
    }
  }
  for(int i=0;;i++){
    if(!kh[i]){dp[l][r]=i;break;}
  }
  return dp[l][r];
}
 
int main(){
  int t;
  cin >> t;
  for(int cs=1;cs<=t;cs++){
    int n;
    cin >> n;
    vector<pi> seg(n);
    for(int i=0;i<n;i++){
      cin >> seg[i].first >> seg[i].second;
      seg[i].first--;seg[i].second--;
    }
    vector<vector<int>> dp(100,vector<int>(100,-1));
    if(grundy(0,99,dp,seg)){cout << "Alice\n";}else{cout << "Bob\n";}
  }
  return 0;
}

posted:
last update: