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

Автор Acko, история, 4 года назад, По-английски

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.

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

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

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

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

plz check. the register doesn't work.

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

[Deleted]

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

why I am able to register in Div1 also ?

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

is it rated?

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

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

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

How many participants allowed in a team?

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

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

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

Number of problems is secret?

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

Problems are not sorted by difficulty, right?

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

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

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

    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)

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

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?

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

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

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

      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

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

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.

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

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

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

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

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

      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.

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

I didn't expect 14 questions.

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

Why the TL for J is so tight?

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

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.

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

How to solve E: guess the statement.

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

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.

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

How to solve div2-M ?

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

    Nevemind didn't see the Div2

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Topological sorting
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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?

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

J — amazing time limit :)

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

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

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

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

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

      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.

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

      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.

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

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

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

        same here (with hard optimization)

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

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

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

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.

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

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

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

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

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

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

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

      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.

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

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

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

    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

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

    J is O(1) per query

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

I think the test cases for Problem B are weak . My wrong code was accepted it seems. Link to my submission --> https://codeforces.net/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.

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

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

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

Can someone explain how to do F?

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

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

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

How did you write validator for problem M ?

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

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

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

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

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

    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?

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

    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.

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

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.

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

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

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

      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.

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

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

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

    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.

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

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

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

      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.

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

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

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

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

          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.

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

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

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

            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.

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

      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.

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

        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.net/contest/1424/submission/94802563 Your solution (AC in the contest) gives WA on test 21 on resubmitting (added after the contest).

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

What's wrong with this test to M?

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

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

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

      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.

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

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

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

          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

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

        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.

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

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

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

By when shall we expect the editorials Acko?

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

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

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

    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.

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

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.

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

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.net/contest/1423/hacks/669698) and it says "FAIL Integer parameter [name=rows] equals to 1001, violates the range [1, 1000]".

Why is that?

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

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.

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

    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.

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

I wonder what "Unexpected verdict" means?

ps: I found it in Hacks.

thx

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

    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.

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

Shall we even expect editorials? Acko

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

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

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

Editorial ??

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

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.

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

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
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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