Currently the contest starts in ~45 min and I've found no blog about it, so I created one.
Contest link: https://codingcompetitions.withgoogle.com/codejam/round/00000000008779b4
This is my first time participating in Round 3. Good luck to everyone! And feel free to discuss the problems after the end of the round.
UPD: I actually ranked #500 (preliminary rankings), pretty happy of my performance. And I got all my points in the first hour :).
It's also my first time to participate, Good luck everybody!
UPD: Got 551, lower than round 2 ranking, so sad.
By the way, anyone else thinks this contest is easier than Round 2, especially the first problem? Although I did pretty bad.
Problem A: I just split them into cycles, and assigned the cycles the same value, got 18 points, since the last test case is only 3 points so I gave up furthering optimization.
Problem B: Realized it was a segment tree problem, but I just brute-forced the small test case using the sliding window. Then I saw so many people passed problem C and I decided to turn to problem C.
Problem C: Tried recursion, TLE. Then I thought maybe there are many solutions and constraints were limited, so I tried random initialization, TLE again. Waste so many time on it.
Solved C shortly after the contest, the judgement of self-loop is simple. After that, first, transfer the directed graph to non-directed graph, then for each color, maximize number of nodes that can be colored, using BFS. If it cannot be fully colored within 13, output impossible. This is very similar to one contest problem I have ever done, but I cannot find which problem.
Problem D: Saw only a dozens of people passed, and didn't have a look at it.
Finally got 30 points, lower than round 2 ranks. I am wondering if this is round 2, and I need to be top 1000 to enter round 3, then I will not even pass the round.
I did pretty much the same thing. Tried thinking about C and D for a while but didn't figure out the solution.
A was very nice though. But I didn't get the last 3 points (which I also kind of gave up).
I don't think this randomized solution for C was intended to pass but it worked for me. It even passed the large version.
IMPOSSIBLE.IMPOSSIBLE.How would we make hack data that might kill this solution?
It was my first time too participating in Round 3. Got 532nd rank. For problem C, Tried optimising the randomised solution for more than an hour but TLE. Overall, enjoyed the contest.
I believe it's actually quite easy to find a tree for D with a grundy value of 0 by trying random trees with sufficient hashing, just using the following optimizations:
If we just try random trees, created by trying an edge uniformly at random and adding it if it's not yet a tree, we find solutions very quickly. Perhaps this isn't good enough for a judger against antagonistic trees, but against uniformly random trees, it seems safe. Furthermore, it seems reasonable that it's legit to expect a small number (< a few thousand) of missed trees since as there aren't that many nodes here, the grundy numbers seem likely to stay rather small.
I wrote a naive version of your algo, it took me eternity. Not easy implementation-wise
Took eternity to write or to run?
Write. It's not that fast, but somewhat endurable
It's enough to try binary trees. That guarantees a small number of possible moves. (For every node, I randomly decided if it should have 1 or 2 children.)
The implementation is time-consuming anyway. And I didn't even do centroids. Just rooted a tree anywhere to compute the hash (by sorting hashes of children) — so possibly redid computations multiple times for the same tree.
Cool! I'm thinking about how to prove that for every N, there's at least one binary tree that satisfies the conditions.
But then for N = 40, $$$C_40$$$ is super big! Perhaps using some kind of heuristics could help optimize it, so that the tree is found in a a small number of moves.
Interesting, I used grundy values to brute-force a tree structure I had in mind but it was wrong.
We could have used meet in the middle to generate all grundy values for trees of size N = 13, 14, 15. And then try combining them to form N = 30.
Actually this wouldn't have worked for N = 40 as brute-forcing all trees of size N = 20 is too big. So then we have to do the divide and conquer.
It took me like 5 seconds to come up with the solution of C-large, but the tests of C-small are trash, so my code passed it even though the implementation was completely wrong.
I'm not trying to brag about anything. The problem is just a knowledge test on graph coloring. Because of the problem quality, I'm not sad about missing virtual finals at all...
I won't write this if my elimination to finals doesn't depend on this.
During the contest when I pressed submit button, 4 of 5 my submissions were duplicated with same code and submit times with less than 10 second difference. This costed me two extra penalty, for problems B and C and without this bug I am in top 25 in current standings. I know at least two participants faced the same bug but it happened with less probability. I already submitted bug report to codejam@google.com and hope they will review submissions.
It wasn't hard to get O(N^2) pass in B. The heavy operations are: - Increment or decrement on a range - Count the number of times a specific value occurred on a range.
With avx2 that's almost 8x optimization.
Isn't that specific value always the minimum on this range? In this case you can do just one more simple step to turn that into a segtree.
Is there someone who can help me understand how to implement B-large starting from a default segment tree code? I read the analysis and did some research but I am still stuck. Basically I am not sure how to concurrently implement both the functions to: (i) count number of occurrences of max values; and (ii) lazy update on ranges, in O(lg n) time on the same tree.
I read that to perform (i), you basically store (value, #occurrence) in each node instead. I think I can implement that where the combining function is (max, custom function to figure out occurrence).
On the other hand, I read that to perform (ii) on a tree where you store only values in nodes, you store the value to be added at certain nodes and only "push them down" when you need to make queries.
But if my nodes store (value, #occurrence), how do I push the value to be added down nodes while update #occurrence correctly? Or am I overthinking about things? Thanks much!
If you add (increment) to all elements represented by a node (value, #occurrences), you get (value+increment, #occurrences): Every occurrence of (value+increment) after the update has to have been an occurrence of (value) before and vice-versa. Hence #occurrences doesn't change.
Btw just curious if anyone has received their Code Jam T-shirt already? I submitted the details on the delivery webpage about a month ago and still waiting for it (eagerly :p)
Are you still waiting for it? I submitted the address via a form at the end of June. Then several days ago I asked them via googleswaghelp@canarymarketing.com, they said it did not went through (I was supposed to receive a confirmation or something) and there would be no more product to ship to me. This is unfair.
I managed to receive it earlier this month (August). Sorry to hear about your story! :(