×

# ANKGAME - Editorial

Author: Ankit Srivastava and Uttam Kanodia
Tester: Roman Rubanenko
Editorialist: Amit Pandey

Easy-Medium.

# PREREQUISITES:

Game theory and Combinatorics.

# PROBLEM:

A game is played with the rule that a non-zero number of the stones must be removed from the first non-empty 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_1-1$ 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{(N-x)!}{(M-x)!\ 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(N-x)!}{(M-x)!}$$

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
Tester's solution can be found here

This question is marked "community wiki".

25911522
accept rate: 0%

19.8k350498541

 2 answered 22 Jun '15, 02:05 7★alei 231●5 accept rate: 0%
 1 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 5★saanc 650●5●7●21 accept rate: 0% Fixed, thanks for pointing out. (22 Jun '15, 00:47)
 0 Nice tutorial. But can someone explain the last step i.e. Ways(2r) = W(2r) - W (2r+1).. (Also what is this 'r' here.) answered 22 Jun '15, 00:25 6★likecs 3.7k●23●80 accept rate: 9% thanks :) as we have to keep even number of 1's in the beginning. So, r is an integer >= 0, as given in number of permutations formula. (22 Jun '15, 00:40)
 0 I can not access the author's or tester's solutions because I keep getting the following error: AccessDenied Access Denied BAB460C98DBD4174 ESEdzdoiDcxnEmbsJ0jb0xUcx/qeOmelwnlKaUJg2akfvF3K2PvGlB39v8tMYbLz The RequestId and HostId change when I refresh. answered 22 Jun '15, 00:48 128●13 accept rate: 16%
 0 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 21●1 accept rate: 0% 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)
 0 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 5★miteshag 31●2 accept rate: 0%
 0 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 3★NPSD 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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 3-2=1 but actual answer is 2 answered 01 Jul '15, 22:21 3★tirupati 1●2 accept rate: 0%
 0 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 3★esemzv 21●2 accept rate: 0%
 0 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 3★esemzv 21●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,672
×891
×317
×150
×81
×2

question asked: 17 Jun '15, 10:24

question was seen: 4,353 times

last updated: 27 Feb '16, 12:52