dickynovanto1103's blog

Help on Game Theory problem — SOS Gym ECL-Final 2017
By dickynovanto1103, history, 6 years ago, In English

Hi Codeforces community, I have tried to figured out the solution of this problem: http://codeforces.com/gym/101775/problem/L . However, I can't get the way to solve this problem. Maybe anyone knows the approach to solve this problem?

I know that game theory type problem often require to compute the grundy number. But as far as I know, computing the grundy number is just the identifier whether the state is losing state (grundy number = 0) or winning state (grundy number != 0). However, this problem required to output condition where the result may be a draw and I don't know what is the grundy number representation for a draw.

Maybe do anyone know how to compute the grundy number if the solution is computing the grundy number?

Thanks anyway!! Good day to you..

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dickynovanto1103 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dickynovanto1103 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dickynovanto1103 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You don't need Grundy numbers for this problem, haven't seen a problem with "Draw" as a possible answer that is solvable with Grundy numbers. You can solve it without any advanced Game Theory, so I encourage you to play the game given in the problem and figure out when you can win as the first player and as the second player.

I found it helpful to think of how a player can make a "trap" to make the other one lose.

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

    Okay..thanks a lot for your hint :D...Does it mean that making a trap is the one of the optimal step to make?

    Sometimes I find it difficult to determine what is a optimal step for a player, because in this game, the optimal move can be a step to create opportunity to win (create 'S' to be later formed "SOS"), or just to prevent from losing, and making a trap.

    Does 3 steps as I said before can be considered as an optimal step?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      If it's a game where someone can win, then in the optimally played game the player in the winning position will try to make a trap (and succeed, since the other can try to prevent it but won't be able to). Then the player in the losing position can try to delay his lost, but in the end he will have to fall in the trap.

      Try to think of what a trap looks like and in which cases it can be made. Or you can do the DP with bitmask and see a pattern as ancile suggested XD this approach of solving small cases and finding a pattern is very useful and works for many problems.

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

        Thanks a lot for your explanation :D...may good things come to you

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          the general advice in this kind of problem is if you can't get how the optimally play solution looks like in one glance, then you have several options here: 1. try to "play" the game using pen and paper (this consume time, and you should only do this if u have time) 2. If the constraint is big enough like this problem, try to code the DP/bruteforce solution for smaller N (or smaller constraint in general), and check for pattern. Usually, problem with big constraint is needed for you to infer the pattern. 3. If the constraint is small enough that DP solution (or maybe bruteforce solution) suffice, I suggest don't bother to check for how the nim version should be like (or etc).. Just code the DP solution, and get accepted already during the contest. Learn the nim version etc, later on.. 4. If the solution indeed need nim (and grundy), you're out of option here, and need to devise the grundy and nim solution during the contest. (To minimize this, you need to see many nim problem beforehand, so that the prior knowledge can help you here).

          → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Find pattern in this problem. Code a DP bitmask solution, and run it with N ~ 18.. (3^18 ~ 400million). Then check the pattern for N = 1 .. 18. After that, try to deduce for n > 18.. That should help you.

→ Reply