Explain your logic for this game thoery problem

help
, , , ,
1

Problem Link-https://www.codechef.com/LOCAPR17/problems/ABHIAMBI

2

For solving these type of problems you should work over small data and look for pattern to crack the logic.
So, in this problem you are given N, the number of piles and H, the height of each pile which will be always prime.

These are some of the key observations:

  1. It’s stated that you can remove X coins from a pile with height H, so obviously 1<=X<=H. That means X can take values ranging from 1,2,3,…,H.
  2. Calculate how many coins in total you have to remove. It will be the product of N and H. Let’s denote it by Y. Since you can use one value of X only once, what’s the total coins you can remove? It will be sum of all the values of X you can take. Let’s denote it by S. So, S = 1+2+3+…+H or, S = (H*(H+1))/2.

Now, the base case is when n=1. In this case, Abhi always wins. As he can choose X=H.

Now there are two cases:

Case I: When S < Y: In this case it is guaranteed that the game will stop due to lack of moves as there are not enough moves to remove all the coins. So, there are total H moves (1,2,3,…H). If H is odd, Abhi wins else Ambi wins. Quite trivial.

Case II: When S>=Y: In this case you can prove that Abhi always wins. Here we can ensure that the game will complete (that is, we can remove all coins from all the piles). There are enough moves. Since Abhi plays first, he can always choose X=H as his first move and remove any one pile completely. Now X can only attain values < H. For every X=k that Ambi chooses, Abhi can choose X=H-k and remove that pile. He can do this for all the piles and hence he wins the game. Note that k will never be equal to H-k as H is prime and H will be always odd except when H=2, which will always fall under Case 1, as even for N=2 if H=2, we get S=3 and Y=4. So obviously for larger N it will be valid.

Although I wrote too much, the solution is very very short. Link: https://www.codechef.com/viewsolution/13758433

2 Likes
3

@rishi_07 quite amazing explanation
Thank you
The editorial wasn’t that clear to me but your explanation was up to the mark.

4

@rishi_07 when i solved this problem during contest, my idea was not as simple as your’s ,but too close to your approach.
This one is better idea.You have made this problem very easy. This will help to others as well as me
to solve this type of problems easily.

1 Like