You are not logged in. Please login at to post your questions!


ANKGAME - Editorial




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




Game theory and Combinatorics.


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.


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.


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.


Setter's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

asked 17 Jun '15, 10:24

amitpandeykgp's gravatar image

accept rate: 0%

edited 09 Feb '16, 20:02

admin's gravatar image

0★admin ♦♦


answered 22 Jun '15, 02:05

alei's gravatar image

accept rate: 0%

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

saanc's gravatar image

accept rate: 0%

Fixed, thanks for pointing out.

(22 Jun '15, 00:47) amitpandeykgp4★

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

likecs's gravatar image

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) amitpandeykgp4★

I can not access the author's or tester's solutions because I keep getting the following error:

<Error> <Code>AccessDenied</Code> <Message>Access Denied</Message> <RequestId>BAB460C98DBD4174</RequestId> <HostId> ESEdzdoiDcxnEmbsJ0jb0xUcx/qeOmelwnlKaUJg2akfvF3K2PvGlB39v8tMYbLz </HostId> </Error>

The RequestId and HostId change when I refresh.


answered 22 Jun '15, 00:48

noble_mushtak's gravatar image

accept rate: 16%

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 :


answered 22 Jun '15, 11:10

venkatnani82's gravatar image

accept rate: 0%

It is even - odd.

(22 Jun '15, 11:19) amitpandeykgp4★

Used int instead of long long for the number at two places now its working

(22 Jun '15, 12:22) venkatnani822★

Can anybody please suggest me, as to why I am getting TLE with same solution of mine?


answered 22 Jun '15, 11:45

miteshag's gravatar image

accept rate: 0%

Can someone help me finding out why I am getting runtime error. Below is my code.


answered 24 Jun '15, 02:09

NPSD's gravatar image

accept rate: 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

ag_shar96's gravatar image

accept rate: 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.

are there any corner cases that it is failing?

can anyone please help.


answered 01 Jul '15, 20:40

akash0123's gravatar image

accept rate: 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

tirupati's gravatar image

accept rate: 0%

edited 01 Jul '15, 22:23

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

esemzv's gravatar image

accept rate: 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

esemzv's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 17 Jun '15, 10:24

question was seen: 4,340 times

last updated: 27 Feb '16, 12:52