Biza's blog

By Biza, 5 years ago, In English

Hello, Codeforces!

It's our pleasure to announce the the finals of the 12th Bubble Cup! Bubble Cup is a programming competition organized by Microsoft Development Center Serbia (MDCS). The contest will take place on Saturday, 14th of September at 10:00 UTC+2 in Belgrade, and will last for 5 hours. Live results will be available on the official Bubble Cup website. Results will be frozen during the last hour of the competition. The winners will be announced at the closing ceremony.

The format of the competition is very similar to ACM-ICPC — teams consisting of up to three people are allowed, and they have one computer and five hours to solve problems without partial scoring. Ties are broken using the usual time penalty rules.

Just like in the previous years, there will be an online mirror of the finals here at Codeforces, starting on Sunday, 15th of September at 15:35 UTC+2.

Just like last year, the onsite competition is 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. We do not guarantee that every problems unique to Div2 is easier than every problem that is not.

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 ACM-ICPC team contest rules.

Both contests will be unrated, due to the format and the length of the mirror being dissimilar to the standard Codeforces rated rounds. Note that this is a team contest, i.e. competing in teams up to three people is allowed. (Of course, you can also compete in a 1-person team.) There will be at least 8 problems in each division.

As of now, Codeforces does not support rating-based divisions in team contests, so we came with the following ad-hoc rule: teams with the maximum rated member having rating less than 1900 should enter the Div2 contest. Teams with the maximum rated member having rating at least 2100 should definitely enter the Div1 contest. The teams not covered by the previous two criteria are free to choose.

Here are the past Bubble Cup mirrors on Codeforces:

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]

The problems and their solutions were created by employees and interns of Microsoft Development Center Serbia (MDCS).

We are very grateful to MikeMirzayanov and the rest of the Codeforces team for their support and the wonderful Polygon platform. Special thanks to knightL for big help with problem testing.

The full editorial, together with the statements and solutions of the tasks from the qualification rounds, will be available in the booklet section of the Bubble Cup website on Sunday.

We wish good luck to all participants!

EDIT:

Congratulations to everyone who participated!

Top three teams in Div1 who were also the only teams who solved all 9 problems:

  1. ITMO University: Standard deviation: budalnik, craborac, cdkrot

  2. Almost Retired: KAN, Um_nik

  3. denglaoshi fans: 300iq, jqdai0815

Winners of Div2 are:

  1. Omar^3: OmarHashim, Momentum, omarosama96 with 5 problems solved

  2. WNTN: Diashka, DeD_TihoN, ZloyHR with 4 problems solved

  3. Reversal Destiny: SorahISA, Nkl5RDZZZVq1N2F0 with 4 problems solved

You can now find the solutions to the problems in the booklet section of the Bubble Cup website.

Thanks to everyone who took part in the competition!

image

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Is the time link wrong? It says 15:35 UTC+2 but when I go to the link it says 15:35 UTC.

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

    Yes, thank you for pointing out. It is corrected now. :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In this round problem will be in increasing order of difficulty like usual codeforces rounds or it will be in random order?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many problems are shared between div.1 and div.2?

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

If you have registered for the contest several times (for example, as part of a team and as an individual participant), then delete (unregister) the extra registrations before starting to solve problems. If you do not, then your submission may be counted on behalf of a random registration.

===

Если вы зарегистрировались на соревнование несколько раз (например, в составе команды и как индивидуальный участник), то самостоятельно удалите лишние регистрации до начала решения задач. Если вы это не сделаете, то ваш попытка может быть зачтена от имени случайной из регистраций.

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Why problem C is like doing constant optimization so you tle and then you do constant optimization so you tle and then you do constant optimization so you tle and then you do constant optimization so you tle?

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

    What is your complexity? My solution works no more than 1 second on these tests. And it has complexity $$$O(n ^ 3 + k)$$$.

    UPD: Well, I saw bellow your complexity. And I guess correct answer on your question is "Because you have $$$nk$$$ summand in your complexity :)"

    UPD2: Well, now I noticed that $$$n ^ 3 \cdot 2 == n \cdot k$$$, and therefore I take my guess back :)

»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Wtf was that Q<=10 in E? Reading that statement makes you think "how tf do I handle these queries and this weird transformation of that array?" and then you see Q<=10. Such trolling is never welcomed.

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

    We laughed a lot when we noticed q <= 10. We lost some time, but I think it's good trolling

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

What is pretest 4 of G?

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Why does problem E exist? Awful.

Problem A looks like "We came up with a cool problem but couldn't solve it faster then $$$O(n^{2})$$$ so ...".

I liked problem C, but couldn't you make $$$K$$$ smaller? Looks like some constant optimizations are required to get AC.

Problem G is also nice.

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

    What complexity did you get for problem C? Is it $$$O((N + M) * K)$$$?

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

      $$$O(n^3 + nk)$$$ (I assume $$$n=m$$$)

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I was mistaken about the complexity of my solution (mine was indeed $$$O(n^3 + nk)$$$). Can you share what kind of constant optimization you did in order to get AC?

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

          I stored bad guys for each cell with info about it previous occurrence, then when calculation DP I can go either right or down, and when I go to new cell, I would try all the bad guys. It gets TL 29.

          Then I changed it to storing horizontal and vertical bad guys separately + total cost for all bad guys in this cell, and when calculation DP try only bad guys with the same direction I'm currently moving. It gets AC in 2.3

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

        Can be done in $$$O(n^3+k)$$$, but whatever.

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

          Without $$$O(n^3)$$$ memory?

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

            Yep, the state is $$$dp_{vertical}[n][m][k]$$$ and $$$dp_{horizontal}[n][m][k]$$$. The first one means that we are in the cell $$$(n, m)$$$ and we've just made exactly $$$k$$$ vertical steps. You have to add some costs for each $$$k$$$, but each transformer adds the cost only to the prefix of possible $$$k$$$, so prefix sums for each cell separately. Also, only the last row is interesting to reduce memory.

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

              Adding $$$k$$$ to the state is smart, thanks.

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

                Intended solution was just as Radewoosh described. Didn't expect $$$n*k$$$ there :)

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

            There is actually another (very similar) solution in $$$O(N^3 + K)$$$ amortized that doesn't require any memory optimizations. First we calculate cost of every cell, which is the sum of required energy to kill all transformers that you will meet if you enter that cell (ignoring that they disappear if you've already met them). Only way to meet a transformer twice is to move straight down or right between the two meeting points, and that can be represented as vertical and horizontal intervals. There will be 2K intervals maximum. Keep two buckets for each cell, the horizontal intervals whose right cell is the current one and also the vertical intervals whose bottom cell is the current one.

            Now let's do $$$dp_{vertical}[N][M]$$$ and $$$dp_{horizontal}[N][M]$$$ (we arrived at cell $$$(N, M)$$$, and our last move was vertical/horizontal). Let's say we moved horizontally last, that is, we're calculating $$$dp_{horizontal}[i][j]$$$. Our last position is one of $$$dp_{vertical}[i][k]$$$, where $$$0 \leq k < j$$$. But, while calculating dp we also use a sweep from left to right and 'activate' horizontal intervals when we pass their right ends, by adding $$$-e$$$ to the cost of the cell that is the left end of that interval (we will have to keep two copies of the cost, just so we don't mix the one for vertical and horizontal transitions). Then our recurrence relation is $$$dp_{horizontal}[i][j] = max(dp_{vertical}[i][k]+c[i][k...j])$$$ (where $$$c[i][j]$$$ is the modified cost of cell $$$(i, j)$$$). For this we just do partial sum starting at $$$(i, j)$$$ and going left. At the end, our answer is $$$max(dp_{vertical}[N-1][M-1], dp_{horizontal}[N-1][M-1]) + c[N-1][M-1]$$$.

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

      After several tries, I reduced complexity to $$$O(n^3 \log n + k \log)$$$ with $$$O(n^2)$$$ memory.

      But before that, I wrote $$$O(n^3)$$$ with $$$O(n^3)$$$ memory and got ML :(

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

        Is it actually smaller? :) Or is it just trolling?

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

          Well, $$$n^3 \log$$$ was with constant 0.5 and with $$$\log$$$ from Fenwick, so it was very fast, much faster than my initial $$$O(n^3 + nk)$$$.

          Also, $$$O(n^3 + k\log)$$$ was super fast, but I need to store $$$500^3$$$ long longs... No idea why authors decided to use long long answer in this problem and 128 MB ML :(

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Mindfuck of a year to me: *secik.begin(); on an empty set gave me TLE instead of RTE. That's why it took me 50 mins to get the easiest problem accepted. UBs have no mercy.

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

    Onsite we (and some other teams) had TLE from out-of-bounds array call and recently on Olympiad of Metropolises I had a runtime error because I used an int function as a void function (not returning anything). I guess this is the year of troll undefined behaviour.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H? Any hints?

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

    Hint: how does graph $$$i \to a[i]$$$ looks like?

    more
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

When will it be possible to finish tasks?

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Okay, you know what? $$$O(n^{3} + k)$$$ solutions to C are smart and all, but since $$$k \approx n^{2}$$$, optimizing $$$O(n^{3} + nk)$$$ to $$$O(n^{3}+k)$$$ is still kind of constant optimization, and words from problemsetters like "we didn't expect $$$O(nk)$$$ to pass" are weird.

  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it +22 Vote: I do not like it

    I'm still waiting to submit my O(N^2*log^3) solution with lichao tree + 2D fenwick for the function evaluation that can be optimized to O(N^2*log^2) with persistent segment trees or maybe even O(N^2 * log) going down the lichao tree and the persistent seg tree at the same time... Don't know what to expect from this, I delayed learning lichao tree properly until this C...

    Edit: My solution looks correct but surprise surprise I'm having a hard time to not get MLE using my usual 2D fenwick with coordinate compression on vectors because it uses O(K*logNM) memory, it's getting 130MB on test 29 :D thanks mr setters

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

      Why downvotes? this is the real shit data structure swag

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it

    I didn't mean i didn't want $$$O(nk)$$$ to pass at that moment, but we had two different solutions running in 1s and 1.6s, which unfortunately didn't have factor $$$O(nk)$$$, so i decided to put TL at 4s, which i thought at that moment was enough for a constant difference.

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

    60686995 O(N^2 * log^3N + K * logK) time complexity as I said, could be optimized with persistent seg trees to cut a log in time.

    That being said, I had to optimize both memory and time constants a bit to make it pass, maybe that's expected for this complexity, but I have O(N^2 + K * logN) memory and it was getting 130MB because I was using long longs for coordinate compression, 118MB after changing it to int. I completely agree that this problem was weird. I'm not even sure if persistent seg trees fit in this ML if you don't do some wizardry like updating every point in the same coordinate at the same time lol. You can also use CHT, the idea really is the same as this problem, the functions intersect in at most 1 place.

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Why can't I submit solutions for practice? The previous Bubble Cup rounds are open to practice submissions.

Edit: works now

»
5 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

I Apologize

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I am not able to open the tutorial of this contest.It seems that the website is down. Can someone please share the editorial?

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

    The website will be up next week. Sorry for the delay.