fvogel's blog

Google Code Jam 2022: Round 3
By fvogel, 22 months ago, In English

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

Tags gcj
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
22 months ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

It's also my first time to participate, Good luck everybody!

UPD: Got 551, lower than round 2 ranking, so sad.

→ Reply
»
22 months ago, # |
← Rev. 4   Vote: I like it -7 Vote: I do not like it

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.

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

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

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I don't think this randomized solution for C was intended to pass but it worked for me. It even passed the large version.

    1. First, filter out cases where there exists a 2-node cycle ($$$A \rightarrow B \rightarrow A$$$) since the answer for this case can only be IMPOSSIBLE.
    2. Assign random values in range $$$[1,13]$$$ at $$$a_i$$$ for all $$$N$$$ nodes.
    3. Loop until we don't exceed time limit:
    4. Check all $$$N$$$ nodes and for each node $$$i$$$ if it violates the condition ($$$a_i=a_{L_i} \lor a_i=a_{R_i} \lor a_i=a_{L_{L_i}} \lor a_i=a_{R_{L_i}} \lor a_i=a_{L_{R_i}} \lor a_i=a_{R_{R_i}}$$$), assign new random value at $$$a_i$$$. Do not stop until you check all $$$N$$$ nodes.
    5. If there were no violation on 4, print the answer and finish case. Otherwise, continue the loop.
    6. If it didn't find any solution within time, print IMPOSSIBLE.

    How would we make hack data that might kill this solution?

    → Reply
»
22 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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:

  1. We'll only process isomorphic trees once (or perhaps twice) by hashing from the centroid. Once we root at the (or one of the two) centroids, we sort our kids, and then process one at a time.
  2. We can process all transitions between two states with the following algorithm in about n^2 time:
  • Brute force the center node. For this node, we'll need to consider all subsets of adjacent verticies to potentially remove.
  • Store a hashset of the xors we have been able to hit. Then, when we process the next adjacent node, we'll either remove it, (and get the xors of all it's neighbors), or not remove it and get the value of it's subtree, which we'll calculate recursively.

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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I wrote a naive version of your algo, it took me eternity. Not easy implementation-wise

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

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

      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.

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

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +121 Vote: I do not like it

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 [email protected] and hope they will review submissions.

→ Reply
»
22 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

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

    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.

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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!

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

    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.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    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 [email protected], 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.

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

      I managed to receive it earlier this month (August). Sorry to hear about your story! :(

      → Reply