vamaddur's blog

Google Code Jam 2019 Round 3
By vamaddur, history, 5 years ago, In English

(I'm mildly surprised at no blog post on the front page about this, but here it goes!)

Google Code Jam 2019 Round 3 will begin at 14:00 UTC. The top 25 participants will advance to the onsite finals in San Francisco!

Let's discuss (and rage about) the problems here after the contest is over!

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

Comments Comments (35)
| Write comment?
»
5 years ago, # |
  Vote: I like it +78 Vote: I do not like it

(I'm mildly surprised at no blog post on the front page about this, but here it goes!)

Translation: Oh look, free contribution!

GL&HF everyone.

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Scoaboard link please!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Wow, nobody solved D-hard? damn

I wrote about 400 lines and I think I would need about a 100 more -_-

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

    I didn't even try to solve it. I had more-or-less arrived at what the editorial described (but without the proof, and I hadn't thought about optimisations), but I would probably have needed at least another hour to code it.

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

Can someone break my solution to C-large? I am not convinced that it works, nor have I thought very hard about its correctness.

First, if an edge can only work in one direction, force it in that direction (irrespective of whether it's useful or not).

Now, for all remaining edges that can go in either direction, randomly assign a direction.

Now, while we haven't yet constructed a valid arrangement, pick a random edge that, if we swapped the orientation for it, would connect two currently disconnected components. Swap the orientation for it. You may not swap an edge twice. Report IMPOSSIBLE if you've swapped every edge or if you've somehow gotten stuck.

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

    In fact, my solution is even simpler, and I think that it is correct: add edges as long as they connect different components of the same color, then check.

    I think that it is correct because, to isolate a group of cells, you need to build a cycle of opposite color. But if you only connect cells from different components, you never build cycles.

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

      This is what I had too. You need a little more work to prove it correct though: You can still isolate some color using a path of the other color and the border of the grid.

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

        If this happens, you cannot connect both colors, so the answer is IMPOSSIBLE.

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

Is there any Stack Memory Limit that I don't know about? I'm doing D&C in the second one and getting RE and can't see why

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

    I got RE in B for the same reason (I would have been in the top 25 otherwise :(). The stack size is 64MB, which is not sufficient. (My solution would work for $$$n \le 3 \cdot 10^5$$$)

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

      64 MB for google...I'm sorry, man

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

        >mfw stack limit is just something I set in a linker script

        I don't mean in competitive programming though.

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it
Troll solution to C
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you make it $$$O(R^2C^2)$$$? I also implemented this solution. There are $$$O(RC)$$$ edges — matroid elements. Each iteration is a BFS on a complete graph, and there is linear number of iterations in worst case, giving $$$O(R^3C^3)$$$. Am I mistaken somewhere or you have better intersection algorithm?

    I managed to pass only the small group and have unknown WA on large btw.

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

      OK, my analysis was stupid, I somehow remembered that it was $$$O(E^2)$$$. Now I feel bad at myself...

      I think we need some intuition from the model solution to make it work. As most edge updates are fine, we can actually expect the graph to be sparse and have a short augmenting path.

      FYI, My implementation: https://ideone.com/n14QX5

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

    I didn't even bother writing it because I was sure it would be too slow. :(

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

    C is the only problem I can come up with correct idea, but it's like 9 — 10 second late to write the full code so sadly, my score is the big zero. The idea is simple : create the dsu of As squares, two adjacent squares belongs the same set. Note that we only need to create fence for 2 x 2 squares like "A, B, A, B" or "B, A, B, A" clockwise. So if there are two As in that kind of 2 x 2 squares and belong to 2 different sets, we create fence between them and merge 2 sets. So in the end, if we can connect all set of A then topologically, it will look like a tree with nodes are the connected components of the adjacents As squares with the fences are the edges. So it will contain no cycle, no B square can be surrounded by a cycle of the nodes and can always find a way to connect with other B square by some paths and fences.

    Actually, I realized that I cannot make it anyway so I spended only last 30 mins to think and code this. Even so, now I really regret.

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

looking at the statement of the first problem

dat feel
→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Damn, that was a tough contest. How to solve A,B,C and D?

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

    You can read official editorials.

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

      With all the "robotic intuitiveness" of the new interface, it took me a few good minutes to actually find the editorials. If, by any chance, someone is struggling to do that too, here's how.

      The "Show round overview" toggle at the top (small and not clearly visible) doesn't help. Instead, you have to open a problem. Then, scroll down your attempts, down to the problem statement. Below the attempts, but above the problem statement, there are actually two tabs: PROBLEM and ANALYSIS (small gray font, not clearly visible).

      Me and the designer clearly live in two entirely different universes.

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

Thanks to the problem authors!

Problem A reminded me of my own problem from an Opencup round on October 2014 (roughly a 2D version of this). The statement is basically this:

There is a rectangle (16x16 to 25x25) on a square grid. Two players put 2x2 squares in it. The player who can't make a move loses. The jury player moves randomly. How to win most of the time?

Here's a comment with the 2D version solution.

Today, I used a similar idea: As long as there are long segments present, try to make many segments with Grundy value 2. When there are only short segments left (Grundy values 1 and 2), pick a move to make the total Grundy value equal to 0. Or a random move if it is 0 already. Update: Code is here.

However, I'm sure there was some easier approach today, with the problem being open-ended.

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

I had a different solution to C. The implementation is a bit more difficult, but I think it's interesting.

First I checked the border for the case that makes it impossible, as in the official analysis. Now suppose there is at least one B on the border (if not, swap all A's and B's). Draw an edge between two adjacent cell corners if there is an A on exactly one side of the edge. Now find an Eulerian cycle of the edges, being careful not to cross over one's own path. The "inside" of this cycle is now all the A's, and diagonals should be connected up such that the cycle does not cross the diagonals.

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

    how do u come up with such complex solutions.

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

      I have vague memories of some other problem that made use of cycles of edges connecting cell corners to define components in a way that allows one of each pair of diagonals to be treated as connecting components, but I don't remember any details.

      I did feel pretty stupid after reading the editorial since I'd had basically all the ideas I needed to see the official solution but didn't connect the dots (excuse the pun). But in fact the code is not too bad.

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

        This problem seems slightly related.

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

          Maybe, but it's not the one I was vaguely recalling. I think it was a TC problem, and I don't think it was related to mirrors. It's even possible that I'm conflating multiple problems.

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

            Maybe this one?

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

              Might be one that influenced my thinking, but I also have some vague memories of a max-flow/min-cut.

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

I think my solution to B-large is even simpler than the second one from the editorial, although it is tricky.

We will count the sum of all heights of stacks among all possible non-empty pyramidized intervals — since the original sum can be easily subtracted, that is enough.

Consider the contribution of stacks that rise to $$$P[i]$$$ (WLOG heights are different). Let $$$next[i]$$$ be a smallest index greater than $$$i$$$ s. t. $$$P[i] < P[next[i]]$$$.

Then, if $$$R \ge next[i]$$$, $$$L$$$ must be between $$$prev[i]$$$ and $$$i$$$ and all stacks from $$$i$$$ to $$$next[i]$$$ rise to $$$P[i]$$$. Similarly for $$$L \le prev[i]$$$. If $$$prev[i] < L \le R < next[i]$$$, then only $$$P[i]$$$ rises to $$$P[i]$$$.

All in all, We have a nice $$$O(1)$$$ formula and from now on, the solution is straightforward.

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

    I think this ends up being equivalent to the O(S) solution from the editorial, just with some of the arithmetic shunted around because you're computing the total sum of heights rather than height differences. It does sound like that makes things slightly simpler though.

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

Screencast

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

I just got my t-shirt yesterday (Friday 8/16/19)! PSA to be on the lookout for yours coming soon!

→ Reply