PROBLEM LINK:Author: Ankit Srivastava and Uttam Kanodia DIFFICULTY:EasyMedium. PREREQUISITES:Game theory and Combinatorics. PROBLEM:A game is played with the rule that a nonzero number of the stones must be removed from the first nonempty pile. Find the number of permutations of the piles, in which the first player has a winning strategy. QUICK EXPLANATION:Find a way to check if a given permutation is the winning permutation, followed by finding the number of permutations which satisfy the given condition. EXPLANATION:The problem can be solved using various claims. Claim 1: If each pile contains exactly $1$ stone. Now, if number of piles is even, then second player will win. Otherwise, first player will win. Reason: The reason being that each player will have exactly one way of making a move, i.e. emptying the current pile. Claim 2: If the first pile contains more than one stone, then first player will always win. Reason: Suppose that piles are numbered as $1,2,3...N$. Number of stones in piles are given as $A_1,A_2,....A_N$ with the condition $A_1 \ge 2$. Case 1: Suppose in piles $A_2,A_3,...A_N$, first player has winning strategy, then first player will remove $A_11$ number of stones from the first pile and second player will be enforced to remove remaining $1$ stone. First player will have winning strategy on remaining piles. Case 2: Suppose in piles $A_2,A_3,...A_N$, first player doesn't have winning strategy, then first player will empty first pile in single move. So, when game will arrive as pile $2$, second player will not have the winning strategy, hence first player will have winning strategy. Claim 3: Now we can claim very easily that first player will win if permutation is in such a way that $A_1 = 1, A_2 = 1,... A_x = 1, A_{x+1} != 1$, and $x$ is an even number, because when the game will arrive at pile number $(x+1)$, first player will be making first move and he will win according the points given above. How to count number of permutations such that number of 1's in the beginning is even? Suppose count of $1$'s in the array $A$ is $M$. Each distinct number of array $A$(except 1) is in array $B$, i.e., $B_1, B_2,...B_K$, and count of $B_i$ in array $A$ is $cnt[B_i]$. Now count the number of permutations in which number of 1's in the beginning is at least $x$. To do that, keep $x$ $1's$ in the beginning and permute rest of the numbers. $$W(x) = \frac{(Nx)!}{(Mx)!\ cnt[B_1]!\ cnt[B_2]!\ ....\ cnt[B_K]!} $$ $$\text{Consider } K = \frac{1}{cnt[B_1]!\ cnt[B_2]!\ ....\ cnt[B_K]!} $$ $$So, W(x) = \frac{K\times(Nx)!}{(Mx)!} $$ Number of permutations in which number of $1's$ in the beginning is exactly $2r$. $$ Ways(2r) = W(2r)  W(2r+1)$$ So, number of permutations in which numbers of 1's in the beginning is even: $$ \text{Number of permutations} = \sum_{r=0}^{2r+1 \le M} Ways(2r) $$ $K$ is a constant which can be calculated in $O(N)$ time, and we can calculate it in the beginning. So, Number of permutations can also be calculated in $O(N)$ time. Solution:Setter's solution can be found here
This question is marked "community wiki".
asked 17 Jun '15, 10:24

answered 22 Jun '15, 02:05

there is a mistake in claim 1. It should be "if number of piles is even, then second player will win" answered 22 Jun '15, 00:43

I can not access the author's or tester's solutions because I keep getting the following error:
The answered 22 Jun '15, 00:48

I had used the similar idea but subtracted the permutations which begin with odd number of ones from total number of permutations. But, got wrong answer. Wasn't able to fix it up. Code link : http://www.codechef.com/viewsolution/7264254 answered 22 Jun '15, 11:10
It is even  odd.
(22 Jun '15, 11:19)
Used int instead of long long for the number at two places now its working
(22 Jun '15, 12:22)

Can anybody please suggest me, as to why I am getting TLE with same solution of mine? http://www.codechef.com/viewsolution/7266806 answered 22 Jun '15, 11:45

Can someone help me finding out why I am getting runtime error. Below is my code. http://www.codechef.com/viewsolution/7275255 answered 24 Jun '15, 02:09

I am getting wrong answer...i have tried many testcases can anybody suggest me some corner cases that i maybe missing...Thanks in advance answered 25 Jun '15, 01:48

I tried a different approach... I used the principle of inclusion and exclusion. I am getting right answers for all the cases that i tried. But it is showing wrong answer here. http://www.codechef.com/viewsolution/7310208 are there any corner cases that it is failing? can anyone please help. answered 01 Jul '15, 20:40

I have a problem with Number of permutations formula mentioned above. Say you have 1 1 2 as the numbers then we can see that first player wins when 1 1 2 or 2 1 1 so 2 possibilities. But the formula mentioned i.e summation here M=2; B1 = 1; and n=3; so summation would be just doing w(20)w(20+1) as 2*r+1<=M so r can take only one value i.e 0 w(2*0) would be 3 and w(1) would be 2 hence answer will be 32=1 but actual answer is 2 answered 01 Jul '15, 22:21

Can you please give links to setter/tester's solutions in ideone? The links you have provided don't work. answered 27 Feb '16, 12:52

Can you please give links to setter/tester's solutions in ideone? The links you have provided don't work. answered 27 Feb '16, 12:52
