### niksmiljkovic's blog

By niksmiljkovic, history, 4 years ago,

Hi Codeforces!

It's our pleasure to announce the 10th edition of Bubble Cup. Bubble Cup is a programing competition organized by Microsoft Development Center Serbia (MDCS), and will be held this weekend. Contest will take place on Saturday, 2nd of September at 09:30 UTC, in Belgrade, Serbia. Live results will be available on the official Bubble Cup website (results will be frozen during the last hour of the competition). Winners will be announced at the closing ceremony.

Just like the two previous editions, this final will be followed by an online mirror competition on Codeforces. Mirror will take place on Sunday, 3rd of September at 10:00 UTC. Contest will last for 5 hours and ACM ICPC rules will be applied. It will be a competition for teams of 1-3 members. There will be at least eight problems.

We kindly ask participants of the onsite final to hold off discussing problems publicly until the mirror is over.

Contest was mainly prepared by employees of MDCS. We give our thanks to Nikolay Kalinin (KAN) for the round coordination, Mike Mirzayanov (MikeMirzayanov) and the team behind Codeforces and Polygon platforms. Special thanks goes to knightL for helping out with problem testing.

The contest will be unrated. The reason for this is because rules of this contest are not common for Codeforces. Also, it is only a mirror of an onsite competition.

Editorial will be available in the booklets section on the Bubble Cup website a few hours after the online mirror ends.

EDIT:
Here you can find mirror contests from the previous two finals:
Bubble Cup 8 — Finals [Online Mirror]
Bubble Cup 9 — Finals [Online Mirror]

EDIT #2:
The contest has started. You can see the live results on the Bubble Cup website.

EDIT #3:
Here are the results of the onsite finals.

The top three winning teams of the online mirror contest:
1. tourist, VArtem
2. zigui, molamola., dotorya
3. Um_nik, Kronecker
Complete rankings are listed on this link.

Congrats to all winners!

You can find contest editorial here.

EDIT #4:
Thank you for your comments. While our official and ainta's solution matched on the test cases provided we found out from the comments here that there are some edge cases we didn't handle correctly and don't know how to handle properly given the constraints. Because of that we decided to remove the problem from the set and reset all penalties people received from the incorrect submissions. Sincere apologies to everyone affected by this.

• +151

 » 4 years ago, # |   0 Auto comment: topic has been updated by niksmiljkovic (previous revision, new revision, compare).
 » 4 years ago, # |   0 I read on the official site that the onsite finals only allow C/C++/Pascal. Will the online mirror allow all the usual Codeforces supported languages (or at least Java)?
•  » » 4 years ago, # ^ |   0 It will allow all languages supported on Codeforces, atleast that was the case in previous years.
•  » » 4 years ago, # ^ |   +13 The online mirror will allow all languages supported by Codeforces. However, we can't guarantee that all problems will be solvable in each language.
 » 4 years ago, # |   0 Is it harder than normal CF contest???
•  » » 4 years ago, # ^ |   +7 Here is booklet of Bubble Cup 2016, it contain problems also: http://www.bubblecup.org/Content/Media/Booklet2016.pdf
•  » » » 4 years ago, # ^ |   -8 Tanks.
•  » » » » 4 years ago, # ^ |   +13 Blog post is updated with the links to the previous two Bubble Cup mirror contests.
•  » » » » » 4 years ago, # ^ |   -8 tank you.
 » 4 years ago, # |   +3 Is was contest rate plz I need now teechr will fail my?
 » 4 years ago, # |   +27 Will there be T-shirts like last year?
•  » » 4 years ago, # ^ |   +12 Unfortunately, there will be no T-shirts this year. There are some custom laws that are complicating shipments from Serbia to Russia.We are working on finding an alternative way to provide T-shirts, and if do find it, we'll update the blog post.
•  » » » 4 years ago, # ^ |   0 The same for T-shirts for previous year? Maybe you can send them to other country? Please write me to PM if it is possible.
 » 4 years ago, # | ← Rev. 2 →   -31 Who will join this contest in spite of unrated, put like.
 » 4 years ago, # |   0 Auto comment: topic has been updated by niksmiljkovic (previous revision, new revision, compare).
 » 4 years ago, # |   -37 Is it rated?
•  » » 4 years ago, # ^ |   0 No.From the blog post:The contest will be unrated. The reason for this is because rules of this contest are not common for Codeforces. Also, it is only a mirror of an onsite competition.
 » 4 years ago, # |   -18 Bubble sort Cup, amazing!!!
 » 4 years ago, # |   -40 Is it rated?
 » 4 years ago, # |   -22 Upvote me or be bad at code!
•  » » 4 years ago, # ^ |   -11 Get upvoted cool kid
 » 4 years ago, # |   -23
 » 4 years ago, # |   -13 I as well would like to know in the fullist if this contest on the code force will count towards my codeforce rating on the codeforces.com webite on the internet on the wires that are inside the tubes that the internet is made of.
 » 4 years ago, # |   -24 Bad luck. Solution for A and C was correct. If these two got rated then.... Alas! they got skipped.
 » 4 years ago, # | ← Rev. 2 →   0 How many computers will teams have during finals ?
•  » » 4 years ago, # ^ |   +8 Each team will be provided with one computer.
 » 4 years ago, # |   -28 sorry but i have to ask is it rated?
 » 4 years ago, # |   +15 is it a team contest?if answer is yes so why we cant register as a team?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +21 Yes, the registration page will be updated soon to allow team registration.
 » 4 years ago, # |   +5 May I ask how to register as a team member? The register page doesn't have this choice.
 » 4 years ago, # |   +6 you think i will say "is it rated" ? No! i just want your downvotes lol
 » 4 years ago, # |   0 Where are final results?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 Radewoosh's team won, second place for Jagiellonian Armadillos from Poland and third place for Cheeks from Russia. From facebook.
•  » » » 4 years ago, # ^ |   -13 I know, I asked for detailed results
•  » » » » 4 years ago, # ^ |   +5 It's in the post you. Can't you read?
•  » » » » » 4 years ago, # ^ |   0 Results on site are before freezing. TOP3 had 9, 8, 7 problems respectively
 » 4 years ago, # |   -10 Team of tourist and VArtem opens the scoring...
•  » » 4 years ago, # ^ |   -14 Also me, but they kicked me from their team.
 » 4 years ago, # |   0 How to solve problem I?
•  » » 4 years ago, # ^ |   +21
 » 4 years ago, # |   +87 Guy who wrote this:should seriously urgently learn some math
•  » » 4 years ago, # ^ |   +13 Yes. I did and solved problem C in my team, but I got stuck at this symbol, and I throwed two questions... (I spent ~15 minutes to read this and understand the symbol, but overall the contest was good and fun.)
 » 4 years ago, # |   +33 How to solve A correctly?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 One could calculate dynamics d[x] for numbers <= 9 * 200000 + C how fast we could reduce x to one digit. Call numbers with d[x] >= 3 bad. If sum of digits of A0 is not bad all is ok. Let's take nonzero digits in A and remove plus after them (merge two digits in one two-digit number), if the new sum will be good we will stop, otherwise continue this process. On every step A1 will increase on 9x, 1 ≤ x ≤ 9. If in A0 there are n digits we could perform at least n / 2 such steps. One could calculate another dynamics on "bad" numbers and see that it will not help only for 379 and 388. If sum of A0 digits is 379 or 388 we will merge on the first step 3 digits and then do the same staff.
 » 4 years ago, # |   0 Will the problems be open to solve again soon?
 » 4 years ago, # |   0 How to solve F?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The solution is a(mCn + mCn - 2 + ...), a(mCn - 1 + mCn - 3 + ...), ...a(mC2 + mC0), amC1, amC0find the x s.t. and as it is prime, find modular inverse and calculate.
 » 4 years ago, # |   0 What's the intended solution for problem H? I've come up with a O(N 3 × K) solution. Is it fast enough?
•  » » 4 years ago, # ^ |   0 It is
•  » » 4 years ago, # ^ |   0 I also doubted that, but it ran in 826ms somehow
•  » » 4 years ago, # ^ |   0 I think There is an O(N^2 * K + N^3) solution (with preprocessing sorting-by-angle).
•  » » » 4 years ago, # ^ |   0 Wow, that would be great, can you elaborate?
•  » » » » 4 years ago, # ^ |   +3 Sorry. I miscalculated time complexity :(
 » 4 years ago, # |   0 When can we submit codes after this contest?
•  » » 4 years ago, # ^ |   0 I was only a few seconds late :(
•  » » 4 years ago, # ^ |   0 You should be able to submit now.
 » 4 years ago, # |   0 Was the intended solution for B O(m4) polynomial multiplication?
•  » » 4 years ago, # ^ |   0 I have solution in O(n + m^2logl) so i think O(m^4) might be too slow.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Could you please elaborate?Edit) I got the solution you are referiring to from someone else. Thank you for your help.
•  » » 4 years ago, # ^ |   +13 How do you multiply two polynomials in m^4 :P?
•  » » » 4 years ago, # ^ |   0 The were polynomials of two variables.
•  » » 4 years ago, # ^ |   0 The way interpreted the problem was essentially to calculate where cpi is the number of times i appear in the array c for all (xi) s.t. so we tried to multiply the polynomials and sum over all the coefficients of xL - 1yM - k by multiplying them with the number of ways sa + cb + eb = k via counting sort.Could someone please help us with a better solution?
•  » » » 4 years ago, # ^ |   +3 Let's assume that costs from first city and to last city are zeros for simplicity. Then create a polynomial and calculate and take its x0 coefficient. You can do it in . You can very easily add costs from first city to that solution. To include costs to last city you need to take out one of middle layers and join it with last layer because if you go to some city in last layer you have already determined cost to last city (as opposed to costs from first city to first layer where city you're going to from first city has no influence on next cost).
•  » » 4 years ago, # ^ |   0 Solved it in O(m^3logL+N) using matrix multiplication.
 » 4 years ago, # |   0 can someone explain how to solve problem A correctly?and btw what is the 6th test case ..
•  » » 4 years ago, # ^ |   +1 A simple greedy of putting them all into single digits does not work. Say for example we have(something) + 1 + 3 + 4 = 66 -> 6 + 6 = 12 (so impossible)but if we do(something) + 134 = 210 -> 2 + 1 + 0 = 3 (so possible)I expect TC6 to be an example of this.
•  » » » 4 years ago, # ^ |   0 thanks :)
 » 4 years ago, # |   +10 It wasn't so cool to waste a hour with correct but not very optimized solution for I. What was the purpose to set TL to 2s? Is your solution too?Anyway well problems :)
 » 4 years ago, # | ← Rev. 2 →   0 Is it possible to solve D without binary search. Like adding edges in sorted order and updating flow? I submitted that code but it got TLE. I don't know is it correct or why it got TLE.Edit: Not B, D.
 » 4 years ago, # |   -10 For D — Exploration plan,My submission of D is using Binary_Search together with MaxFlow, but WA on test 6. My SubmissionHowever, it seems many accepted solution divided a single node into two group.First group is attached to the source. Second group is attached to the sink. And then add edge with the constraints of Binary Search, like add_edge(i, j + n)So I want ask that "is there a way to construct the graph without dividing the vertex?"It is something like add_edge(i, j).Thank you!
 » 4 years ago, # |   +80 Why my submission of J changed to Accepted? Were there some wrong test datas?
 » 4 years ago, # |   +35 I am sceptical about editorial to J...
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 After reading the editorial for Problem , I am certain they literally copy-pasted the technique explanation from my blog and changed a couple of words here and there..Unsurprisingly, that is how I solved the problem during the contest as well (Copy the code in the blog -> Change Inputs -> Submit -> Profit). Seems like even they submitted this.EDIT: Why am I being downvoted into oblivion? I didn't say anything untrue, did I? The editorial literally uses the same variable names (ST and EN) and copies the two cases verbatim from my blog. (the language is exactly the same)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +30 I found a counterexample for ainta's solution of J. 5 5 9 1 3 2 3 4 3 5 3 2 2 3 2 4 2 1 1 5 1 is same as 5 5 5 1 2 2 2 4 2 5 2 3 1 and the answer is 2, but output is 3.EDIT:
•  » » » 4 years ago, # ^ |   +30 I think that answer for that case is even 1 as shown by this configuration 5 5 3 1 1 3 1 5 1 But yeah, that doesn't change that model solution to J is shite and is not correct.
•  » » » » 4 years ago, # ^ |   +20 Yes. zigui's example is a counterexample of my algorithm. But I think 5 5 3 1 1 3 1 5 1 is not same as zigui's example. In zigui's example, for every input, output is 2 (probability : 1/2) or 4 (probability : 1/2), but yours is not.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +40 We (Polish guys) had a discussion on how shitty and unclear was statement of this problem and its details, but it seems it is even more unclear than I have thought. I was convinced that we are interested only in amount of water that falls to every cell (which is 1/2 for 2 and 4 and 0 for 1, 3 and 5 in all mentioned cases) but it seems you're suggesting that we should also care where did that water come from. I think I will stick to my version, but who knows what organizers meant when saying "distribution of water"
•  » » » » » » 4 years ago, # ^ |   +30 At first, I understand the same way but soon I realized I can't manage that problem.I agree with that description of this problem is very unclear and hard to read.
 » 4 years ago, # |   0 Auto comment: topic has been updated by niksmiljkovic (previous revision, new revision, compare).
 » 4 years ago, # |   +11 Oh, so we've maxed the onsite, good to know :3
 » 3 years ago, # |   -30 You are doing such a great work. I really appreciate your efforts towards your blog. Cheap Price of Wrist Watch Thank you.
 » 3 years ago, # |   +1 I was an official finalist and when I did the online mirror (it's unrated anyway so why not, we were only asked not to discuss problems in public, and participating in the mirror does not really count as such), someone kept removing my submissions, marking them as skipped. Not a problem, until I found out that they accidentally removed one submission from practice I had previously done! Please be more careful next time!