ANKGAME - Editorial

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Ankit Srivastava and Uttam Kanodia

Tester: Roman Rubanenko
Editorialist: Amit Pandey

DIFFICULTY:

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

5 Likes
2

Nice tutorial.
But can someone explain the last step i.e. Ways(2r) = W(2r) - W (2r+1)… (Also what is this ‘r’ here.)

3

thanks :slight_smile: 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.

4

there is a mistake in claim 1. It should be “if number of piles is even, then second player will win”

1 Like
5

Fixed, thanks for pointing out.

6

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.

7

My editorial: https://aleigorithms.wordpress.com/2015/06/21/ankit-srijan-and-a-game-of-stone-piles/

2 Likes
8

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

9

It is even - odd.

10

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

11

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

12

Can someone help me finding out why I am getting runtime error. Below is my code.
http://www.codechef.com/viewsolution/7275255

13

I am getting wrong answer…i have tried many testcases can anybody suggest me some corner cases that i maybe missing…Thanks in advance

14

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.

15

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

16

Can you please give links to setter/tester’s solutions in ideone? The links you have provided don’t work.

17

Can you please give links to setter/tester’s solutions in ideone? The links you have provided don’t work.