PROBLEM LINK:
Setter: Prasann_Kumar_Gupta
Tester: Vishal_Mahavar
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Game Theory, Recursion-Memoization
EXPLANATION
We can use Sprague Grundy theorem to solve the problem. To do so we have to find the grundy numbers for each state. We can use Dynamic programming to do so.
So, let dp[a][b] denote the grundy value for a pile pair \{ a,b \}. Now we know, Grundy value is nothing but the MEX of grundy value of all states immediately reachable from the current state. Therefore, let set S_1 be a set consisting of all states \{ a-E_1,b+E_1/2 \} for all positive even number E_1 less than or equal to a. Similarly, S_2 be a set consisting of all states \{ a+E_2/2,b-E_2 \} for all positive even number E_2 less than or equal to b. Then,
dp[a][b] = MEX(S1 + S2)
We can easily precompute these grundy values for every pair \{ a,b \}, where 0 \leq a \leq 500 and 0 \leq b \leq 500 in the required time limit.
After finding Grundy numbers for every pile pair, we just need to xor the Grundy value for every pile pair involved in the game, as we do in a standard nim game. If the Xor is 0, Reyna loses, Else she wins.
Setter's Solution
#pragma GCC target ("avx2")
//#pragma GCC optimize "trapv"
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define input(a,n) for(ll i1=0;i1<n;i1++)cin>>a[i1]
#define ll long long
#define pi 2 * acos(0.0)
#define usll uset<ll>
#define sll set<ll>
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpll vector<pll>
#define umll umap<ll,ll>
#define S second
#define sz size()
#define all(v) v.begin(),v.end()
#define Y cout<< "YES"<< "\n"
#define N cout<< "NO"<< "\n"
#define F first
#define pb push_back
#define pf push_front
#define ld long double
#define random(l,r,T) uniform_int_distribution<T>(l,r)(rng)
using namespace __gnu_pbds;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<class T, class H>using umap=unordered_map<T,H,custom_hash>;
template<class T>using uset=unordered_set<T,custom_hash>;
const ll mod = 1000000007;
vector<vector<ll>> dp(751,vector<ll>(751,-1));
ll game(ll a,ll b){
if(dp[a][b] != -1)
return dp[a][b];
if(abs(a-b) < 2 || (a < 2 && b < 2)){
dp[a][b]=0;
dp[b][a]=0;
}
else{
ll h[501]={0};
for(ll i=2;i<=a;i+=2)
h[game(a-i,b+i/2)]=1;
for(ll i=2;i<=b;i+=2)
h[game(a+i/2,b-i)]=1;
for(ll i=0;;i++){
if(h[i]==0){
dp[a][b]=i;
dp[b][a]=i;
break;
}
}
}
return dp[a][b];
}
int main()
{
//freopen("07.in","r",stdin);
//freopen("07.out","w",stdout);
clock_t clk = clock();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll test=1;
cin>>test;
for(ll i=0;i<=500;i++){
for(ll j=0;j<=500;j++)
game(i,j);
}
for(ll tc=1;tc<=test;tc++){
ll n,ans=0;
cin>>n;
for(ll i=1;i<=n;i++){
ll x,y;
cin>>x>>y;
ans ^= dp[x][y];
}
if(ans)
cout<< "YES\n";
else
cout<< "NO\n";
//cout<< "Case #"<<tc<< ": "<<ans<< "\n";
}
cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
const int M = 500;
const int N = M + M/2;
int memo[N+1][N+1];
int solve(int a,int b){
if(memo[a][b] != -1) return memo[a][b];
int len = a/2 + b/2;
int mex[len+1]={0};
for(int E=2;E<=a;E+=2){
mex[solve(a-E,b+E/2)]=1;
}
for(int E=2;E<=b;E+=2){
mex[solve(a+E/2,b-E)]=1;
}
int ans;
for(ans=0;;ans++) if(mex[ans]==0) break;
memo[a][b] = memo[b][a] = ans;
return ans;
}
int main(){
memset(memo,-1,sizeof(memo));
int t; cin>>t; assert(1<=t && t<=100);
while(t--){
int n; cin>>n; assert(1<=n && n<=1e4);
int ans=0;
for(int i=1;i<=n;i++){
int x,y; cin>>x>>y; assert(0<=x&&x<=500&&0<=y&&y<=500);
ans = (ans ^ solve(x,y));
}
if(ans) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}