Zlobober's blog

Google Code Jam Round 3
By Zlobober, 11 years ago, In English

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.

  • Vote: I like it
  • +67
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

top-25 or die

LOL

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Previous year champion has a wildcard?

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve Clarge?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 =\

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I have greedy solution, through it is quite complex

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D-small?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much!

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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).

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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! :)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for your answer!

      I look forward to seeing you in LA aswell!

      → Reply