rishabh1994's blog

Doubt
By rishabh1994, 11 years ago, In English

This is a 2 player game . There are matchsticks . A person can remove either 1 matchstick or any 2 adjacent matchsticks . Removing a matchstick creates a hole. I denotes a matchstick , X denotes a hole .

Example IIII

There are four matchsticks. Now if the first player removes second matchstick (IXII) then only second and third matchsticks are adjacent now . Given a number n denoting the length of string and the string in the next line , output if it possible for player 1 to win assuming he takes the first turn . The player who makes the last move wins the game . Assume both players play optimally.

Sorry if problem is not clear as i dont remember it exactly . This was asked in a coding round held in our college for internship.

Example 3 III output : Win 4 IXXI output : Loose

Please let me know the logic or the approach of the above problem .

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

The player who makes the last move wins the game

If you are not mistaken, then it is quite simple. First player always win if he takes 1 or 2 sticks from the middle, so that two equal parts remain. Then he simply follows "symmetric strategy".

Far most complicated variant is when the player to move last lose the game.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Actually the thing is that the state is given after both the players have taken many turns . So now we have string like (IIIXXXIIXIXIXIXIX) where I denotes a matchstick which a person can remove and X means a hole that is the matchstick from there has been removed . Also a person can remove 2 adjacent matchsticks also . Now from this position onward both play optimally and the person making the last move wins . Now we have to detemine who is the winner . Please tell some approach to solve this. Thanks for your answer .

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Please tell some approach to solve this. Thanks for your answer

      You repeat this as a chant, so I start suspect the problem is either from some ongoing contest or from your homework :D

      What are the limits on the number of sticks given with your problem?

      → Reply
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Well this is neither from a ongoing contest neither a hw contest . I dont cheat and submit solutions to ongoing contest by taking help from others . This question was asked for internship by some company in our college . The limits on the number of stick was around 400.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I think that for such limit you have no other ways (like some simplified DP) except the approach advised by goo.gl_SsAhv. One of the main disadvantage of it is that you need to spend significant time to understand it :)

          → Reply
»
11 years ago, hide # |
← Rev. 5  
Vote: I like it +2 Vote: I do not like it

There is Sprague–Grundy theorem. Look also game NIM.

→ Reply