Matches (May Long)

help
, ,
1

Can anybody help me to figure out the problem in my approach for the Long problem MATCHES, here is my code.

https://www.codechef.com/viewsolution/24287375

3 Likes
2

For n = 1 m = 1 Your output will be “Ari” but it should be “Rich”. Why? well it is exercise for you.

Please check wiki page for nim game first to understand below details.

My bad I directly jumped to nim game.
Let me explain it in detail
Assume n != 1 and m != 1 and n != m
So according to your code we will find number of moves( or we say piles and number of stones in pile). Now our task is to pick stones from piles and last picker will win ( except one restriction players should empty piles or pick stones chronologically).
In your code you are getting count of number of piles and then if they are even assuming rich will win which is not always true. Assume there are two piles and each first pile contain 2 stones(moves) and second contains 1 stone. Then your program will return Rich but Ari can win by first removing 1 stone from pile 1.

Hope it helps you to understand. Let me know if require any detail

4

You should apply greedy method in every step like in first step Ari become greedy and in second step rich become greedy alternate this process continue.
For example1. 17 6
Ari can take two type stpe:
11 6
5 6
5 1 so rich will win
Type second
17 6
5 6
5 1. So Ari will be win by become greedy

5

" Assume there are two piles and each first pile contain 2 stones(moves) and second contains 1 stone. Then your program will return Rich but Ari can win by first removing 1 stone from pile 1 "

my code will return “Ari” as i have considered the case
if(m==1 || n==1 || m==n) cout<<“Ari”<<endl;

6

I have applied greedy approach only but still getting WA.

7

Player needs to play optimally. As quoted by @man_hard earlier “17,6” Ari will win by becoming greedy. However, greedy approach won’t work for below.
Initial : 9 4
Player | Case 1 | Case 2
Ari | 5 4 | . 1 4
Rich |1 4 |rich wins
Ari |Ari wins |

Hence the question reduces to which step should Ari choose.

Let me know if need any more clarification

8

Thanks @anunay1991 for pointing out my mistake so not every time greedy will work so whats the approach to solve this problem then.

9

I’ve used the classical dynamic-programming approach which ensures the correct answer and makes things pretty clear, I’ll soon write an editorial for it :slight_smile:

1 Like
10

it can be solved using greedy algo as ‘Ari’ will direct the game in such a way he will always win if he get more than 1 possible way of removing the matches.

11

One solution can be this

Condition 1 : If the two numbers are such that the ratio of the bigger and smaller number is 2 or more than that. Then the player whose chance is there to remove a number can direct this game accordingly so that he will always will.

If the ratio is less than 2 than there is only one move possible move. keep checking the condition 1 after this move and keep track whose chance is there to remove the number when condition 1 satisfy

if the ratio is 1 than always the first person will win

2 Likes
12

@rk_221b
Let’s approach this problem mathematically, with below constructs.

  1. You reduce the bigger heap with a multiple of the lower heap
  2. If a heap is reduced to 0, the current player wins.
  3. Ari starts the game
  4. Both play optimally

Therefore, we can assume we have 2 heaps (big & small)
big can be interpreted as below:
big = m*small + d

hence, while approaching the solution we will reach a state where we are left with heaps (small, d)

Since Ari starts the game, there can be only 2 possible cases at small, d
Case 1: Ari wins
Case 2: Ari loses (hence, Ari should pass small+d, small to Rich to win)

If m >= 2, then Ari will choose a state with either small, d (i.e. remove small m times from big) or (small+d, d ; i.e. remove small m-1 times). Since Ari has full control for this condition, Ari will always win

if m == 1; then Ari has no choice to make a move, hence Ari will pass small, d to Rich.
Now if Rich has m’ >= 2 for new heap, Rich will win, else Rich will have single option only.

Game will go on until either heap is reduced to 0.

Dry Run:
m >= 2;
17 , 6 --> (m >= 2; Ari wins) – already mentioned earlier
9, 4 --> m >=2; Ari wins – same–

m == 1
5, 4 --> 1, 4 (m >=2 ; Current player; i.e. Rich wins)

4 Likes
13

Hi @rk_221b

Apologies for late reply. I was not talking about given problem statement, forgot to explain transformation part and directly explained second part.

  • What is nim game ?

    • We have n piles and player can remove any number of stones from piles. Winner will be last picker(or other player).

  • Part 1:

    • First convert given game to simple nim game with less restriction(possibly none). As problem statement explain game that we can remove stones X if X % SmallPile is 0.
    • So number of moves for any player at given instance will be BigPile/SmallPile (e.g N = 10 M = 5, then number of moves will be 2 = 10/5, here we can remove 5 or 10 stones (because it 5 divides both values)).
    • We will create an array which will keep numberOfMoves for each instance (e.g N = 15 M = 4, 15/4 => 3, next N = 3 (15%4), M = 4 swap to keep consistency N = 4, M = 3. again 4/3 = 1, next N = 1(4%3), M = 3 swap and N = 3, M = 1. again 3/1 = 3, 3%1 = 0 (stop when 0) . Here arrayOfMoves = {3, 1, 3}) .
    • We can say that this array is now representing nim game where numberOfMoves are stones and player can remove any numberOfStones from pile but with one restriction that player always have to choose first non-empty pile.

  • Part 2:

    • In first part we established a fact that we have a nim game with one restriction that player had to choose first non-empty pile and can remove any number of stones. There are 3 ways to solve this problem :
      • By observation we can say that first player will lose in one condition only[Not tried] :
        • There are two piles with {1, 1} stones.
      • We can find grundy number of this array and if it is 0 then first will lose[CodeChef: Practical coding for everyone].
      • Use DynamicProgramming in minMax fashion as resultant number of piles will not large.

I hope this explain my thoughts. Please let me know if require any details.

1 Like