By TadijaSebez, history, 8 days ago,

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

• +138

 » 7 days ago, # |   -19 Why do I keep missing the minimum age requirement for some many contests?! I am one year behind the minimum age of 15.
•  » » 7 days ago, # ^ |   +6 You still stuck? I told you to grow up already.
•  » » » 7 days ago, # ^ |   0 Uh please. How can I keep growing up already? I am not God so I can't just grow when I feel like it.
 » 7 days ago, # |   -34 i hope that my rating will increase after this contest
•  » » 7 days ago, # ^ |   +10 I think it is an unrated contest. What a pity!
•  » » » 7 days ago, # ^ |   +7 your username remembers me this: Spoiler
•  » » » 7 days ago, # ^ |   +10 Oh no, I didn't notice it. I'm sorry :(
•  » » » » 7 days ago, # ^ |   0 You need to pay more attention next time...
 » 7 days ago, # | ← Rev. 2 →   +67 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
•  » » 7 days ago, # ^ |   +11 Everything is okay, bubble cup crew connected to us, and give the opportunity to join contest)Thx for help :)
 » 7 days ago, # |   +31 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?
 » 7 days ago, # |   +31 Thanks for the interesting contest! How to solve Restaurant Game and Bob's Beautiful Array?
•  » » 7 days ago, # ^ |   +10 Yeah , interesting problems are there !!
 » 7 days ago, # | ← Rev. 3 →   +29 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
 » 7 days ago, # |   +11 How to solve problem A "Weights" ?
 » 7 days ago, # |   +36 A was beautiful.
 » 7 days ago, # |   +10 How to solve question E (array game)?
•  » » 7 days ago, # ^ | ← Rev. 2 →   +1 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.
 » 7 days ago, # |   +42 Exactly the same problem, even the input/output format.
 » 7 days ago, # | ← Rev. 3 →   0 F: I thought hash like in the editorial should not work as $k$ is limited (less than $500$). There is no randomness at these.
•  » » 7 days ago, # ^ |   0 My solution with k = 2 (and 2 heuristics) passed the tests
•  » » » 7 days ago, # ^ |   0 My k=2 without heuristics passed, what heuristics did you use? Were they necessary?
•  » » » » 6 days ago, # ^ |   0 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.
•  » » » » » 6 days ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » » 6 days ago, # ^ |   0 I think you can make tests to make all k = 2 solutions fail.
•  » » » » » » » 5 days ago, # ^ |   0 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.
•  » » » » » » » » 5 days ago, # ^ |   0 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.
•  » » 7 days ago, # ^ |   +15 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)$.
 » 6 days ago, # |   +8 Problem A is almost the same as IOI2002 Utopia and timus 1481.