TimonKnigge's blog

Google Code Jam 2020 -- Round 3
By TimonKnigge, history, 5 years ago, In English

Just a reminder that GCJ Round 3 is about an hour away. I don't think there was a reminder email and I only just realized this, hopefully this will save some of you too :-)

Dashboard link

EDIT: Round is over, can discuss now.

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

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

How to solve problem C: Pen testing ?

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

    Way to increase probability: We want to find an empty pen. Let's try pens in random order. Empty one will be approximately in the middle. After that choose 2 pens that you haven't tried.
    I got accepted 2 subtasks with looking for pens 0, 1, 2, 3.

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

    I got the first 2 subtasks by a sort of iterative deepening search.

    • First try each random pen once until you hit empty one.
    • Then try each random pen twice until you hit empty one...and so on (three times, four times...)
    • Of course, you should start by trying pens you've already tried in previous rounds but are not empty yet (and keeping track of cumulative tries).

    I roughly simulated the percentage of success, and stopped when percentage was high or I found ~4 or 5 pens. These parameters were somewhat trial and error.

    Got me to around 62.4%, couldnt get to 63.3% for the last subtask.

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

How to approach Problem B?

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

Who knows what happened to the standings? The hidden verdicts were shown for a little period of time and now they are invisible again.

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

    Now it's good. Seems to be a short-timed issue.

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

The unofficial list of finalists:

  1. tourist Gennady Korotkevich
  2. Benq Benjamin Qi
  3. ecnerwala Andrew He
  4. VivaciousAubergine
  5. gs12117 Seokhwan Choi
  6. ksun48 Kevin Sun
  7. RomaWhite Roman Bilyi
  8. ainta SeungHyun Joe
  9. KAN Nikolay Kalinin
  10. LHiC Mikhail Ipatov
  11. SnapDragon Derek Kisman
  12. eatmore Evgeny Kapun
  13. ATS
  14. goffrie Geoffry Song
  15. sevenkplus Yuzhou Gu
  16. scott_wu Scott Wu
  17. yutaka1999 Yuta Takaya
  18. saketh Saketh Are
  19. Jacob Yakov Dlougach
  20. 300iq Ildar Gainullin
  21. AndreySergunin Andrey Sergunin
  22. ikatanic Ivan Katanic
  23. ohweonfire Sunli Chen
  24. ko_osaga Jaehyun Koo
  25. FizzyDavid Junzhao Yang
→ Reply
»
5 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Thanks for the interesting problem C in particular.

And a separate thanks to Petr for problem C analysis! In addition to showing a few approaches to the problem itself, the analysis contains a detailed writeup on judges' considerations when setting a probabilistic problem.

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

Had a roller-coaster with C after the contest.

  • Wrote a simple DP over bitmasks for sizes of pen with 3 moves (take 2 random, remove 1 learning its size, try all pens removing 0 if it was present).
  • This gave around 69% so expected to get all three.
  • Coding this was a pain because of merged test cases.
  • Had bugs, couldn't debug in time.
  • Saw that A + B1 + C is enough for WF.
  • FFFUUUUUU.
  • Shortly after the contest re-read the statement and found that the only bug was that I thought pens' initial capacity were from 1 to N rather than from 0 to N-1.
  • FFFFFFFFFUUUUUUUUUUUUUU.
  • Submit during practice.
  • WA on C3.
  • A + B1 + C1 + C2 wasn't enough anyway. MASSIVE RELIEF.
  • Rerun locally, with reducing the amount of ink in pens, it's now 60.44%.
  • (facepalm) (facetable)

Conclusion: after all those years I still haven't learned to read problem statements.

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

I think there is a (very minor issue) with the editorial of C-small:

The distance between two strings of length up to 6 is at most 6, since we could just replace every character in the longer string (or an arbitrary one, if they are of the same length) to match the other string, and delete any excess. Moreover, the distance between two strings is never less than the absolute difference in length between them, because we would need to add at least that many characters to the shorter string (if one is indeed shorter) just to make it as long as the other string. It follows that the output should never be longer than 12 characters. Notice that it is possible to have a solution of that length, e.g., XXXXXXYYYYYY is an acceptable solution for a case with the names XXXXXX and YYYYYY.

The last sentence is false, since the path through XXXXXXYYYYYY has length 12 whereas the answer is 6. As mentioned in the first sentence, $$$d(P, Q) \leq \max(|P|, |Q|)$$$. So the longest string $$$L$$$ that we could visit in any optimal solution has satisfies $$$(|L|-|P|) + (|L|-|Q|) \leq d(P, L)+d(L,Q) \leq \max(|P|,|Q|)$$$ or $$$2|L| \leq |P|+|Q|+\max(|P|,|Q|)$$$. So for the input limit of 6 this means no optimal solution visits a string longer than 9 characters.

EDIT: For AAABBB and BBBCCC, a valid output would be AAABBBCCC.

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

Problem A is fun when one has levenshteinDistanceAndPath in the standard library, doing half the work.

For example, in the first case XYZZY ZZYZX, it gives distance and path as
Tuple!(uint, EditOp[])(4, [insert, substitute, none, none, remove, substitute]).

Didn't ultimately help though, as I was too bad at all the other problems.

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

Fun fact: jqdai0815, whose GCJ ID is "xll114514", failed B large only because his "x" array is not "ll"(=long long according to his typedefs).

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

    No #define int long long? Typical rookie mistake

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

    I'm curious how tmwilliamlin168 didn't clear this round, he is so fast and precise as seen in previous rounds of codejam.

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

Does anyone know what was rotavirus's handle?

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

I don't think there was a reminder email

anyone else miss the round?

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

Don't know about others, but I really felt very sad after watching Errichto 's GCJ stream :( .

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

Huh, B was solvable in O(n^2)? Seems weird that they decided to set $$$n \le 100$$$ in that case. I had $$$O(n^3 \log n)$$$ (could be optimized to $$$O(n^3)$$$ with a little hassle). Possibly they were aware of it and decided to let it pass, but no mention of that in editorial. My solution was in style "we can assume that some object is in one of interesting positions and there is finite number of them". Let's consider a solution and shift some thermometer and ones that are "connected" with it through sequence of symmetries up to the furthest possible point where structure doesn't change. That is, so that for some thermometers it holds that its position is either $$$x_i-1$$$ or $$$x_i+1$$$ (I multiply coordinates by 2). Points that become if interest are results of consecutive symmetries of such points through given points and there are $$$O(n^2)$$$ of them in total. I fix position of one thermometer on one interval in $$$O(n)$$$ possibilites and for each of them I consider simple dp with $$$O(n^2)$$$ states (implemented on map). There is one special case — when n is odd and the answer is n. Fortunately it was featured in samples which was life-saving.

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

    My solution is $$$O(n^3)$$$, but I think it can be solved in $$$O(n \log n)$$$. I don't want to verify this though.

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

    I just got accepted in practice with O(N) actually. If you read their solution it basically says to pick each of the N intervals as a starting interval of positions for the first thermometer and mirror the interval / reset the interval & add 1 to the count until you get back to the start — which is O(N). However, you are guaranteed to reach a valid solution as long as you pick a starting interval that works if you only put one thermometer. Combine this with "you don't need 2 consecutive intervals with 2 thermometers" and you only need to check 2 consecutive intervals as starting points.

    → Reply