### ibra's blog

By ibra, 5 years ago, translation,

In the very beginning of this post I would like to thank everyone who contributed to make this contest happen — both onsite and online versions. For many of us it was practically the first contest we really took part in preparing of — we all loved working on it and hope you liked it too.

I would also like to mention that 2864 teams (about 4k people!) registered to this contest, 1025 actually took part in it, 637 managed to solve at least one problem and there were 4 teams that solved all the problems before contest ended. Congratulations to everybody! Ok, so here is top 10 of Codeforces version of Bubble cup:

 1 tourist 2 Nizhny Novgorod SU: mike_live, vepifanov 3 SPb ITMO University 1: antonkov, enot110, subscriber 4 Dreadnought: TankEngineer, rowdark, BaconLi 5 nedrharmsw: AntiForest, rnsiehemt, JoeyWheeler 6 Orz!: zcz, KFDong, ExfJoe 7 -XraY- 8 Saratov SU Daemons: danilka.pro, Edvard, kuviman 9 Omogen Heap: Gullesnuffs, simonlindholm 10 Bsuir_power: andrew.volchek, teleport

All of them will get T-shirst. But apart from them, as we promised, there will be 10 T-shirts more sent to randomly chosen teams, here they are:

For those who are interested here is a link to results of onsite competition.

Since editorial is pretty big I think it is more reasonable to share link to file here than posting it all here.

• +82

 » 5 years ago, # |   +119 ".docx" T_T ..........There is a joke on UW that one particular of our professors has solved TSP problem, but he is ashamed to publish it, because he has written solution in .docx format
•  » » 5 years ago, # ^ |   +7 thx for comment, changed to pdf-file
 » 5 years ago, # |   +17 When I read the first entry about competition, I read it wrong, so instead of "10 t-shirts will be handed out randomly to other participants of the top 100", I read something close to random 10 teams from top 100 will get t-shirts.Later on, of course I realize my mistake, but now I'm very curious about implementation of this t-shirt algorithm. As far as I concerned, it's really hard to give 10 t-shirts to a random teams, that sum of team members will be equal to 10 and also satisfy the uniform distribution (of course you didn't said you will give t-shirts based on uniform distribution)Could you reveal some information on your random generator?
•  » » 5 years ago, # ^ |   +15 algo randomly picks a team and if we have enough T-shirts left we take that team, else trying to pick once more.
 » 5 years ago, # |   +12 H. Bots. It can be simply shown that the number of possible solutions is equal to . So it is needed to find.
•  » » 5 years ago, # ^ |   +1 I knew about this solution, but i didn't know how to prove it.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 Answer is , which is basically "square" from Pascal's triangle. To simplify this we can use "golf club theorem" two times which unfortunately I'm unable to find in Internet. It says . After marking involved summands you will understand why it's called golf club theorem :P.
•  » » » » 5 years ago, # ^ |   +5 I like other name more — Christmas Stocking Theorem :)
•  » » » » 5 years ago, # ^ |   +5 It's also known as the "hockey stick theorem".
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 Also known as Chu Shih-Chieh’s Identity, at least in my lecture notes :)
•  » » 5 years ago, # ^ |   +4 Or just precalculate first few numbers and search for the producing formula: https://oeis.org/search?q=1%2C5%2C19%2C69 )))
•  » » » 5 years ago, # ^ |   +1 It cannot be proof of statement.
 » 5 years ago, # | ← Rev. 3 →   0 good problems! But most chinese students can't use dropbox, sad...
•  » » 5 years ago, # ^ |   0 why solving it with HLD? LCA here is much more obvious. And much easier to implement
•  » » » 5 years ago, # ^ |   0 Yes, you are right. But for me, when dealing with path in tree , the first idea came into my mind is HLD.
•  » » 5 years ago, # ^ |   +16 Rehosted, in case it's useful: http://www.pdf-archive.com/2015/09/07/editorial/editorial.pdf
•  » » » 5 years ago, # ^ |   0 Thanks.It's very helpful.
•  » » » 5 years ago, # ^ |   0 I'm a Chinese student.Thanks for your sharing!
 » 5 years ago, # |   0 In problem H, can someone explain why most of the solutions include C(i, N) * C(i, N)?
 » 5 years ago, # |   0 H. Bots. What does "Number_of_duplicating_vertices_from_level" stands for? Is it number of vertices on level i each of which will produce two vertices on level i+1? Does C(i,N) stands for i choose N?
•  » » 5 years ago, # ^ |   0 yes
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 ibra, thanks, it must be I don't understand here something. If I look at trie for N=3 there is 6 vertices on level 3 that produce duplicates. But according to PD definition PD(3) = 2 * C(3,3) = 2. What I missed?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 thanks for comment, it is a typo.PD is number of vertices that do not duplicate (because they already spent all 0s or all 1s), and of course then, Count[i+1] = PD(i) + (Count[i]-PD(i))*2will correct it now
 » 5 years ago, # |   0 In the editorial for problem F, when it says "If x_turn is shining, then pos' is shining as well, so we could have finished our turn there.", isn't that only true if x_closer2 <= pos'?Also, how can we justify that it is optimal to stay at an endpoint when x_turn is not shining?
•  » » 5 years ago, # ^ |   0 Sorry if not clear enough, the only sentence about x_turn shining is "If x_turn is shining, then pos′ is shining as well, so we could have finished our turn there.". Other part of the paragraph is about x_turn not shining.And statement "If x_turn is shining, then pos′ is shining as well, so we could have finished our turn there." is always true. Take a look at the picture above that sentence. pos' and pos'' are the closest light-up endpoints to the x_turn, so the smallest interval of shining bulbs is at least [pos', pos'']. Rationale: if x_turn is shining and it is not the endpoint then one endpoint is left other endpoint is right...
•  » » » 5 years ago, # ^ |   0 Right, I didn't notice that. Thanks for the explanation.
 » 15 months ago, # |   0 For Tablecity I made a smaller version where you can do it yourself, I made it on a webpage, you can download it here
 » 14 months ago, # |   0 Was the solution file down? I can't open the Dropbox link. Can anyone upload a new one?