niksmiljkovic's blog

Mirror of Bubble Cup X Finals on Codeforces
By niksmiljkovic, history, 7 years ago, In English

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.

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

Comments Comments (75)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by niksmiljkovic (previous revision, new revision, compare).

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

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

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

    It will allow all languages supported on Codeforces, atleast that was the case in previous years.

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

    The online mirror will allow all languages supported by Codeforces. However, we can't guarantee that all problems will be solvable in each language.

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

Is it harder than normal CF contest???

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

Is was contest rate plz I need now teechr will fail my?

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

Will there be T-shirts like last year?

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

    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.

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

      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.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

Who will join this contest in spite of unrated, put like.

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

Auto comment: topic has been updated by niksmiljkovic (previous revision, new revision, compare).

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

Is it rated?

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

    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.

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

Bubble sort Cup, amazing!!!

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

Bad luck. Solution for A and C was correct. If these two got rated then.... Alas! they got skipped.

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

How many computers will teams have during finals ?

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

sorry but i have to ask is it rated?

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

is it a team contest?

if answer is yes so why we cant register as a team?

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

    Yes, the registration page will be updated soon to allow team registration.

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

May I ask how to register as a team member? The register page doesn't have this choice.

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

you think i will say "is it rated" ? No! i just want your downvotes lol

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

Where are final results?

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

    Radewoosh's team won, second place for Jagiellonian Armadillos from Poland and third place for Cheeks from Russia. From facebook.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I know, I asked for detailed results

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

        It's in the post you. Can't you read?

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

          Results on site are before freezing. TOP3 had 9, 8, 7 problems respectively

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

Team of tourist and VArtem opens the scoring...

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

How to solve problem I?

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

Guy who wrote this:

should seriously urgently learn some math

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

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

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

How to solve A correctly?

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

    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.

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

Will the problems be open to solve again soon?

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

How to solve F?

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

    The solution is

    a(mCn + mCn - 2 + ...), a(mCn - 1 + mCn - 3 + ...), ...a(mC2 + mC0), amC1, amC0

    find the x s.t. and as it is prime, find modular inverse and calculate.

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

What's the intended solution for problem H? I've come up with a O(N 3 × K) solution. Is it fast enough?

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

    It is

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

    I also doubted that, but it ran in 826ms somehow

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

    I think There is an O(N^2 * K + N^3) solution (with preprocessing sorting-by-angle).

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

      Wow, that would be great, can you elaborate?

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

        Sorry. I miscalculated time complexity :(

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

When can we submit codes after this contest?

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

    I was only a few seconds late :(

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

    You should be able to submit now.

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

Was the intended solution for B O(m4) polynomial multiplication?

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

    I have solution in O(n + m^2logl) so i think O(m^4) might be too slow.

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

      Could you please elaborate?

      Edit) I got the solution you are referiring to from someone else. Thank you for your help.

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

    How do you multiply two polynomials in m^4 :P?

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

      The were polynomials of two variables.

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

    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?

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

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

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

    Solved it in O(m^3logL+N) using matrix multiplication.

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

can someone explain how to solve problem A correctly?

and btw what is the 6th test case ..

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

    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.

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

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

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

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.

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

For D — Exploration plan,

My submission of D is using Binary_Search together with MaxFlow, but WA on test 6. My Submission

However, 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!

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

Why my submission of J changed to Accepted? Were there some wrong test datas?

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

I am sceptical about editorial to J...

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

    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)

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

    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:

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

      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.

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

        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.

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

          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"

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

            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.

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

Auto comment: topic has been updated by niksmiljkovic (previous revision, new revision, compare).

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

Oh, so we've maxed the onsite, good to know :3

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

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!

→ Reply