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
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$$$.
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.
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
First off, there is no space before the question mark.
No, there is only one trie. Looks like this:
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.