DontHackMeSenpai's blog

456D. A Lot of Games
By DontHackMeSenpai, history, 6 years ago, In English

https://codeforces.net/contest/456/problem/D "Fedor wants to know who wins the game if both players will play optimally" They play optiomally each game, or maybe one of them deliberately lose to win the final game ? Thanks very much.

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

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

In each game, they will either compete to win or compete to lose depending on what's favorable. So first compute who will succeed in both cases. This can be done putting all the strings in a trie and then using DP to determine the results at each state (node in the trie).

Now there are four cases for results while competing to win and competing to lose

  1. First is able to win, First is able to lose
  2. Second is able to win, Second is able to lose
  3. Second is able to win, First is able to lose
  4. First is able to win, Second is able to lose

In case 1, First wins (he has complete control of all games)

In case 2, Second wins (he has complete control of all games)

In case 3, Second wins (he always wins and becomes second player in the next match and repeats..)

In case 4, the result depends on k being odd or even.

See this for implementation.

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

    Here you don't need the dp, as a node, is being visited only one time, not multiple times in each fun call.

    → Reply