Hello, Codeforces!
Microsoft Development Center Serbia is thrilled to announce the finals of the 14th edition of Bubble Cup competition! Bubble Cup is an international, ICPC-style team contest aimed at university and high school students.
Contest will take place on Saturday, 9th of October at 10AM CEST, in online format. Winners will be announced at the closing ceremony. You can find more info on the BubbleCup website.
Just like the previous editions, this final will be followed by an online mirror competition on Codeforces. Mirror will take place on the same day about an hour after the start of the finals — Oct/09/2021 12:05 (Moscow time). Contest will last for 4 hours and ICPC rules will be applied. It will be a competition for teams of 1-3 members. There will be at least eight problems.
Just like last year, the finals are divided in two "divisions", called Premier League and Rising Stars. The two contests will have most of their problems in common, but the Rising Stars competition will feature some easier tasks targeted at high school contestants.
Both of the contests will be mirrored here on Codeforces, with Premier League mapping to the Div1 contest and Rising Stars mapping to the Div2 contest. The mirror will use native Codeforces ICPC team contest rules. Each team is allowed to use multiple computers.
Both contests will be unrated, due to the format and the length of the mirror being dissimilar to the standard Codeforces rated rounds.
The problems and their solutions were created by employees and interns of Microsoft Development Center Serbia: niksmiljkovic, acac97, renea, BubbleCup, nikolapesic2802, berke00, davidmilicevic97, ijevtic, dj0l3, igzi, Kole, Vasiljko, pavlej and me TadijaSebez.
We give our thanks to Nikolay Kalinin (KAN) and Mike Mirzayanov (MikeMirzayanov) for making these mirror contests possible and for the wonderful Codeforces and Polygon platforms. Special thanks goes to Alexandr Lyashko (knightL) for helping out with problem testing.
You can find problems from previous finals on our Codeforces online mirror competitions:
Bubble Cup 8 — Finals [Online Mirror]
Bubble Cup 9 — Finals [Online Mirror]
Bubble Cup X — Finals [Online Mirror]
Bubble Cup 11 — Finals [Online Mirror, Div. 1]
Bubble Cup 11 — Finals [Online Mirror, Div. 2]
Bubble Cup 12 — Finals [Online Mirror, Div. 1]
Bubble Cup 12 — Finals [Online Mirror, Div. 2]
Bubble Cup 13 — Finals [Online Mirror, Div. 1]
Bubble Cup 13 — Finals [Online Mirror, Div. 2]
We wish good luck to all participants!
UPD: Editorial
Why do I keep missing the minimum age requirement for some many contests?! I am one year behind the minimum age of 15.
You still stuck? I told you to grow up already.
i hope that my rating will increase after this contest
I think it is an unrated contest. What a pity!
your username remembers me this:
Oh no, I didn't notice it. I'm sorry :(
Feel like a clown because, we go through the qualifying round and now have no access to the main round, also have no link to the contest, and at official email, nobody answers to us :(
p.s. team All Cats Are Beautiful
Everything is okay, bubble cup crew connected to us, and give the opportunity to join contest)
Thx for help :)
I don't exactly understand the idea about letting official contestants see which problems are being solved in CF mirror. Doesn't it kind of violate traditions?
Thanks for the interesting contest! How to solve
Restaurant GameandBob's Beautiful Array?Yeah , interesting problems are there !!
Everywhere I go, I see that windmill IMO problem.
G is almostly the same as this problem (with the extra step of finding the line itself and sorting the the points on the line).
H is exactly the same as this problem.
UPD: I have also heard about problem A from one of my lecturer, so it's probably a duplicate as well
How to solve problem A "Weights" ?
A was beautiful.
How to solve question E (array game)?
I'm not sure if it can be done in a cleaner way. Notice that whenever you have to play, you can choose "greedily" what move you should make.
Consider the case where left and right elements are different, if you take the bigger one, the other side can't be used again. And if you do so, the rest of the game is determined by how many integers are left such that they are strictly increasing. That part can be precomputed and you don't need to explore it anymore. Now consider you take the lower one, now you have the exact same problem as before with 1 element less.
If both left and right are equal values, any of them counts as taking a big one, so you just need to check both cases.
IF left and right values are equal doesn't this lead to an O(n^2) algorithm?
If both values are equal it leads to a O(1) check, since you can only play from 1 side now.
Imagine the test case:
5 1 1 2 1 1
How is this going to be an O(1) check?
This issue has been resolved here. https://mirror.codeforces.com/blog/entry/95774#comment-853249
A https://acm.timus.ru/problem.aspx?space=1&num=1481
Exactly the same problem, even the input/output format.
F: I thought hash like in the editorial should not work as $$$k$$$ is limited (less than $$$500$$$). There is no randomness at these.
My solution with k = 2 (and 2 heuristics) passed the tests
My k=2 without heuristics passed, what heuristics did you use? Were they necessary?
I added a random number to every value in the array and checked if the first value of the sequence is in the segment. They were not necessary, but I don't think that the k=2 solution should pass with proper tests.
Does failing some specific k's make tests good? I'm not sure, if you get WA you can just add extra checks. I don't see anything wrong with k=2 solutions, is there some relationship between sum and sum of squares?
I think you can make tests to make all k = 2 solutions fail.
You should target some hash if you know it's bad (you can fail with high probability that class of hashes). If it's not you just make it bothersome for people who decided to choose that particular seed. If you can't prove that hash is bad/make good counter tests it's your problem.
In contests with hacks you have to counter all possible hacks in your solution, well, that's the rules of contest. But in ICPC format it feels ridiculous for me.
In this particular problem you can choose several K. So I just submitted k=2 and was planning to add k=3,4,.. If it's possible to fail all of them, then yeah, tests were bad.
Author's hash solution and yours are wrong. There is no randomness at all. You can only choose a limited K, so possibly there are test cases to fail all such limited K.
F can also be solved using rolling hashes:
$$$hash(S) = (\sum_i B^{S_i}) \text{ mod } P$$$
with prime modulo $$$P = M \cdot k + 1$$$ (where $$$M = 1e9 + 7$$$) and some base $$$B$$$ such that $$$B^M \equiv 1 \; (\text{mod }P)$$$.
Problem A is almost the same as IOI2002 Utopia and timus 1481.
TadijaSebez can you check test 5 of problem D (Bubble Popping)? Firstly there are collinear bubbles unlike what the statement says. Secondly, unless I'm missing something in the statement, the answer to the last query should be 2 instead of 6 (seems to agree with a figure I drew on GeoGebra).
In the problem Array game, Why does it feel like you need to do something different when the numbers on both ends are equal? I've tried out a couple of cases. I still don't understand what end to pick from if both ends have the same number,
Sequence needs to be strictly increasing, so if the numbers are equal, whichever one you pick will make the players be able to pick numbers from that side only.
No way! I can't believe I missed the fact that the sequence needs to be strictly increasing SMH. Thanks
Weak tests for 1599B - Restaurant Game
2 3 1 1 left right 2 3 1 1 right left
The answer is 0, 2, but one can get AC with 0, 0. For example in this submission: 131309008.
I have a doubt in Problem C (Bubble Strike) Editorial: -
In the Editorial, for the case where out of the three maps, exactly one is studied by Johnny, it states that "If he has studied exactly one map of the three, then the probability is 50%, depending on the opponent's choice". Shouldn't it be (100/3)% as the opponent is selecting the map randomly out of 3 maps?
The checker for problem J seems to be really strict on the output format, and in fact requires a trailing space for the solution to pass — maybe this should be changed next time?
Failing solution — 144889042
Accepted solution — 144889058
Note how the only difference is in printing an extra space to make it work
Slightly different approach for problem $$$F$$$:
If $$$N$$$ is sufficiently small ($$$\le 40$$$, for example), then we can try all possible sets of 5 vertices to see if it is valid. If $$$N$$$ is larger than $$$40$$$, then try $$$10^5$$$ random sets of 5 points.
145700723
The pure random solution manages to work actually (I think the tests are just weak maybe). 159587716