Acko's blog

Mirror of Bubble Cup 13 Finals on Codeforces
By Acko, history, 4 years ago, In English

Hello, Codeforces!

Hope you're all safe and well.

Microsoft Development Center Serbia is thrilled to announce the finals of the 13th edition of Bubble Cup competition! Bubble Cup is an international, ACM-style team contest aimed at university and high school students.

Contest will take place on Sunday, 4th of October at 11AM CEST, virtually. Live results will be available on the official Bubble Cup website (results will be frozen during the last 45 minutes of the competition). Winners will be announced at the closing ceremony. You can find more info on the BubbleCup website.

Just like the previous editions, this final will be followed by an online mirror competition on Codeforces. Mirror will take place on Monday, 5th of October at 15:05 CEST. Contest will last for 3 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.

Just like last year, the finals are 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.

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.

We kindly ask participants of the virtual finals to hold off discussing problems publicly until the mirror is over.

Contest was mainly prepared by employees of MDCS with help from our alumni member Lazar Milenković (milenkoviclazar). 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 Alexandr Lyashko (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.

Editorial will be available in the booklets section on the Bubble Cup website sometime after the online mirror ends.

You can find problems from previous finals on our Codeforces online mirror competitions:

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]

Bubble Cup 12 — Finals [Online Mirror, Div. 1]

Bubble Cup 12 — Finals [Online Mirror, Div. 2]

We wish you best of luck in competition!

Update #1: Given the current situation we want everyone to be safe and enjoy the Bubble Cup finals from their home and that's why team members will be allowed to work on different machines.

Update #2: Congratulations to the winners!

Div1:

  1. Omatase-Trinity: hos.lyric, maroonrk, yosupo
  2. Almost Retired Dandelion: Merkurev, Um_nik
  3. times187: Cyanic, ix35, s_r_f
  4. tourist
  5. Itst两小时阿克离场: newbiegcz, Itst, pupiI

Div2:

  1. 2-sad walk: Dart-Xeyter, tem_shett, sevlll777
  2. TeamSeven: liit_mixer, sachin208, jnarutoj
  3. Fast but not Furious: amirmohammad-nezami, armin.atarod, ymmparsa
  4. （￣ー￣）: noneTP
  5. heh: Eyed, penguinhacker, el_heffeh

Preliminarily version of the editorial can be found here. Full version of the booklet will be published at a later time.

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

Comments Comments (138)
| Write comment?
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

plz check. the register doesn't work.

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

[Deleted]

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

why I am able to register in Div1 also ?

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

is it rated?

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

ping me if by any chance anybody is interested in teaming up with me
UPD: SORRY BUT I've ALREADY TEAMED UP

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

How many participants allowed in a team?

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

    "It will be a competition for teams of 1-3 members. There will be at least eight problems."
    Read the announcement dude

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

Number of problems is secret?

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

    There will be at least eight problems.

    Read the announcement dude

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

Problems are not sorted by difficulty, right?

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

Is the order of the questions sorted by difficulty value? (Because this is the icpc rule, I am not sure about this.)

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

    Problems are sorted arbitrarily, I don't think that even on ACM ICPC they are sorted (unless something has changed since last time I competed)

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

I have a couple of questions.

  • What is native Codeforces ACM-ICPC team contest rules? I haven't heard of this rule. I'm particularly concerned about whether it is allowed to copy-paste my library.

  • Team members can work on their own computers. Does this mean we can code simultaneously? Or we still shouldn't use multiple computers at the same time?

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

    I am pretty sure it is allowed to code simultaneously, that's why the length of the contest was shortened.

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

      Quoting the rule from the official website:

      "During the finals, contestants are allowed to use any code previously written by themselves, as well as any source of information on the Internet. You're not allowed to use somebody else's code."

      So to answer your questions: 1. You can copy/paste your library 2. You can code simultaneously on different computers

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

Get the book "BUGS in Writing: A Guide to Debugging Your Prose", statements are unintuitive (e.g in H) and hard to understand. Also consider adding more formal definition for statements.

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

    100% percent agree, we had to practically guess problem H

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

    Is this book generally a good read for problem setters or people who write algo articles?

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

      I found the book from the webpage of MIT6.xxx (The human intelligence enterprise), it is a general guide of writing for "computer science people". The book consists many segments, each segment covers one conceptual chunk of information, and each stands alone.

      I bought a copy months ago and found the book quite fun, and probably helpful for good writing, though I haven't read much of it.

      I would suggest you to get a scanned version from the web and read the foreword and readme to see if you are interested, since the book is hard to describe in short.

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

I didn't expect 14 questions.

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

Why the TL for J is so tight?

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

    I waste too much time on it ,but get TLE on Test21. :(

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

      There is a better solution :)

      It was intended for dp problems to pass only if they are maximally optimized.

      The booklet will probably be uploaded tomorrow, and there is a simple derivation that shows that the answer is (m/2 — m/4 + 1)(m/4 + 1) (where / is in integer arithmetic).

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

      By the way,can O(64*14)pass?

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

        Yes, some solutions can pass.

        But it hugely depends on constant factor, optimizations, etc.

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

    I also initially got TLE 21. After constant optimisations I barely got AC in 998ms (94776156). Maybe DP over carries in the sum isn't the intended solution :/

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

      You should use faster IO optimizations(for example getchar or fread)

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

These are what we sent and received for problem E during the contest:

The input is a floating number while we need to do binary decisions. Are the judge solutions accurate?

Yes

As nothing is mentioned about the number of digits of the input, we believe there exists a case where the judge solution is incorrect.

No comments

How many digits after the decimal point can the input values have?

4 decimal places.

The planned building area is represented as a rectangle with sides width and height. Is it always located at [0, width] \times [0, height]?

Yes

What is the constraints of N? If the only constraint is N Q <= 10^6, then there would be 10^6 * 40 points in the input.

N <= 150000

What do you think, community? I strongly hope that this kind of problem preparation be gone.

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

How to solve E: guess the statement.

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

Why does E have such a small amount of constraints? I don't see anything in the statement that guarantees that the input file is smaller than $$$10^{10^{100}}$$$ bytes.

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

How to solve div2-M ?

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

    Nevemind didn't see the Div2

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

I surely misunderstand E but cannot get what I'm missing.

How I understand E: Get the sum of the whole areas of the polygons that intersect with the given circle. But this is too easy, right?

I also don't get what that "planned building area rectangle" has to do with the problem.

Can someone point out what I'm missing here?

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

J — amazing time limit :)

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

    Am I the only one to solve it by looking up OEIS ?

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

      I wrote a bruteforce till the poly degree 10, then looked at the output)

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

      I used the same OEIS sequence.

      But, When I am precomputing with N=1e6+5 then I am getting AC.

      But when I am using N=1e7+5 then getting WA also after N=1e7+5 precomputation for all test cases with n>1000 I am receiving actualanswer+1. I don't get why I am getting actual answer+1 for N=1e7+5 precomputation.

      Can you tell me what's going on?

      Edit: Talking about Div2 J.

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

      For the sake of a solution which doesn't use OEIS (since our team didn't use OEIS), note that $$$7 = 2^3 - 1$$$, so expand the coefficients of the polynomial into their binary representation, and let $$$a$$$ be the sum of all powers of $$$2$$$ which have the first bit (from the right) set in the coefficient, $$$b$$$ be the sum of all powers of $$$2$$$ which have the second bit set in the coefficient and $$$c$$$ for the third bit.

      Then you have a bijection between the solutions of $$$a + 2b + 4c = m$$$ over non-negative integers $$$a, b, c$$$, and the set of all solutions in the problem statement, so we need to just count the number of solutions to the former equation. Now to count them, it suffices to count the number of solutions to $$$b + 2c \le \lfloor \frac{n}{2} \rfloor$$$, which turns out to be precisely the expression at OEIS.

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

      am I only one who overkilled this problem with a overcomplicated dp solution 94783445

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

        same here (with hard optimization)

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

          Could you explain your solution? I tried submitting a very similar dp solution here as well as during the contest but I can't seem to fit it in TL (I wrote an iterative dp too, but somehow it's slower than the recursive one because it visits all states).

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

Wasn't J can be solved by this sequence?

I got WA on test case 3? Can anyone tell me why my solution is wrong on n=10000?

Edit: Got AC when changed precomputation from 1e7 to 1e6.

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

Problem F.

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

    Problem J.

    Similar to a solution there, we can write

    $$$\begin{eqnarray} m&=&a_0+2a_1+2^2 a_2+2^3 a_3 + 2^4 a_4 + 2^5 a_5 + 2^6 a_6 + \cdots \\ &=&\left(a_0 + 8a_3 + 8^2 a_6+\cdots\right)+2\left(a_1+8a_4+8^2a_7+\cdots\right)+4\left(a_2+8a_5+8^2a_8+\cdots\right) \\ &=&x+2y+4z \end{eqnarray}$$$

    where $$$x,y,z$$$ can be any non-negative integer (since the coefficients can be between $$$0$$$ and $$$7$$$, and we've represented the numbers in base $$$8$$$).

    So the answer is the number of non-negative integer solutions to $$$x+2y+4z=m$$$.

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

      I really like this solution. Thanks. Much better than my very complicated proof of problem J.

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

    How do you come up with such an invariant? Is is something that is based only on intuition?

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

      Same, no idea how can we can come up with such solution. I can only see people reducing the problem to bitmask dp with O(t*64*8) at best.

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

Well that was awful.

  1. Statements are long and unreadable in places. You don't give accurate limitations.

  2. 15 problems for 3 hours with this kind of writing?

  3. I believe there are some interesting problems underneath but you buried them under (at least) 8 problems "write obvious solution in 200 lines of code"

  4. (That's my own butthurt, but) What's the point of giving 5e5 tests in J? What were you trying to cut out? Will the problem be worse with one test? Reading the input takes at least 0.3 sec with scanf wtf

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

    Couldn't have agreed with point 3 more -- as we were doing the non-mirror version of the contest, I think none of the team members did take a look in 7-8 problems at least

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

    J is O(1) per query

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

I think the test cases for Problem B are weak . My wrong code was accepted it seems. Link to my submission --> https://codeforces.me/contest/1424/submission/94787727 Though it got accepted It fails on this test case which I thought

5 9

1 1 1

1 2 2

1 3 3

1 4 4

1 5 5

2 1 6

3 1 7

4 1 8

5 1 9

The answer must be -1 and my code gives the answer as 9 and still got accepted. Please correct me if I am wrong somewhere.

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

This should have been a 5 hour contest and not 3 hours.

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

Can someone explain how to do F?

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

in problem L, tests have T_i == 0...

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

How did you write validator for problem M ?

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

I passed M 10 minutes after the game, (it looks like 20 minutes, that's because the codeforces main station seems to be banned by GFW for 10 minutes and i cannot access during the period), If it is a rated contest, I would regret it for a long time...What a sad story...

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

A neat solution to J:

Think of the answer to query $$$n$$$ as the n-th coefficient in the following polynomial: (where $$$B$$$ is some large number, greater than $$$10^{18}$$$)

$$$ \begin{aligned} &\prod_{i=0}^{B} (1+x^{2^i}+x^{2\cdot 2^i}+\cdots+x^{7\cdot 2^i})\\ =&\prod_{i=0}^{B} \frac{1-x^{2^{i+3}}}{1-x^{2^i}} \\ =& \frac{(1-x^{2^{B+3}})(1-x^{2^{B+2}})(1-x^{2^{B+1}})}{(1-x)(1-x^2)(1-x^4)} \end{aligned} $$$

After ignoring high order terms, it will be $$$\frac{1}{(1-x)(1-x^2)(1-x^4)}$$$. This is equivalent to complete knapsack problem with item weights $$$1,2,4$$$. A little bit math shows that the n-th coefficient is just $$$\sum\limits_{i=0}^{\lfloor \frac n4\rfloor}\sum\limits_{j=0}^{\lfloor\frac{n-4i}{2}\rfloor}1 = (\lfloor \frac n2 \rfloor - \lfloor \frac n4 \rfloor + 1)(\lfloor \frac n4\rfloor + 1)$$$.

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

    Div2 J : I used OEIS for generating the sequence formula.

    When I am precomputing with N=1e6+5 then I am getting AC.

    But when I am using N=1e7+5 then getting WA also after N=1e7+5 precomputation for all test cases with n>1000 I am receiving actualanswer+1. I don't get why I am getting actual answer+1 for N=1e7+5 precomputation.

    Can you please help me with what's going on?

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

    Here's a more combinatorial version of the same solution (which was how I came up with my solution). Note that $$$7=2^3−1$$$, so expand the coefficients of the polynomial into their binary representation, and let $$$a$$$ be the sum of all powers of 2 which have the first bit (from the right) set in the coefficient, $$$b$$$ be the sum of all powers of 2 which have the second bit set in the coefficient and $$$c$$$ for the third bit.

    Then we have a bijection between the solutions of $$$a+2b+4c=m$$$ over non-negative integers $$$a,b,c$$$, and the set of all solutions in the problem statement, so we need to just count the number of solutions to the former equation. Now to count them, it suffices to count the number of solutions to $$$b+2c\le\lfloor \frac{n}{2} \rfloor$$$, which turns out to be precisely the expression claimed above.

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

I could be wrong, but I think a lot of people had solutions accepted from problem B which should not have been accepted. The test cases were weak and new ones have been retrospectively added which would have resulted in failures.

Problem K (div1) / J (div2) was also very poor. The entire performance of the algorithm depended on reading the inputs fast enough. That is weak.

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

    Can you please explain how to solve Problem K (div1)/J (div2)?

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

      Sure:

      The first thing is to ensure you have a fastio configuration — otherwise reading / printing 10**6 times will be enough to TLE.

      After that, the problem is relatively simple. 1 is always lonely. Beyond that, as we extend the sequence 1,2,3,... etc, the newest number lonely iff it is prime. This is because otherwise we can write the number as n = pq, where p is the smallest prime divisor of n. Then q > 1, otherwise n is prime (contradiction). Take m = p(q-1), then we have the triangle p, q, q-1 which satisfies our requirements (since p>1 and p <= q).

      When does the prime stop being lonely? The prime stops being lonely when its square joins the set, since p*p, p give us the triangle p, p, 1. It is trivial to show that p is lonely before its square joins, since the triangle p, k, 1 is not possible for k < p.

      So we generate a list of primes < 10**6 (Sieve of Eratosthenes), and then precompute the answers from 1 to 10**6, adding one each time we hit a prime and subtracting one each time we hit the square of a prime.

      This can all be done is O(10**6) time.

      To get the required answers, we simply query our precomputed answers.

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

How to solve div2-B(valuable paper)? Thanks in advance:)

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

    I did a binary search on the answer, by removing all edges greater than a certain weight and then doing Hopcroft Karp to find a maximum matching, and check whether the matching is a perfect matching.

    However, there seem to be people who didn't use matching at all, and I'm curious about their solutions too.

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

      nor — I think your method is correct. Many people's algorithms were accepted incorrectly, and would now fail the new test case 21.

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

      Why do we need Hopcroft? I don't think it is necessary. I also thought of the maximum matching of the bipartite graph at first, but found it to be redundant. Just mark the two end points of each road and check whether all factories and airports are all marked.upd:Sorry, I thought about it carefully, and the maximum matching of the bipartite graph is indeed needed.

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

        https://codeforces.me/contest/1424/submission/94794499

        @mejiamejia — your code now fails the new test case 21

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

          Yes, the maximum matching of the bipartite graph is necessary. My algorithm is easy to have counterexamples, that is, a factory connects all airports, and an airport connects all factories. I thought of the wrong algorithm during the game because I felt it first The data range of is very large, and running the bipartite graph matching will exceed the time limit.

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

            I got hacked at my submission 94774721, but my intended solution was based on Hall's theorem.

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

            Yeah — I failed to come up with a bipartite matching that satisfied the time constraints. Tricky problem, made to look easier than it was by the poor test cases.

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

      It was simple greedy tbh. Just greedily remove the high weight edges as long as it is possible. The first edge that we cannot remove is our answer.

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

        What is the condition of not being able to remove the last edge?

        In my solution, I assert that the condition is that $$$MaxMatching(resultantGraph) < N$$$, and if there is a simpler condition that this degenerates to, please let me know the condition and a proof of it.

        EDIT: https://codeforces.me/contest/1424/submission/94802563 Your solution (AC in the contest) gives WA on test 21 on resubmitting (added after the contest).

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

What's wrong with this test to M?

3 3
2 3 4
4 1 3
5 4 2
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    I suspect that the validator is wrong in M... Could somebody elaborate?

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

      Validator checks only if matrix is Monge array, as we used Monge arrays for the test set. The solution doesn't use any properties specific to Monge arrays, and it works for any matrix that satisfy constraints from the problem statement. We'll try to fix the validator.

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

        Even though a validator and decent tests are way easier to make than the solution to the problem, none of those existed in this problem and only monge arrays were used. I wonder why...

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

          I mean, I believe SMAWK works also for the matrices they described in the task statement... Even they described those matrices in the paper (Section II).

          Does this mean this is a great task? /s

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

        Since the validator still isn't fixed, hopefully putting a fixed version here will help change that.

        Correct validator

        It's also possible to make the time complexity of the validator $$$O(nm$$$ $$$log$$$ $$$m)$$$ with divide and conquer but the speed difference isn't that big.

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

http://codeforces.me/contest/1424/submission/94795249 Could anyone please explain why this is giving TLE??

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

By when shall we expect the editorials Acko?

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

Sorry, I'm greedy, uphacks on B, C, M, and N weren't enough for me:

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

    Yeah, I believed that it is almost impossible to solve (even to read the input for) the case with $$$n = 10^6$$$ and $$$q = 1$$$. That's why we issued a clar and told that "N <= 150000" and "4 decimal places."

    Based on your hack, it seems that the validator seems to check $$$n \le 150000$$$, I suspect it does not check the number of the digits; chance for yet another unexpected verdict :)

    Edit: Oh I misread the numbers of your hack. I must admit I assumed that the test data is not too strong during the contest. Kudos for hacks.

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

why there is no system testing?? Many group solve the question no B valuable paper using binary search but they actually got wrong ans in test case 21 that i think added after the contest. So if system testing is there then i think they might got why their logic get WA on test case 21. Please pay attention what i have said. Thank you.

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

    Test case 21 was added in uphacking.

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

      okk but why there is not any system testing??

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

        Because all solutions were tested on all test cases during the contest.

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

          but before system testing i think the uphacking test cases are also added

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

            Uphacking happens after the contest and lasts for 7 days. They aren't just going to rejudge all solutions 7 days after the contest.

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

The statement in M says: $$$1 \leq n, m \leq 10^6$$$. I looked through the tests and saw that all tests have $$$1 \leq n, m \leq 10^3$$$. Moreover I tried uphacking some solution with tests with $$$n, m = 1001$$$ (https://codeforces.me/contest/1423/hacks/669698) and it says "FAIL Integer parameter [name=rows] equals to 1001, violates the range [1, 1000]".

Why is that?

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

I did a weird constant optimization for J.

We can write $$$m_i$$$ as a binary string with length $$$L=60$$$. Let $$$M=8$$$ be the size of coefficient set. We can write a DP solution in $$$O(t \cdot L \cdot M)$$$. However, this approach TLEs.

I decided to divide the string with length $$$L$$$ into blocks of size $$$B$$$. We can precompute the DP transition matrix for all binary strings from $$$0$$$ to $$$2^B-1$$$ in $$$O(B \cdot 2^B \cdot M^3)$$$. Then, for each $$$t$$$ queries we can multiply $$$\lceil \frac{L}{B} \rceil$$$ matrices with the base case matrix in $$$O(\lceil \frac{L}{B} \rceil \cdot M^2)$$$ to get the answer.

Thus the final complexity is $$$O(B \cdot 2^B \cdot M^3 + t \cdot \lceil \frac{L}{B} \rceil \cdot M^2)$$$. Picking $$$B=12$$$ passes the testcases. Submission.

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

    It's not that weird, similar trick is used in some theoretical algorithms like: 1 2 3

    What is imo a little weird is that this trick indeed improved actual running time enough to get past TL instead of just improving theoretical time complexity.

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

Problem M of Div 2

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

I wonder what "Unexpected verdict" means?

ps: I found it in Hacks.

thx

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

    Most probably: one of the model solutions failed on the hack. Or maybe the checker failed. There are probably some other possible reasons, too. Either way, it implies that the organizers botched something.

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

Shall we even expect editorials? Acko

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

How to solve Lonely Numbers — Div1 problem K — Div2 problem J

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

    Observations:

    1. $$$1$$$ is always lonely;

    2. primes greater than $$$\sqrt{n}$$$ are always lonely ($$$P$$$ can never pair with $$$k\times P$$$ for $$$k<P$$$);

    3. primes no greater than $$$\sqrt{n}$$$ can always pair with its square;

    4. composites can always be expressed as $$$x \times y$$$ where $$$x$$$ is its smallest prime factor, thus they can always pair with $$$x \times (y-1)$$$.

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

Editorial ??

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

Problem E has a lot of issues with hacks.

It's too easy to generate a hack, just print as many integers as you can. In fact, I hacked all but two solutions like this. Also, input validation is bad, it doesn't check whether polygons intersect. In fact, you can just print the same polygon as many times as you want. It's also kind of impossible to do within reasonable time.

My suggestion: remove all hacks, restore testcases to the official ones used for the BC finals, and disable hacks for this problem.

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

Can somebody tell me why are these two problems having this high rating difference in spite of them being the same problems :
PROBLEM1 -> 2200 rating
PROBLEM2 ->1600 rating
I literally used almost the same solution for both the problems

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

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

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

@Acko ： My team's name is "5times187" .

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

Can anyone give me a hint of how to optimize bitmask dp in Div 1 problem J ?

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

I tried the problem 1424G many times but its giving wrong and on 7th test case. Can anyone tell the idea behind the question or provide with a solution

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

Orz Itst pupiI and newbiegcz!

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

Can someone tell me why am I getting a TLE here https://codeforces.me/problemset/submission/1423/99648601

→ Reply