TadijaSebez's blog

Mirror of Bubble Cup 14 Finals on Codeforces
By TadijaSebez, history, 3 years ago, In English

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

  • Vote: I like it
  • +138
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Why do I keep missing the minimum age requirement for some many contests?! I am one year behind the minimum age of 15.

→ Reply
»
3 years ago, # |
  Vote: I like it -34 Vote: I do not like it

i hope that my rating will increase after this contest

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +67 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Everything is okay, bubble cup crew connected to us, and give the opportunity to join contest)

    Thx for help :)

    → Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Thanks for the interesting contest! How to solve Restaurant Game and Bob's Beautiful Array?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Yeah , interesting problems are there !!

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve problem A "Weights" ?

→ Reply
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

A was beautiful.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve question E (array game)?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

A https://acm.timus.ru/problem.aspx?space=1&num=1481

Exactly the same problem, even the input/output format.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

F: I thought hash like in the editorial should not work as $$$k$$$ is limited (less than $$$500$$$). There is no randomness at these.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution with k = 2 (and 2 heuristics) passed the tests

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My k=2 without heuristics passed, what heuristics did you use? Were they necessary?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think you can make tests to make all k = 2 solutions fail.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                  ← Rev. 5   Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem A is almost the same as IOI2002 Utopia and timus 1481.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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,

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No way! I can't believe I missed the fact that the sequence needs to be strictly increasing SMH. Thanks

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a doubt in Problem C (Bubble Strike) Editorial: -

Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The pure random solution manages to work actually (I think the tests are just weak maybe). 159587716

    → Reply