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

Автор Zlobober, 12 лет назад, По-английски

Code Jam R3 starts today at 14:00 UTC. Don't miss!

Top-25 contestants will pass to onsite this August in Google's LA office.

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

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится
»
12 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

To be more precise, only Top-24 and ivan.metelsky are going to LA.

Edit: I was wrong, Top-25 and ivan.metelsky will advance to the Onsite Finals.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

How to solve Clarge?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D-small?

  • »
    »
    12 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится -8 Проголосовать: не нравится

    I had simple bruteforce:

    Choose 2 starting points then recoursively choose an edge, move the player, remove edge, make recoursive call, then add edge back.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    Dynamic programming: D[Hs][Hc][Ss][Sc], where Hs and Hc are starting and current position of Hanaa and similarly Ss and Sc for Sherine. Value is the maximal balance we can achieve if it's currently Hanaa's turn.

    For each state we carefully make one turn for Hanaa and one turn for Sherine. Sherine tries to minimize the value of the state we come to, Hanaa tries to maximize. Also we do not forget to separately process states where one of the girls has no way to move (in this case we have similar solution, making the other girl collect as much as she can).

    It can be possibly implemented even easier if we'll make turn only for one girl in each DP state, but it was much more clear for me to implement it in such way as I described.

    Also the answer is maxHsminSsD[Hs][Hs][Ss][Ss] because Hanaa starts choosing starting position first, and then Sherine will choose the worst position from all possible.

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

    Recursive case analysis worked 2 minutes for me (but I stored tree as a 2D matrix, so it could be more efficient). Iterate over all starting points for A and B, then iterate over all possible moves:

    • If A and B are in the same vertex, then iterate over all possible moves for A, then we have independent games, so we can just launch DFS calculating the biggest sum from a child to a leaf for both parts.
    • If A and B are in different vertices, then iterate over all possible moves for A. Assume vertice for A is root. Then, if we move in the same subtree with B, we just remove that edge, swap A and B, and recursively call the function. Otherwise, if we move in the different tree, again we have independent cases — remove edge and launch 2 DFS.

    This is reasonable, because we make a recursive call only if we move to the same subtree, which can happen exactly once in each function call, so maximum recursive depth will be O(N).

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

Hello!

Im'ranked the 26th at this round, and considering that mystic is ranked 21st, it is certain that top 26 participants are qualified to the on-site finals?

Thanks!