Ankit, Srijan and a game of stone piles

Problem statement: http://www.codechef.com/COOK59/problems/ANKGAME

Problem Analysis:

How can we know who wins the game if we already know the order of the piles?
Let f_i denote who wins the game if we consider only the last i piles. By convention f_i=0 if  the first player always wins and  f_i=1 otherwise.

Note that f_n=0 . because the first player can remove all stones and win. So now let’s analyse what happens when i<n . There are two cases:

Case 1. f_{i+1}=0
If the number of stones in the pile i is equal to 1 , then the first player always loses (because he will be the second player on pile i+1). On the other hand, if the number of stones on pile i is greater than 1 , then the first player can erase all stones minus one (In this way he will be the first player on pile i+1).
Case 2. f_{i+1}=1
The optimal strategy for the first player is to remove all stones of pile i (in this way he will be the second player on pile i+1)

With that in mind, we can construct a recurrence that calculates the number of pile permutations in which the first player always wins.
The only case in which the first player loses is when the number of stones of the first pile is 1, and f_2=0 (note that this is valid only when n>1 , indeed I didn’t notice this in my first submission)
Let g_u denote the number of ways in which the first player wins, if we have already used u piles of one stone. It is easy to calculate g_u by complementation: g_u is the total permutations of piles if we don’t use u piles of one stone (this can be easily calculated with the multinomial) minus the number of ways in which the first player loses. The nice fact is that the number of ways in which the first player loses is equal to the number of ways in which the first player wins if we have used one more pile of one stone.
In Iverson notation:

g_u={n-u \choose q_1-u, q_2, q_3,...} - [u<q_1] \cdot g_{u+1} , where q_i is the number of piles with i stones.

I got AC on this question 40 seconds before the end of the contest 🙂

p.s Be careful, A_i \leq 10^{10}
As usual, my awesome implementation:


#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;

const uli mod=1e9+7;
const int mx=1e5+10;
uli fa[mx],fi[mx],d[mx];
int n,n1;
uli ivs;
uli fxp(uli b,uli x,uli m){
   uli a=1;
   for(;x!=0;b=b*b%m,x>>=1)
      if(x&1ll)a=a*b%m;
   return a;
}
inline uli solve(int u){
   uli cmb=fa[n-u]*fi[n1-u]%mod*ivs%mod;
   if(u==n1){
      if(n==u)return 0;
      return cmb;
   }
   return (cmb-solve(u+1)+mod)%mod;
}
int main(){
   fa[0]=fi[0]=1;
   for(int i=1;i<mx;i++){
      fa[i]=fa[i-1]*uli(i)%mod;
      fi[i]=fxp(fa[i],mod-2,mod);
   }
   int t;
   scanf("%d",&t);
   while(t--){
      scanf("%d",&n);
      n1=0;
      for(int i=0;i<n;i++){
         scanf("%lld",d+i);
         if(d[i]==1)n1++;
      }
      sort(d,d+n);
      ivs=1;
      for(int i=0;i<n;){
         uli v=d[i];
         int qv=0;
         while(i<n && d[i]==v) i++,qv++;
         if(v!=1)ivs=ivs*fi[qv]%mod;
      }
      uli ans=solve(0);
      printf("%lld\n",ans);
   }
   return 0;
}

Author: Alei Reyes

I know that I know nothing

Leave a comment