ayushrocker92's blog

problem in a game theory question
By ayushrocker92, 10 years ago, In English

Hi,

I am trying to solve to solve this question.

I have also read the editorial 2-3 times but i am not getting the basic concept on how to solve this question.

Please help.

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

»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Which part? Trie stuff or game theory? Game theory in this problem is simply calculating the winner for each state of the game. If you can move the other player into a losing state from somewhere it is a winning state else it is a losing state. And if the state is a leaf of trie it is a losing state.

EDIT 1: And for this problem you need to calculate "can you lose if you want to" too in a similar way.

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

    Game theory part.Am not clear what the states actually represent and how transition is done among states.Trie part is clear

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

      As i said you need to calculate can you lose if you want to in a different array. But think for the normal problem first.Here is my submission 7403866 (yeah debugs everywhere). Each node of trie represents the string made by chars you have to pass through starting from the root. And you can calculate is a string is a wining or losing state for the Player Making Move On It(PMMOI) by checking each valid string you can make your move. If any of them are losing states for the PMMOI your string is a winning state because if you make that move other player will lose. But if there is no such move you will lose. You can fill the array win[] which holds is that stae is winning or not by iterating all trie array backwards because all childs of a node have a bigger id than that node. I fill the array lose at the same which holds can you lose if you want to for that string same way. After you have this information you can know which player can win or lose a one game you can find out who will win the Kth game.

      → Reply