dpaleka's blog

Mirror of Bubble Cup 11 Finals on Codeforces
By dpaleka, history, 6 years ago, In English

Hello, Codeforces!

It's our pleasure to announce the the finals of the 11th Bubble Cup! Bubble Cup is a programming competition organized by Microsoft Development Center Serbia (MDCS). The contest will take place on Saturday, 22nd of September at 11: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 Saturday, 22nd of September at 12:35 UTC+2. Unlike in the previous years, the mirror will be on the same day as the onsite finals.

This 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 9 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]

The problems and their solutions were created by employees and interns of Microsoft: Milanin, ibra, balsa_knez, Kole, radras, fulu, pedja, niksmiljkovic, davidmilicevic97, FilipVesovic, yours truly, and many more. Most of the team works in MDCS.

We express gratitude to KAN and 300iq for round coordination, and MikeMirzayanov and the rest of the team for the great Codeforces and the wonderful Polygon platform. We thank testers DBradac and especially the extremely helpful knightL, for helping prevail various difficulties.

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. An editorial with short descriptions of solutions may appear on Codeforces before that.

Good luck to all participants!

EDIT: Congrats to everyone that competed! In total, there were over 800 teams that solved at least one problem.

The winners of Div1 are:

  1. Merkurev, I_love_Tanya_Romanova, Um_nik — a special congratulations for being the only team on the mirror to solve all problems, two of them in the last 5 minutes!

  2. LHiC — the best one-man team, with 9 problems solved

  3. xtalclr, nong, ko_osaga — also solved 9 problems

The winning team of Div2 is:

  1. fengyecong, Als123, 200815147 — winning with three problems to spare!

This post will be updated again when the booklet is online, which should be before the end of the day in UTC+2. Also, onsite results won't be known until the awards ceremony in the evening.

Thanks all for participating!

EDIT 2: The editorial is up!

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

Comments Comments (55)
| Write comment?
»
6 years ago, # |
  Vote: I like it -83 Vote: I do not like it

How pathetic

Just trying to raise your contribution

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

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

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

does the one-computer rule apply to unofficial participants too or only the onsite contestants?

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

    Nobody can really come to your house/wherever you do the contest and force you to use one computer. Depends how you want to do it, and how honest you are with yourself.

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

    That's an excellent question! We should have put this in the announcement:

    After some thinking, we decided to adapt the Bubble Cup onsite rules, i.e. the rule on the mirror is that at most one person in the team is writing code at any time. Using more computers than one is OK, as long no two people code at the same time.

    The reason for this is twofold:

    1. we want to "mirror" the onsite competition at closely as possible, and enable comparison the results of the onsite and online teams

    2. we want to enable teams to have this Bubble Cup mirror as a practice contest for the coming ACM-ICPC season

    As everyone knows, this rule cannot be enforced efficiently except in the most outrageous cases. However, we made the round unrated, and we think it would be really sad to see cheating en masse on an unrated Codeforces round.

    Good luck everyone!

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

      In my opinion it is quite a silly rule for anyone not participating at an ACM ICPC competition. The rule only makes you waste time. It would be wonderful if you could have an option which you check if you are obeying the rule. That's the most honest and fair you can get for everyone.

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

Is it rated?

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

    No, 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 9 problems in each division.

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

Why didn't CodeForces evaluate the code?

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

Unrelated questions :
1. Why is there no participants in Technocup 2019 — Elimination Round 1?
2. Why Codeforces' Submissions has so many "In Queue"?
Update : the problem in question 2 had been fixed

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

My rating is less than 1900 but I register in Div. 1 without any warning ?1?!? Can I participate in Div. 1?

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

What does that orange colour indicate (over the team number)?

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

    One or more of your team-mates has registered individually. Unregister it before the starting of contest to correct it.

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

i participated in both round with one handle .am i going to disqualified.

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

How to solve B?

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

    B is mine, along with C and F.

    If A is the first bag, B is the second, a necessary and sufficient condition for some residue x not being in A + B is:

    A = x - A.

    And this is a string problem, where the characters are the differences of consecutive members of A!

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

      Really liked B, thank you! It was hard for me but people solved it very well.

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

        It is weird how the early accepted solutions on public scoreboards reshape the flow of the contest. On the onsite, B wasn't solved in the first two and a half hours!

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

          Yeah, and here on CF, E was practically unsolved but onsite there were at least three teams who solved it.

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

        And of course, B having more ACs on the mirror than D — I thought it could never happen.

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

      Nice solution! I didn't think of this during the contest and then I did some random approach :

      Randomly shuffle the array A. Consider S = {A[0] + A[0], A[0] + A[1], ..., A[0] + A[n - 1]} as the set of all candidate solutions.

      Let s be the sum of all A[i], then if x is a solution, we must have Nx ≡ 2s(modM). Remove elements in S not satisfying this property.

      For each remaining candidate x, I check it against C random A[i] by checking if x - A[i] is in the array. If it works for all C random A[i], then I consider x in the final answer. C is carefully chosen so that I won't get TLE.

      I'm not sure why this works or it probably doesn't and it might be possible to find a countercase for it.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it 
        200000 400000
0 2 4 6 8 ... 399998

        with 8 replaced with 9 and 399998 replaced with 399997 is a counter case. since 9 and 399997 along with x - 8 and x - 399998 are the only witnesses for the invalidity of even numbers (except 6).

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

what a contest!

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

Clutch submit wipes sweat

P.S. Problem name is Last Chance

Just realized that I had the first and last accepted submission in the Div. 1 mirror.

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

How to solve "Self-exploration" and "Hyperspace Highways"?

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

    Hyperspace Highways:
    Find biconnected components. Build a graph where nodes are nodes of old graphs and components; edges are between nodes from old graph and components they belong to. Now you have queries on tree.

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

    My solution for Hyperspace Highways : Construct bfs tree. It can be easily proven that for any two nodes u, v in the bfs tree, if u is not a parent of v or vice versa but there is an edge between u, v, then u and v must share the same parent if the graph satisfies the given condition.

    For a query u, v, if u is an ancestor of v (or vice versa) in the bfs tree, the answer must be dist(u, v) in the bfs tree. Otherwise, let L be the lca of u, v and let u', v' be the children of L such that u' is an ancestor of u and v' is an ancestor of v. Then, the answer is dist(u, v) - 1 if u', v' are connected by an edge and dist(u, v) otherwise. (dist is the distance function with respect to the bfs tree).

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

      I think your solution fails for this simple test case: 7 7 1 1-2 2-3 3-4 1-5 5-6 6-7 4-7 4 7 How come this solution pass the system test? The test case is simply a cycle! Your code returns 6, whereas the answer is 1. Many have used this approach and their solution have passed, all of them give 6.

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

        The graph you have described does not satisfy the conditions of the problem.

        This is literally underlined in the statement: "In other words, the set of planets in every simple cycle induces a complete subgraph."

        Why is this upvoted? Am I misunderstanding something?

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

          Isn't it forming a simple cycle? `1-2-3-4-7-6-5-1 ? And the dfs solutions are giving 1 as output whereas bfs solutions are giving 6 as output.

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

          I think I've realized my mistake. I thought that every simple cycle in the graph should be replaced by a clique. The clique was already given in the input graph. Sorry for the inconvenience!

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

    For "Hyperspace Highways": You replace each complete subgraph that has vertices [a1, a2, a3, ..., an] with subgraph with edges [(a1, newV), (a2, newV), (a3, newV), ..., (an, newV)] after this you have a tree. It's easier said than done though. Now enjoy my awkward explanation.

    Basic idea is that during dfs-traversal (starting with root depth=0 and increasing depth by one for each layer) for each vertex you go through all it's edges and find neighbour vertex with minimum depth. It is Almost an Id of complete subgraph yet. But not yet, here is an example:

    1 2
2 3
1 3
1 4
4 5
1 5

    If we start dfs with vertex=1 each vertex will find the vertex 1 as the vertex with minimum depth but there are two separate complete subgraphs here that shouldn't merge. The solution is to keep a stack of dfs-traversal and take not the "stack[minimumDepth]" but "stack[minimumDepth + 1]" as the Id of the subgraph. In this case the complete subgraph Ids will be 2 and 4 as they are "just below" 1 in the traversal tree.

    After this you have a tree with no more than 2*N vertices for which you use Least Common Ancestor to find the minimum route length. Code: http://codeforces.me/contest/1046/submission/43264131

    I solved it during the contest but 1s time limit seems to be too harsh for this problem so it haven't get accepted during the contest. Few minutes later I replaced dynamic vectors with preallocated memory and this optimisation barely made it in 1s.

    Does someone have an easier solution or better explanation?

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

      We used much simpler DFS-tree solution, and just smart finding of connected components in neighbourhoods of vertices — both solutions can be made to run in , which should run in 0.3s on the system tests. Everything will be explained in the booklet pdf.

      Of course, the BFS-tree solution is even better and simpler, but it actually took us by surprise during the contest.

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

        I tried to understand the solution from the booklet. Doesn't look much simpler:)

        And I am not sure it's idea is different from my solution as I am also searching for minimumDepth of each complete subgraph.

        Can you provide your code?

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

I didn't code it but does this solution work for Hyperspace highways? We condense each cycle to a vertex and then we can calculate the distance by lca preprocessing. But it seemed like we have to take specific care of some cases like each cycle which we condense should have a cost of 2 and other vertices should have a cost of 1 and also take care when a vertex in one of the queries belongs to a cycle.

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

    Almost, but you replace not just the cycle but all the complete subgraphs. Complete subgraph [a1, a2, a3, ..., an] becomes subgraph with edges [(a1, newV), (a2, newV), (a3, newV), ..., (an, newV)].

    In my implementation this also holds true for complete subgraphs of size 2 (not a cycle): [a1, a2] becomes ([a1, newV], [a2, newV])

    Then you compute distance using LCA and divide it by two (because all edges where replaced by edge-newVertex-edge)

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

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

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

How to solve, 'Palindrome Pairs'? So many people solved it, I feel stupid.

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

    I did it the following way:

    For each string, calculate a bitmask, where the i-th bit will be 1 if you there are odd number of occurrences of the i-th letter in the alphabet, otherwise the bit will be 0. For example, "aabz" will be represented by "100000000000000000000000010", because we have odd number of 'z' and 'b'.

    Within a map, calculate how many time does each mask occur in the input.

    Now let's process each mask one by one. Lets say we have a mask with some number of set bits:

    • First, the string represented by this mask can be part of a palindrome with any other string that has the same mask, so if the number of occurrences of the mask is X, add (X * (X — 1)) / 2 to the result. The resulting palindrome will have even number of occurrences for all letters.
    • Second, find all other masks, which XOR-ed with the current one, will produce a result, which has only one set bit. Why? Because the resulting mask will represent some string with only one odd-repeating character.

    Checkout my code for reference.

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

Does anyone know a problem very similar to E, or a math problem very similar to F? We're now sure that answers to both of these questions exist, but we cannot find anything.

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

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

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

How come Candidate Master can participate in both Div.1 and Div.2 when both contests are at the same time ?

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

My opinion on hard problems:

A: Just write the flow and restore the answer. Oh, and we also made constraints insanely high so you will doubt your solution at first. Like, really, we need to run 5000 DFSs (I use the analysis from the editorial here) on a graph with about 350000 edges. This is not OK.

E: Cool problem, but it looks like there were such problem before.

F: One of the best problems this year, at least.

J: We didn't believe that is fast enough, so we come up with O(NK) ( because we had not enough memory for arrays in trie). And then Merkurev spend 3 hours to squeeze it through ML. This is not cool.

Also, 2 of 4 hard problems are geometry (geometry about convex hulls in particular). Well, F is more about coming up with the solution, but the implementation part is also not easy.

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

    For A, I had to do flow on segment tree. Am I dumb?

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

I would like to share an alternative, easier solution for "AI robots" (Div 1/G, Div 2/A): As in the official solution for each robot I also did 2K+1 queries for different IQ levels. The main idea is to sort all robots by their view radius in the decreasing order and then add robots to the IQ-corresponding-Treap one by one. To count how many robots the current robot can see we simply do one treap request for range [x — r, x + r]. Because we sorted the robots by their viewing radius, all the robots that are already in the treap have viewing radius >= r, and thus can also see the current robot.

Main part of the code:

map<int, Treap<int>* > poses;
num answer = 0;

for (auto [r, x, q]: rs) {
    for (int dq = -k; dq <= k; dq++) {
        int fq = q + dq;

        auto it = poses.find(fq);
        if (it != poses.end()) {
            Treap<int>* root = it->second;
            answer += inRange(root, x - r, x + r + 1);
        }
    }
    auto it = poses.find(q);
    Treap<int>* root = it != poses.end() ? it->second : nullptr;
    root = insert(root, x);
    poses[q] = root;
}

cout << answer << endl;

Submission: http://codeforces.me/contest/1046/submission/43254253

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

Fun fact about problem A: if we reduce it to maximum matchings in a stupid way (so that the graph may have O(NM) edges) and run Kuhn with some optimizations, it passes in 374ms (43263725).

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

Can someone tell me how to efficiently generate tests for Hyperspace Highways?

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

    I am the author of the problem, which was made into existence as I read about 2-distance operation on graphs, and wondered if the inverse of the procedure is computable. (When doing 2-distance of a graph, you keep all vertices and connect every two vertices which are two edges apart.)

    Trying some examples, I noticed that the graphs obtained from trees were particularly nice — in fact, 2-distance graphs of trees are made of two connected components, each of which satisfies the constraints of the Bubble Cup problem.

    So, we created some nice trees, and just applied the 2-distance transformation. For good results, you should have some vertices with degree .

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

Are there any details I need to know on this problem? I always get one less than correct answer on test #32.

→ Reply