Блог пользователя DontHackMeSenpai

456D. A Lot of Games
Автор DontHackMeSenpai, история, 6 лет назад, По-английски

https://codeforces.me/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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить