Блог пользователя niksmiljkovic

Автор niksmiljkovic, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +151
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it harder than normal CF contest???

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Will there be T-shirts like last year?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -31 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Is it rated?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Bubble sort Cup, amazing!!!

»
7 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How many computers will teams have during finals ?

»
7 лет назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

sorry but i have to ask is it rated?

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

is it a team contest?

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where are final results?

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Team of tourist and VArtem opens the scoring...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem I?

»
7 лет назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится

Guy who wrote this:

should seriously urgently learn some math

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

How to solve A correctly?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will the problems be open to solve again soon?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When can we submit codes after this contest?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Could you please elaborate?

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain how to solve problem A correctly?

and btw what is the 6th test case ..

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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!

»
7 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

I am sceptical about editorial to J...

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

    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:

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +40 Проголосовать: не нравится

          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"

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +30 Проголосовать: не нравится

            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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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!