niksmiljkovic's blog

By niksmiljkovic, history, 3 weeks 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, cki86201, 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  

»
3 weeks 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).

»
3 weeks 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)?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it harder than normal CF contest???

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Will there be T-shirts like last year?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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.

»
3 weeks 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).

»
3 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

Is it rated?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Bubble sort Cup, amazing!!!

»
3 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

Is it rated?

»
3 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

Upvote me or be bad at code!

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

»
3 weeks 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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How many computers will teams have during finals ?

»
3 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

sorry but i have to ask is it rated?

»
3 weeks 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?

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where are final results?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I know, I asked for detailed results

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 weeks 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

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Team of tourist and VArtem opens the scoring...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Also me, but they kicked me from their team.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem I?

»
3 weeks ago, # |
  Vote: I like it +87 Vote: I do not like it

Guy who wrote this:

should seriously urgently learn some math

  • »
    »
    3 weeks 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.)

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

How to solve A correctly?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the problems be open to solve again soon?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    3 weeks 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.

»
3 weeks 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?

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

    It is

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

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

  • »
    »
    3 weeks 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).

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

      Wow, that would be great, can you elaborate?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Sorry. I miscalculated time complexity :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When can we submit codes after this contest?

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

    I was only a few seconds late :(

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

    You should be able to submit now.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

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

      The were polynomials of two variables.

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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).

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

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

»
3 weeks 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 ..

  • »
    »
    3 weeks 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.

»
3 weeks 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 :)

»
3 weeks 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.

»
3 weeks 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!

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

I am sceptical about editorial to J...

  • »
    »
    3 weeks 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)

  • »
    »
    3 weeks 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:

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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"

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

»
3 weeks 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).

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

You are doing such a great work. I really appreciate your efforts towards your blog. Cheap Price of Wrist Watch Thank you.

»
2 weeks 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!