Geothermal's blog

GCJ Farewell Round Discussion
By Geothermal, history, 19 months ago, In English

Posting since there isn't a thread yet. Discuss the GCJ Farewell Rounds here.

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

»
19 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Its over :(

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

It really sucks that they discontinued the competitions, they were always quite fun...

Also can I just say, that last problem on round C was kinda hot trash lol

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

    I was shocked by how easy the last problem on round C was, it was in some ways similar to a Div2C. Lots of casework. Casework aside, it seemed easier to me than the first problem of round C. The only difficult part, I suppose, was seeing that the simple approach for P=3 just works (that is, you never run into some issue like AC|AB|B).

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

This was the first contest of my life. I was just solving my first few problems on this site earlier today when I remembered that GCJ was supposed to be held today. So I immediately switched over to that page, just a few minutes before it was supposed to start. I had forgotten to have dinner earlier so I had to eat in the middle of the contest lol It was a lot of fun, and I solved 2 questions of Round A. I spent 2 hours on the ASCII Art question, but failed to solve some corner cases. I got some 3000ish rank.

So this is what contesting feels like.

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

The Round D was beyond my expectation. I was really moved by the problems and the contest itself: "GCJ is truly one of the most successful competitive programming contest ever".

Especially I love the 3rd problem "Hey Google, Drive!". As my preference I like problems with solution like "eliminate until the state has no problem", and this problem was one example. Not only that, I felt that this problem drives this technique in a non-intuitive, brilliant way.

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

    "Hey Google, Drive!" is my favorite from all rounds too, one of the nicest I've seen in a while. Almost all the difficulty is idea difficulty, having simple clean implementation, yet you do not feel "tricked" as in some other problems like that, where after reading the editorial you feel like "How could have such an idea occurred to anybody?". Here, it feels quite natural, like "oh, why didn't I think about that?" (its clearly the one I could not solve, too :P).

    Kudos to the authors!

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

I'm glad to have redeemed myself on this round after barely missing the last few GCJ finals by a couple of minutes (though reducing my penalty time by a few minutes would have gotten me third place, so I guess my streak of missing a meaningfully better rank by a handful of minutes continues :p).

Also, I'm really not sure why a nontrivial number of IGMs/LGMs were smurfing in rounds A/B? Seems kinda silly to pass up an opportunity to compete against many of the best CPers just to speedrun problems vastly below your skill level...

Feedback on the tasks:

A: Not too bad a problem, but it felt fairly standard since the main step is computing the sum of each vertex's distances to the other vertices in the tree. I probably wouldn't consider this suitable for an actual finals since most high-level competitors have seen exactly this idea before.

B: Good problem--it was obvious that we need to handle queries offline, but it took me a while to realize that the most convenient way to do so was to sort the suffixes and prefixes rather than to just iterate in increasing or decreasing order of suffix length. Solving this problem definitely improved my intuition for working with string suffix structures; thanks to the authors!

C: Interesting setup, but I wasn't a fan of how the full solution is essentially "guess that the 26(NM)^2 solution has a really good constant factor". To be fair, this is reasonably intuitive, but I don't have a rigorous sense of why it's true and the editorial doesn't communicate any intuition for why a solution whose big-O expression evaluates to 2.6e9 should run in 0.6s per test case.

D: Solid problem. A bit caseworky, but the idea was interesting and there was a clever way to make the implementation less painful than it otherwise could have been. I don't like that there wasn't a sample case indicating that there must be at least one gold point; I lost eleven minutes of contest time and fifteen penalty minutes overall by not reading this case (I know, I know, skill issue, but still, I generally prefer problems to include sample cases that highlight any potentially unexpected parts of the problem statement so that programming contests don't turn into reading comprehension tests).

E: Fine problem. I figured it had to be harder than the rest of the round and thus didn't read it until after solving E, but upon reading it it seemed like the most obvious construction should work. Building the ring was a bit more annoying than I anticipated since a bit of casework is required, but it wasn't too bad overall.

Thanks to the authors!

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

The intended complexity for problem D of round C is $$$\mathcal{O}(k\cdot (n+m+q))$$$, but it can be solved with a similar idea using dynamic connectivity in $$$\mathcal{O}(m\cdot \log(n)^2 + q\cdot \log(n))$$$. This solution also has a small constant, so $$$n$$$, $$$q$$$ and $$$m$$$ could be $$$2\cdot 10^5$$$ and it would still be fast enough.

Also, in this idea you can forget about the constraint on the amount of colors. So $$$k$$$ could potentially be equal to $$$10^9$$$ and the solution remains the same.

Here is my code :)

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

    It looks like you're using $$$O(m \log^2(n) + qk \log(n))$$$ time, since you check every query pair against every possible missing color. Do you have a way to avoid that? Otherwise, you could also achieve this without fully dynamic connectivity using offline div-conquer on union find with rollback.

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

I am happy about my performance in round D. Sending the solution to problem E without checking locally if it worked (and the previous iteration was not working) 30 seconds before the end of the round and getting accepted was very satisfying.

Here is my feedback on the problems:

  • A:Standard. I had to read it multiple times because I thought it was too easy for this round.
  • B: Boring suffix-structures-based problem.
  • C: I really enjoyed this one. One of the best problems I have solved recently. I had to think for 45 minutes and then the implementation was immediate. Not only the solution is cool, but the statement feels very natural and interesting.
  • D: Okayish. It is clear from the get-go that it is a dynamic programming and the point is computing the answer as the sum, over multiple ranges, of previously computed answers. Then identifying the correct ranges and not messing up the implementation was hard for me.
  • E: The problem is not interesting as the obvious construction works. Then I did some awful tricks to find the Hamiltonian cycle. With a few more minutes maybe I could have come up with a cleaner reconstruction.

Thank you to all the organizers of codejam.

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

    Did you have a particularly compelling reason to expect your C to work? I assumed my solution would pass only the small cases and submitted right before time ran out after giving up on getting full points.

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

It was claimed that Round C is harder than a Code Jam Round 2 but easier than a Code Jam Round 3, but today it seems somehow like a Kick Start Round.

Still really thank all the organizers for presenting such a brilliant competition during the long time.

Goodbye my old free-shirt-asking days.

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

How I solved Round A
How I solved Round B

Railroad Maintenance is my favourite in this set.
Thanks to the organisers. I enjoyed solving codejam and kickstart rounds.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 3   Vote: I like it +18 Vote: I do not like it

    While testing the problem in internal rounds, a good number of people of many different ranks also used dynamic connectivity (dsu rollback) to solve Railroad Maintenance. It surprises me how extremely well known that technique has become nowadays, compared to some 5-10 years ago!

    The expected solution is the one in the analysis: create bipartite graph of lines vs stations, where a line is connected to all its stations. It is nice to note that this graph is pretty natural for many questions involving train lines, not only the one in the problem. For example "train-combination-distance" queries between two stations now become normal graph distance queries. And the Railroad Maintenance problem answer is simply number of "line nodes" that are articulation points.

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

My initial plan: AK round A -> AK round B -> Solve round C as many problems as possible and solve one round D problem.

Actually: AK round A -> get stuck on larger test case of last two problems of round B -> Only 20 minutes left, AC the third problem just 10 seconds before the contest end.

Finally, Thanks Google for providing such a wonderful contest.

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

I didn't see there is a $$$5th$$$ problem in the round $$$A$$$. Solved only 4 (which were fit in the screen) and moved to Round $$$B$$$ and could solve only 2 there.
Anyways enjoyed a lot (was tired though with CF and ATC).

Thank you Google for the amazing era!

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

    similar here i also didn't see the 5th problem in round A

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

My initial plan: AK Round A -> AK Round B -> [?] Round C -> [?] Round D

I was very satisfied with my performance in round A, although needless to say there are many strong participants who went directly to round C/D.

In Round B I got stuck on the second problem for over an hour simply because I never learnt how to find $$$k$$$ such that $$$z \equiv kd \pmod n$$$ given $$$z, d, n$$$ and $$$\gcd(d, n)=1$$$. Or maybe I am supposed to figure out that myself during the contest. Although finally I did figure it out after solving all the other problems in round B and solving the first problem in round C.

Then, I stopped attempting the rest of the problems.

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

Maybe you already found out, I did just now and I thought it is worth to share.

At the end of the "Round Overview", after the touching (and hopeful) quote from "Volver" of Gardel and before the list of authors, there are 3 mysterious test case inputs.

I found out they are respectively of "ASCII Art" (Round A, the one with Cody Jamal), "Game Sort: Part One" (Round C, probably the last Google sort ever) and "Hey Google, Drive!" (a fantastic problem as already commented). If you run them with these inputs, and you put together the outputs in this order, you get:

KEEP CALM AND CODE ON

So funny, nice final Easter egg. A conclusion (the quote and this hidden trick) with a quality at Code Jam level.

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

    Damn, that's one hell of an easter egg. I missed that input initially and moved past that when reading the overview. Thank you for sharing this.

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

The round overview ends with : Last words are always hard, so we can borrow from Gardel the ending of "Volver" that does fit the moment: "I save hidden a humble hope, which is all the fortune of my heart."

The team is hopeful that Google Coding Competitions can return someday in the future :)

→ Reply