ayush29azad's blog

By ayush29azad, history, 3 years ago, In English

Can someone help me in solving this game theory problem? I am not able to get the discussions /editorial , this problem is very tough . Please Help !!!!!!!!!!

Problem Link :

https://leetcode.com/problems/stone-game-ix/

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

First observation: the values of the stones by themselves doesnt matter, what matters is their value mod 3. In particular, what matters is the ammount of each stone on each mod value. From now on when i talk about value im talking about the value mod 3.

Second observation: you can never start with a stone that has value 0, so you will have to pick either one with value 1 or 2. After you pick a stone with value 2, you cant pick a stone with value 1, so you will have to pick a stone with value 2, and then you will have to pick a stone with value 1, and them two, and so it goes. The order you need to take the stones is fixed

Third observation: stones with value 0 essentially skip the turn. If the number of them is even, then nothing can be done because if you want to skip the turn the opponent can always skip back. If its odd, then you will be able to skip the turn if it favors you, even if the opponent tries to fight against that.

Solution: test for picking a stone with value 1 first, then for picking a stone with value 2 first. You will keep alternating between them after that, and the loser is the one who runs out of stones of the type he wants that turn (you also need to think of the scenario where all of the stones run out, which is really annoying). If the number of stones with value 0 is odd, then the loser is the opposite (because of the third observation). Then you pick which situation is the one that is better for the first player, because they are going to choose which one the game starts.