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

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

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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
»
10 лет назад, # |
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.

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

    Previous year champion has a wildcard?

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

    Are you sure?

    There are a total of 26 spots in the Finals, including mystic's spot. So if he places in the top 25, the top 26 contestants will all advance to the finals. Otherwise, the top 25 + mystic will advance.

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

      Right, for some reason I thought top-25 including mystic will advance, however the official site says that top-25 along with mystic are going to LA.

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

How to solve Clarge?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Min-cost-max-flow (the idea isn't very hard, but it'd take a lot of time to explain it in details).

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

      I used just max-flow. The idea is co create a chain of vertices for each person, with vertices within the chain corresponding to events. A flow equal to 1 indicates than a person is inside, and a flow equal to 0 indicates that he is outside. Unfortunately, it's (O(n2)) vertices and edges.

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

    Maximal matching, then adding E? before and L? after, if needed.

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

      Can you write your solution more detailed? I had something like that, but each variation of my matching solution didn't work on some test =\

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        You can download my solution.

        mincost maxflow: Imagine that there are two vertices of infinite capacity, but edges cost 1. For every ID!=0 look if first entry is E , connect it to first vertex. If last entry is L, connect it to second.

        I wrote Matching that does the same.

        Check if your original graph (without that vertices) is correct.

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

    I have greedy solution, through it is quite complex

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

How to solve D-small?

  • »
    »
    10 лет назад, # ^ |
    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.

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

      When I saw the constraint is N <= 80, I immediately thought that any brute force would time out. :(

      Could you leave your handle so I can take a look at how you implemented this idea? Thanks :)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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).

»
10 лет назад, # |
  Проголосовать: нравится +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!

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

    Even if it isn't, you'll be qualified because someone in top-25 definitely will decline invitation.

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

      Thank you very much!

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

      And that's what you're hoping for :D

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

        I'm having an internship at Google from 06/23 till 09/26. I don't really know if I'm eligible to participate in onsite in this situation.

        I'm going to ask something from jury about that (of course if I'll be invited).

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

    The e-mail for the invitation for the round was pretty clear that 25 people + mystic would advance, so the 26th is also qualified.

    See you in LA! :)