sharmahappy654's blog

456D A lot of games
By sharmahappy654, history, 4 years ago, In English

How does dynamic programming helps to solve this problem. Tutorials say run dp on every node of trie and determine state for each node. My question is how to use that data to determine final solution. I understand, we can get who would win by looking at the state of each leaf of trie. But what i do for more than one leaf. Also what first refers to here, person who started first game or person who starts each game ?

Problem: https://codeforces.com/contest/456/problem/D Tutorial: https://codeforces.com/blog/entry/13336

Tags dp, trie
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also what first refers to here, person who started first game or person who starts each game ?

First off, understand that this "$$$k$$$ games" thing is mostly irrelevant. We are interested in, for each individual game, (1) whether the player who starts the game can force a win whatever the other player does and (2) whether the player who starts the game can intentionally lose no matter what the other player does. If we know those things, it basically comes down to the parity of $$$k$$$.

I understand, we can get who would win by looking at the state of each leaf of trie. But what i do for more than one leaf.

Imagine, that instead of appending letters, each player can move a button on the trie. It's easy to see that these games are equivalent. Now, $$$\mathrm{win}[u]$$$ in the official tutorial denotes "can we win no matter what the other player does if we are in the vertex $$$u$$$?". If the opponent can win no matter which letter we append, in other words if $$$\mathrm{win}[v] = 1$$$ for every child of $$$u$$$, then we can't win, thus $$$\mathrm{win}[u]$$$ must be 0. Otherwise $$$\mathrm{win}[u]$$$ must be 1.

Now, you can calculate the values $$$\mathrm{win}[\cdot]$$$ in the tree bottom up.

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

    For example we have these groups of strings
    aaaaa
    bbbbbb
    ccc
    Can you explain how game will go now optimally ?
    If first player decide to choose 1st or 3rd string then he will be the winner otherwise he will loose. Now how final result will depend on k ?
    And also how would I traverse trie in this case as I guess there will be 3 tries

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

      First off, there is no space before the question mark.

      And also how would I traverse trie in this case as I guess there will be 3 tries

      No, there is only one trie. Looks like this:

      Now how final result will depend on k ?

      In this game, it doesn't. Here, the player who starts the first game can win the first game, thus he can start the next game and win that one etc.

      → Reply