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

Hacker Cup Online Round 1
Автор Anurag, 14 лет назад, По-английски
Sub-round1
1. After the Dance Battle
2.
3.

Please tell on how to solve these problems?
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
1 - BFS
Add adjacent unused cells to the queue.
When you are in the cell with non-zero digit, add all cells with the same digit to the queue (and mark them as used, of course).

3. DP
dp is: dp[i][j] = max(dp[i-1][j-1] * probability_of_successful_overtaking, dp[i-1][j] * probability_of_successful_normal_turn)
Answer is dp[n][r-1]
dp[i][j] = probability of being alive after i turns with j overtakings
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "...dp[i][j] = probability of being alive after i turns with j overtakings"
    Correction: if this is a right state then answer is dp[n][r-1].
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Yes, you're right. I've done r--; in my program for convenience but here dp[n][r-1] is more appropriate.
      → Ответить
14 лет назад, # |
← Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится
LOL!  -1 for what ? U guys want me to be dormant? When i am active i get -(minuses) and when i am dormant , i am getting nothing.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
After the Dance Battle: Simple BFS.
First or Last: Simple DP with BigInteger.
→ Ответить