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

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

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

16 лет назад, скрыть # |
← 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
→ Ответить
16 лет назад, скрыть # |
← 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.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
After the Dance Battle: Simple BFS.
First or Last: Simple DP with BigInteger.
→ Ответить