### TimonKnigge's blog

By TimonKnigge, history, 5 months ago,

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

EDIT: Round is over, can discuss now.

• +204

 » 5 months ago, # |   +45 How to solve problem C: Pen testing ?
•  » » 5 months ago, # ^ |   +23 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.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +13 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.
 » 5 months ago, # |   +19 How to approach Problem B?
 » 5 months ago, # |   +35 Who knows what happened to the standings? The hidden verdicts were shown for a little period of time and now they are invisible again.
•  » » 5 months ago, # ^ |   +8 Now it's good. Seems to be a short-timed issue.
 » 5 months ago, # | ← Rev. 9 →   +109 The unofficial list of finalists: tourist Gennady Korotkevich Benq Benjamin Qi ecnerwala Andrew He peehs_moorhsum gs12117 Seokhwan Choi ksun48 Kevin Sun RomaWhite Roman Bilyi ainta SeungHyun Joe KAN Nikolay Kalinin LHiC Mikhail Ipatov SnapDragon Derek Kisman eatmore Evgeny Kapun ATS goffrie Geoffry Song sevenkplus Yuzhou Gu scott_wu Scott Wu yutaka1999 Yuta Takaya saketh Saketh Are Jacob Yakov Dlougach 300iq Ildar Gainullin AndreySergunin Andrey Sergunin ikatanic Ivan Katanic ohweonfire Sunli Chen koosaga Jaehyun Koo fizzydavid Junzhao Yang
•  » » 5 months ago, # ^ |   +211 GO POLAND!!!
•  » » » 5 months ago, # ^ | ← Rev. 4 →   +61 If nothing will change, it will be the first time in the history of Google Code Jam (since 2003) with 0 finalists from Poland.
•  » » 5 months ago, # ^ |   0 Is KalininN KAN?
•  » » » 5 months ago, # ^ |   +55 Yes.
•  » » 5 months ago, # ^ |   0 Is saketh.are saketh?
•  » » » 5 months ago, # ^ |   +48 Yes!
•  » » 5 months ago, # ^ | ← Rev. 2 →   +38 SnapDragon 's name is Derek Kisman. A veteran that nowadays only competes in Google Code Jam. He has a youtube channel
•  » » » 5 months ago, # ^ |   0 Thanks, added.
•  » » » 5 months ago, # ^ |   +110 Thanks for the shout-out. :) My screencast of Round 3 is here.
•  » » » » 5 months ago, # ^ |   -72 You made all Candidate Master proud lol
•  » » 5 months ago, # ^ |   +9 Just curious: what was MiFaFaOvO's handle?
•  » » » 5 months ago, # ^ |   +3 And Um_nik's handle?
•  » » » » 5 months ago, # ^ |   -46 More information here.
•  » » » 5 months ago, # ^ |   0 MIFAFAVO didn't take part in codejam
•  » » » » 5 months ago, # ^ |   0 he did
•  » » 5 months ago, # ^ |   +44 Dlougach is me.
•  » » 5 months ago, # ^ |   +19 Can you please move gs12117 into correct (5-th) place? It seems their last second submission took some time to evaluate, and the first-released standings were incorrect.
•  » » » 5 months ago, # ^ |   0 Done, thanks for pointing this out.
 » 5 months ago, # |   +67 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.
 » 5 months ago, # |   +49 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.
 » 5 months ago, # | ← Rev. 3 →   +8 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.
 » 5 months ago, # |   +26 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.
 » 5 months ago, # |   +18 Fun fact: MiFaFaOvO, whose GCJ ID is "xll114514", failed B large only because his "x" array is not "ll"(=long long according to his typedefs).
•  » » 5 months ago, # ^ |   +26 No #define int long long? Typical rookie mistake
•  » » 5 months ago, # ^ |   -42 I'm curious how tmwilliamlin168 didn't clear this round, he is so fast and precise as seen in previous rounds of codejam.
•  » » » 5 months ago, # ^ |   +42 kickstart*
 » 5 months ago, # |   0 Does anyone know what was Eva's handle?
•  » » 5 months ago, # ^ | ← Rev. 3 →   +12 numb
•  » » 5 months ago, # ^ |   +8 I haven't participated
•  » » » 5 months ago, # ^ |   +3 Hey are you some sort of famous person? I have seen many people talking about you idk why.
•  » » » » 5 months ago, # ^ |   +29 I am some sort of famous for being a woman person
•  » » » » » 5 months ago, # ^ |   +28 and for being a jerk person in comments
 » 5 months ago, # |   +68 I don't think there was a reminder email anyone else miss the round?
 » 5 months ago, # | ← Rev. 2 →   +42 Don't know about others, but I really felt very sad after watching Errichto 's GCJ stream :( .
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 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. SpoilerConsider this problem in an interval, and moreover say that we only determine if answer = $n$ or not. We should find positive real solution $x_1, x_2, \ldots x_{n + 1}$ such that $x_i + x_{i + 1} = len_i$. This is $O(n)$. In a circle, you can do similar things to see if answer is $n$ or larger. Let's say the interval is valid if such a solution exists. If you can divide the circle to $k$ valid circular interval, then you can solve the whole circle with $n + k$ thermometer. If you solve each interval case with $n$ thermometer, the issue only arises where different intervals meet. At that point you can put one sentinel, to "pull" the result in the desired direction. This immediately gives $O(n^3)$ solution which I passed.Now from here, I didn't verify with AC. For each starting point $l$, you can find maximum $r$ such that $[l, r]$ is valid. They are monotonic in every way ($[l, r] \rightarrow [l + 1, r], [l, r - 1]$), so if you find such valid $r$ for all $l$, you can use sparse table (jump pointer) to simulate greedy in $O(n \log n)$, possibly with easier way but who cares.So the hardness lies in where you have to find the interval is valid or not. The simulation of procedure reveals that the answer does not exists if some term of $len_i - len_{i - 1} + len_{i - 2} - \ldots \le 0$. You can take this as a minimization problem, write DP form, and use segment trees.
•  » » 5 months ago, # ^ |   +11 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.
 » 3 months ago, # | ← Rev. 2 →   -8 Resolved