(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!
Translation: Oh look, free contribution!
GL&HF everyone.
Scoaboard link please!
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051707
Wow, nobody solved D-hard? damn
I wrote about 400 lines and I think I would need about a 100 more -_-
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.
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.
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.
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.
If this happens, you cannot connect both colors, so the answer is
IMPOSSIBLE
.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
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$$$)
64 MB for google...I'm sorry, man
>mfw stack limit is just something I set in a linker script
I don't mean in competitive programming though.
It's a simple matroid intersection. Time complexity is $$$O(R^3C^3)$$$ with big constant factor, but it passed XD
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.
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
I didn't even bother writing it because I was sure it would be too slow. :(
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.
looking at the statement of the first problem
Damn, that was a tough contest. How to solve A,B,C and D?
You can read official editorials.
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.
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:
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.
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.
how do u come up with such complex solutions.
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.
This problem seems slightly related.
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.
Maybe this one?
Might be one that influenced my thinking, but I also have some vague memories of a max-flow/min-cut.
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.
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.
Screencast
A much worse Screencast. EDIT: Youtube ate my video; posted new one.
I just got my t-shirt yesterday (Friday 8/16/19)! PSA to be on the lookout for yours coming soon!