How to solve problem C: Pen testing ?

How to approach Problem B?

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

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

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.

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.

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.

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.

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

Does anyone know what was rotavirus's handle?

I don't think there was a reminder email

anyone else miss the round?

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

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.