cip999's blog

By cip999, 2 months ago, In English

We hope you liked the problems! Before we go ahead with the editorial, let us make some general comments about this round.

Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters. Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems.

There were three big "jumps" in the difficlty gaps between consecutive problems. Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them). Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution). The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder). Sadly, we discovered 14 minutes into the round that problem I has already appeared in a contest (most likely also in Polish contest, if you know it please tell us in the comments). See also this comment.


Pre-contest predictions


Detailed overview on the problemset and a bit of behind-the-scenes


Which author did what?


Some thoughts from cip999


Hints and solutions


A


B


C


D


E


F


G


H


I

If you find any typo, feel free to tell us with a comment. Moreover, if you want to share your opinion on the problemset, we are eager to read it.

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

»
2 months ago, # |
  Vote: I like it +69 Vote: I do not like it

Great problems, but too hard for me :,(

»
2 months ago, # |
  Vote: I like it -40 Vote: I do not like it

Everywhere graph . Why :|

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solutions and Implementations aren't visible. Kindly fix it. Thanks.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just read what the editorial says, "As of now, only hints are available"

»
2 months ago, # |
  Vote: I like it +49 Vote: I do not like it

One of the finest rounds on codeforces. kudos to the problem-setters!

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Great Problems.

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Tooooooooooooooooooo.. Hard. Yet, very interesting.

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

.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, won't only the winners(getting best standings) of the 5 marathons be the only potential candidates for the gold medal? Please, someone, help

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    Consider this case:

    1

    6

    2 2 2 2 2

    1 6 6 6 6

    6 1 5 5 5

    5 5 1 4 4

    4 4 4 1 3

    3 3 3 3 1

    1 is the only one that can get a gold medal, but he didn't win any marathon

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks Man

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I tried to solve similar way, whose rank-sum will be less than will be a potential winner but I got WA.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Just consider the following case:
        Number of participants: 5
        Marathons and ranks:
        M1: 1 2 3 4 5
        M2: 1 2 3 4 5
        M3: 1 2 3 4 5
        M4: 4 2 3 5 1
        M5: 3 2 4 5 1
        2 has the lowest 'ranksum', still 1 is the winner.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, but in this case, we simply take a lower index if the sum is equal???

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

            By 'ranksum', you mean the sum of the ranks of the player across the 5 marathons, right?

            What I am trying to say is that the concept of 'ranksum' is of absolutely no use in some cases, as the superior athlete might not actually have the lowest ranksum.

            In the above example itself, the ranksum of the superior athlete 1 (0 + 0 + 0 + 4 + 4 = 8) will be greater than the ranksum of the athlete 2 (1 + 1 + 1 + 1 + 1 = 5), even though 1 is the superior athlete...

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it -14 Vote: I do not like it

              Yeah, now I got your point but I am unable to find any such example. Below is my code it's a little bit hard to understand. Thanks.



              void solve() { int n; cin >> n; vector<vector<ll>> v(n, vector<ll>(5)); vector<pair<ll, ll>> sum(n); ll temp = 0; for (int i = 0; i < n; i++) { temp = 0; for (int j = 0; j < 5; j++) { cin >> v[i][j]; temp += v[i][j]; } sum[i] = {temp, i + 1}; // putting rankSum in vector } sort(sum.begin(), sum.end()); temp = sum[0].second; // taking index of lower rankSum vll m(5); ll flag = 0, k = 0; for (int j = 0; j < 5; j++) { flag = 0; for (int i = 0; i < n; i++) { if (v[temp - 1][j] < v[i][j]) { flag++; } } m[k] = n - flag - 1; k++; } if (n % 2 == 1) { n--; } for (auto x : m) { if (x > n / 2) { cout << -1 << "\n"; return; } } cout << temp << "\n"; }
              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Your code is throwing a lot of compilation errors.
                You could try attaching a link to your WA solution instead, though I don't feel that it's necessary.
                Your code should fail this Test Case (the correct answer here would be 1):

                1
                5
                1 1 1 5 5
                2 2 2 2 2
                3 3 3 1 1
                4 4 4 3 3
                5 5 5 4 4
                
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Okay, i will check, But my code is fine you just have to take main function and put a loop inside main for test case. anyway Thanks for help.

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

    Edit-> definitelynotmee already answered it above, Thank you

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do you think your #2 will always pick the right candidate (if there's any) ?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep I had that incorrect insight too; I should practice more hehe

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

In Problem D, I wrote down some examples and observed 3 ways to get a YES answer (First of all I converted all the negatives elements to positive because since we have been given differences, the sign doesn't matter) :- 1) If there exists a 0 in the array. 2) If there are repetitions in the array. 3) If there exists more than one subset sum in the array. :)

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

    I had the same solution XD The fun part is that I didn't fully understand why would this work but it passed pretests.

    But if you look at the formula in the editorial and move all the negative elements onto the right hand side of the equation (either because they were negative in the first place, or because $$$s_i = -1$$$), suddenly we have the formula we came up with: sum of at least two subsets of absolute values must add up to the same value. It is $$$O(2^n)$$$.

»
2 months ago, # |
Rev. 2   Vote: I like it +64 Vote: I do not like it

I have an $$$O(2^n\cdot n)$$$ solution for D. I don't know why does it work:

Solution
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Great approach but how it works

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it is basically same as editorial solution . Let there exist 2 subset A and B which have equal sum then we can take element of A with positive sign and element of B with negative sign so the total sum of subset (A +(-B) ) =0.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Can you give an example how to construct the array b given two subsets are equal? Thanks.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Suppose A[] = {5,3,8} then you can generate an array B[] = {5,8,16}, we can generate this because we have two subsets (1,2) and (3) with equal sums.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Thanks. Can you explain the construction for A[] = {-3, 6, 10, 1, 12, 100} subsets (1,2,3) and (4,5) have same sum (-3 + 6 + 10) = (1 + 12) = 13

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              I have understood. {0, -3, 3, 13, 1, 100}

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    The target of this problem is to build an array b that contains n numbers instead of n+1 so that if there are 2 subsets have the same sum S, you can build an array b having n+1 numbers with S appears twice, and you just delete one of it to make an array b have n numbers.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanku

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Thanks!

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      you can build an array b have n+1 numbers with S appear twice

      Can you explain this line?

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        We call 2 subsets have sum $$$S$$$ with $$${a[i1], a[i2], ..., a[ik]}$$$ and $$${a[j1], a[j2], ..., a[jr]}$$$ We know that these $$$r+k$$$ elements have distinct index in $$$a$$$ which mean $$$r+k \leq n$$$.

        Let build array $$$b$$$ in this way :

        • $$$b[1]=0$$$

        • $$$(2<=y<=k)$$$ $$$->$$$ $$$b[u+1]=b[1]+a[i1]+...+a[iu]$$$

        • $$$(k+1<=u<=k+r)$$$ $$$->$$$ $$$b[k+u+1]=b[1]+a[j1]+...+a[ju]$$$

        For any element in other $$$n-(r+k)$$$ elements in $$$a$$$, we can easy set to last $$$n-(r+k)$$$ elements in $$$b$$$. Now we have array $$$b$$$ with $$$n+1$$$ elements and we also have $$$b[k+1]=b[k+r+1]=S$$$. Now just remove $$$b[k+1]$$$ to make array $$$b$$$ with $$$n$$$ elements.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey I used the logic that if there is atleast 1 combination of Ai whose sum is equal to the some Aj then we don't have to make a segment for it and it can be done in n Bi otherwise n+1 Bi will be needed but it is giving me NO instead of YES for this test case. 9 25 -171 250 174 152 242 100 -205 -258 Can anyone explain why it is not working? Here is the code for reference

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks it helped me a lot

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

      Thanks, you helped me a lot!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can forget to handle the case when there's a zero in the array. Because one of the subsets is empty set and the sum of it is equal zero. so if there's any zero in the array , the length of the set(sum) will be less then number of subsets.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I also did problem B in O(nlogn) but i used sorting

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you used the STL sort then I think it is a UB.suppose A,B,C are any structs that you sort,the STL sort only works when if A>B,B>C,then A must be bigger than C,Otherwise the sorted result might be a complete mess.Sorry for the bad grammar.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used sort with comperator function and also after sorting I iterate over all thing to check weather it holds satisfies condition or not

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

      can u elaborate more??

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Did the setters anticipate non-bitmask solutions to G? It seems that even with some careful book-keeping to avoid performing any $$$O(n)$$$ calculations at the critical deepest level of recursion, the time limit is still pretty strict for these solutions.

My contest solution (123766099) keeps the non-recursive part of every loop at $$$O((k+1-i) \cdot (1 + |S_i \setminus T_{i-1}|))$$$ by following the set and un-set bits to their destinations in advance and attains something close to $$$O((\frac{n+k}{k})^k)$$$ performance. (It's technically a bit worse for large $$$k$$$, but that's not very relevant to this problem.)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is possible, albeit requires some optimization (or, for example, the second observation described at the end of the editorial), to get accepted without using bitmasks.

    While preparing the problem, I wondered if it was better to give the problem with $$$n=50$$$ (which obliged to use bitmasks) or $$$n=40$$$ which allows many more solutions to get accepted. At the end I decided to go for the "low-constraints" version since the gap between F and G was already rather big.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +38 Vote: I do not like it

      I don't think the second observation by itself would have been enough for my own implementation, since the ratio $$$5^{10} : 6^4 \cdot 5^5 \approx 2.4$$$ it seems to actually save isn't very big, and my own idea (which I estimated saves a factor of about $$$40/5 = 8$$$) didn't yield so much headroom. I should look over the other slow solutions and try to see what ideas they used.

      It's also very possible that my implementation is just rather slow. But if non-bitset solutions were intended to pass, it seems perhaps a bit strange to keep the time limit at one second.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did problem B using a comparator function 123741857

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

    Hey, I also used a similar approach(123769494), but I'm not sure how is this working because,

    If A is superior to B and B is superior to C, then it is not always true that A is superior to C(like in the given test case). This would probably give the wrong sorted order, right?

    Can you please explain why is it working?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Suppose A,B,C,D is the order you get after sorting. Then, D cannot be the answer as C is superior to it, similarly C cannot be the answer due to B, B cannot be due to A. So if any answer at all exist it has to be A.

»
2 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

Typo: The latex in hint 3 for H is currently broken

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Is it only me or the "Hint 3" in problem H is bugged?

»
2 months ago, # |
  Vote: I like it +245 Vote: I do not like it

Don't ever upsolve. If a problem appears at one contest, what is the chance it will appear at another? - Gennady Korotkevich

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I have another way to do in problem D. First, if there is some zero in the given set, the answer is YES. Otherwise, consider the absolute values |a1|, |a2|, ..., |an| and check whether there are two distinct subsets of the new set s.t their sum are equal. This can be done in O(n.2^n).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How is it supposed to solve D in $$$O(3^n)$$$? Is it a typo, while the actual complexity is $$$O(3^n\cdot n)$$$?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You are right! It has been corrected in the tutorial, but it might take some time to render in the blog.

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

    I solved it in O(3^N). Precompute the sums in O(2^N) or O(2^N*N) then iterate through the pairs of non-intersecting subsets.

»
2 months ago, # |
  Vote: I like it +65 Vote: I do not like it

Hello authors,

Thanks for the great contest, all the problems I read were interesting and entertaining to solve and think about.

However, one decision I am confused about is the omission of a max pretest for D. There was no pretest that had 20 test cases of n = 10, and this lead to people FSTing. My solution ran in less than 200 ms on pretests, and so even though I was suspicious of my complexity, I figured that my solution for D was okay, yet it still FSTed.

Next time, please include max tests in the pretests so contestants can be rather certain their solution will pass under the time limit.

»
2 months ago, # |
Rev. 6   Vote: I like it +9 Vote: I do not like it

Sadly, I got FSTed for D. Interesting problems btw. Kudos!

Edit: Can anyone explain why I got TLE for D while the time complexity seems to be n * O(2 ^ n)? 123771731

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    rep(i, 0, elements.size()) { rep(j, i+1, elements.size()) { if(abs(elements[i] - elements[j]) == curr) { return rec(arr, idx+1, elements); } } }

    Just because of this loop your complexity is already at least O(n^2*2^n). There are also 20 test cases. That already puts you at O(10^8). Add any major inneficiency and it's time limit (like what happened).

    For that solution you could just store everything on a set end check in the end if the size of it is equal to 2^n, you really didn't need to make your life hard. Also cout.tie(0) litterally does nothing

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the explanation. I'll keep these things in mind.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

1552C - Maximize the Intersections I still completly do not get why we can ignore the initial chords configuration. The editorials seems to not explain it further. Is that something so obvious?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    It's not obvious, but the idea is that you can consider a pair of new chords separately from any pre-existing chords. Let's say there are multiple chords already drawn, and you now have 4 free points ($$$A,B,C,D$$$ in that order), and you must draw two chords. You can convince yourself that the configuration $$$AB$$$ + $$$CD$$$ intersect the same number (or fewer) previously drawn chords as the configuration $$$AC$$$ + $$$BD$$$, but since $$$AC$$$ and $$$BD$$$ intersect themselves, this configuration is better.

    I hope that it's somewhat clear. It's the usual swapping argument employed in proofs of greedy solutions.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As there is only one configuration that is giving the maximum we can ignore initial chords. If that is not the case then we can't ignore the initial chords.

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

"Problems A and B are meant to be easy!" Really?

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I had a different approach for problem F:

First of all, compress all coordinates so each of them is not greater than $$$2n$$$. The solution below uses 1-indexation for compressed coordinates. The original coordinates are kept in array c.

Then do some kind of right-to-left dp, let's call it over. over[i] means the number of times the ant goes from point i - 1 to point i. Then the answer is clearly $$$\left(\sum_{i = 1}^{2n}over[i] \cdot (c[i] - c[i - 1])\right) + 1$$$.

The point is how to calculate the over dp. There are two cases:

  • i-th coordinate is y for some portal p. Then over[i] = over[i + 1] - cnt where cnt is the number of telepantings through the portal p. It can be easily found as over[p.x] - over[p.x + 1].
  • i-th coordinate is x for some portal p.One can notice that in the half of the cases the ant is moving forward, so over[i] = 2 * over[i + 1] +- 1 (+-1 depends on the initial activity of the portal).

You can read the code here (123756889) or

here
»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I think I have done problem B in more simple way. All I did is 2-d vector sorting using my own compare function.
Compare function code:

compare function

Only first athlete in sorted vector will be contestant to be superior. Just have to check that.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate your logic that how sorting helps in solving this problem!!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because my compare function will automatically bring superior athlete forward.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

D can be solved in O(2^n). It's sufficient to check if two subsets have the same sum.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how does this works?

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

      This works because in a single subarray of B[] we can get at least two elements of A[].

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shouldn't they need to ne non intersecting as well? For ex-: If we have a1+a2-a3-a4+a5-a6=0 => a1+a2+a5=a3+a4. I think that's why you are telling that the two subsets should have the same sum. But, then won't they also need to be non-intersecting?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by non-intersecting?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Two sets having no element in common. Like {a1,a2} and {a3,a4} are non-intersecting but {a1,a2} and{a2,a5} are intersecting.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Okay, then we don't need to check if they are non-intersecting. Take the example, {a1,a2} and {a2,a5} which are two intersecting subsets which have same sum. a2 is common. so we can find {a1}, {a5} which are two non-intersecting subsets which have same sum. It is same for each intersecting subsets. I hope you understood :D

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks ! Learnt a new thing!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2 problem is similar to find the celebrity problem which can be done using recursion https://www.geeksforgeeks.org/the-celebrity-problem/

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Alternative solution to 1552F - Telepanting

Let $$$z_i$$$ be the index of the teleporter reached immediately after using the teleporter $$$i$$$ (it can be calculated by binary search).
Let $$$dp_{i,0}$$$ be the number of times $$$x_i$$$ is reached. Let $$$dp_{i,1}$$$ be the number of times the teleporter $$$i$$$ is used. Then, the answer is easy to calculate (you spend $$$x_{z_i}-y_i$$$ time for each teleporter, and if the teleporter is inactive you spend $$$x_{i-1}-x_i$$$ time).
You can calculate $$$dp_i$$$ in decreasing order of $$$i$$$ by obtaining it from the recurrences
$$$\displaystyle dp_{i+1,0} = \sum_{z_j=i+1}{dp_{j,1}} + \lfloor \frac{dp_{i,0} + (s_i \oplus 1)}{2} \rfloor$$$
$$$\displaystyle dp_{i,1} = \lfloor \frac{dp_{i,0}}{2} \rfloor$$$

As there could be multiple possible values of $$$dp_{i,0}$$$, you have to choose the one with the same parity as $$$s_i \oplus 1$$$ (because all the teleporters are active at the end). This can be done by using mod $$$1996488706 = 2 \cdot 998244353$$$.

Submission: 123775629

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    Nice solution! If I had to guess, I would have said it is impossible to solve this problem without the observation that all portals with $$$x_i < x$$$ are active when the ant is located at $$$x$$$, but it looks like your solution doesn't require this (only that all portals are active in the end). Thanks for sharing.

    I'll try to include it in the editorial, provided that the gods of Polygon are in my favor.

    Edit: Solution added to the editorial (actually explained in a slightly different manner, but hopefully correct).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The Key for Problem B is only one will be the winner and he will be superior to everyone! By the way very good questions

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

One of the best tutorial sections of all time! Though I got demoted to pupil :(, still a nice contest! @cip999

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Magnificent editorial! I wish all editorials would be at least as detailed as this!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Editorial Ever. Would like to have such types of more Editorials :)

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I really liked the contest, since it had a lot of interesting and fun problems.

For me personally it was a bit sad, that my "solutions" A, B, C & D all passed the pretest without any problems, but later my solution for D failed with a TLE although it only took me ~300 ms to pass the pretests.

Since I am new to codeforces, I would like to ask if this is the standard (you are responsible for your own code, so you have to calculate the complexity) or if you normally should be rather safe with a ~300 ms.

Great contest! Looking forward to more :)

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Thank you for the contest!

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

bad pretest for B:,(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I became an International Master after this Round.Thanks to cip999 and dario2994 :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can come up with a solution to problem B, which is referred to as 3rd Solution.

I define a comparison between athlete $$$i$$$ and athlete $$$j$$$, athlete $$$j$$$ is called "greater" than athlete $$$i$$$ if and only if athlete $$$i$$$ is superior to athlete $$$j$$$. After sorting the athletes by this compare, each of them, except the first one, will have at least one athlete that come up before and superior to them.

Finally, we check whether the first athlete is superior to everyone else or not.

Implement: https://codeforces.cc/contest/1552/submission/123730552

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually i also tried this type but in the cmp funtion their i messed up 123750135

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      WRONG
      bool cmp(vector<int> a, vector<int> b) {
        int cnt = 0;
        rep(i, 0, 5) {
          if (a[i] < b[i]) cnt++;
        }
        if (cnt > 2) return a < b;
        return b > a;
      }
      
      ACCEPT
      bool cmp(vector<int> a, vector<int> b) {
        int cnt = 0;
        rep(i, 0, 5) {
          if (a[i] < b[i]) cnt++;
        }
        return cnt > 2;
      }
      
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This solution is broken, because it relies on undefined behaviour. The input data and the comparator do not satisfy the transitivity requirement. If A < B and B < C, then A < C must be also true. This kind of violation is similar to relying on a wrong use of <= operator in a comparator (which is known a bit better to the general public).

    Now I'm not sure if it's really possible to hack your solution in practice. Some implementations of sort could theoretically go into an infinite loop and give you a TLE. The others could crash. Using various combinations of search keywords "transitivity", "sort" "crash", "segfault", "infinite loop" on google shows that bad outcomes happened to be a reality at least in some cases.

    Just consider yourself lucky and don't do it again. An unintended bad thing about problem B from this contest is that it rewards incorrect code with a positive stimulus.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the D problem with a approach different from the editorial . Have a look at it. I find it interesting. 123742321

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

i got first time +140 in this round XD

the best ever contest for me

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The problem C is very very difficult.

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone who solved E during Contest explain what went through their mind while solving it? Did you prove the solution u coded ? And what's the first thing came to your mind when u looked at weird ceil(n/(k-1)) constraint?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    What came to my mind was that there might be a way to split colors into groups of $$$k - 1$$$ such that the intervals in each group do not intersect with each other.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried basic strategy on samples + few handwritten tests, and it gave correct answers. I tried to prove but without hope. There was nothing to do. So I've just implemented it. It passed pretests, so even though if it was wrong solution, I didn't care. So if FST would happen I would just "well, shit happens". Ah... it was second solution from editorial.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

If there is more than such one athlete, print any of them. Can Someone told me important of this line in Problem B.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they just didn't want to make the observation that there is always at most 1 athlete obvious

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    It's normal question from participant: what if several athletes might be answer, which one output? To avoid giving key hint that it's always unique, this statement is included.

    Also, there is often statement "Output -1 if there is no solution" in problems that always have solution.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else try doing B with bitmasks?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem B I tried defining a class of runners and defined the way for the array of runners to be sorted (Check if first runner has better rank in at least three marathons than the second runner). The test cases passed but I kept getting runtime error on my submissions. Can anyone point out why? Here's my code:

123745722

Edit: Got it. The relation between runners is not transitive.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my randomized solution didn't work? https://codeforces.cc/contest/1552/submission/123740930

Also I tried copy pasting the solution given in editorial but it got TLE as well. https://codeforces.cc/contest/1552/submission/123800021

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why I am getting a TLE in my solution of problem B?? 123801888

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your Solution is correct Just pass your 2D vector to check function by reference and it will get pass ! bool check(vector<vector> &m,int j,int k)

    like this !

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks bro, Yeah it got AC but can you explain why it was getting TLE??

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        By default the arguments are passed by copy. Every time you call that function, the vector must be copied. But you don't need that, you pass it by reference so it won't be copied, it will use the original vector

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Federico in B made me think about Federico Chiesa. LOL :)). Anybody have the same imagination?

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

I think I have an interesting and easy-to-understand solution for B.

Here's the idea:

  • Keep a knockout style tournament

  • Each player will play 2 other players ( n-1, and n+1)

  • Only those players who have won both their matches will advance to the next round

  • Eventually, only one person will remain. (Possible winner)

  • To check if he's the actual winner, see if he's superior to all other players.

Example:

  • First round -> 1, 2, 3, 4, 5, 6, 7
  • Second round -> 2, 4, 6 (2 won against 1,3; 4 won against 3,5; 7 won against 6,1)
  • Third round -> 6 (Only 6 won against 4,2)
  • Now, apart from 6, all other players have lost at least once, so they can't get the gold medal.
  • The only thing remaining is to check if 6 is superior to all 6 other players.

Code: https://codeforces.cc/contest/1552/submission/123742601
Complexity: O(n*logn)

What are your thoughts?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem B please add the two pointers tag as well. The situation in the problem is like a knockout tournament where one who loses a match would be eliminated and at last only one player would be left. Then simply check if this player can defeat all other players or not. If yes the answer is YES else NO. The time complexity is O(n). code

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please share the code for D using knapsack!

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

tourist is Lionel Messi of cp. GOAT.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody share the O(nlogn) algorithm mentioned in problem C solution?(=-=)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can Binary Search be applied? I could not come up with required O(NlogN) solution, but this may help someone

    You might have already thought about this
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Submission Let's have two ranges [a,b] and [c,d] such that a<c. Now both ranges will intersect iff c<b<d. I used ordered_set to count the no of such endpoints for a range. Since I added the endpoints in increasing order of starting points, all such endpoints will be valid.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nu cuoi da tat vi mim qua dak

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Editorial I have seen ever, thanks

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've seen some solutions for E that do not seem to explicitly check for the ceil(n/(k-1)) constraint and greedily make "n" passes over the array and on each pass tries to pick disjoint intervals whenever it can. (Here's a sample submission that does this).

Does anyone have a proof that this won't violate the ceil(n/(k-1)) constraint ?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I am getting TLE in B .It is stillO(N).

Spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are calling the get_sp and find_sp as call by value and because of this the data copying is taking a lot of time. Instead , call the function by using call by reference methodology. Also, there is no meaning of calling the get_sp function again, you have already stored it's output in b variable (although it won't cause tle).

    Tuned Solution for reference(123892742)

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

O(N log N) solution for problem C:

I used indexed set but could also be done using segment tree.

Spoiler
»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Seems like sansen is hacking everyone's G and most of them are failing with TLE, does that mean the system tests were weak? Sorry if I'm getting this wrong

reference:
https://codeforces.cc/contest/1552/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=G
https://i.ibb.co/YPDkbV9/hacks-1.png

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    Actually I am curious about that. I had worked pretty hard to make the tests decent (both to fight against randomized solutions and to fight against slow solutions), but I must have failed if $$$\ge 10$$$ solutions out of 50 are hacked. Please sansen explain your trick.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      Most of the hacked submissions are dp-like solution. The complexity is the same as Editorial, but it uses a lot of memory and has a large constant factor. However, in the prepared testcase, there were a lot of state collisions, so it was very fast.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem E,why can construct it? I don't understand.who can help me?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What didnot u understand? I can try to explain it to u.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      can you speak Chinese? ,my English is not good,but I accept English, my question is why can prove two intervals selected in different steps are disjoint,programme is understanded for me,but why?

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

        Xi,s+1<Xj,s+1, because x was sorted and if Xi,s+1>Xj,s+1 we have took j first ans then i. Xj,s+1 <= Xj,t because s<t
        P.S. Sorry for my English...

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem E [n / (k-1)] can be 0, if k — 1 > n. In this case there is no answer, but "One can show that such a family of intervals always exists under the given constraints." Help me, please.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain why do we swap c and d in the intersect function in problem C Is that done to cover the part 1 of the tutorial can someone clearly explain it please Just the second line of the intersect fucntion is enough to check the intersction is happening or not right?? why do we swap c and d??

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

Interesting observation in Problem E I haven't seen mentioned yet. One can look at the special case $$$n=k-1$$$. Then we have the case, that each number belongs to at most $$$1$$$ interval. We can solve this and use the solution to solve the general case.

In the general case we have $$$n$$$ and $$$k$$$ and at most $$$\left\lceil \frac{n}{k-1} \right\rceil$$$ intervals. Then we can split up the $$$n$$$ numbers arbitrary into $$$\left\lceil \frac{n}{k-1} \right\rceil$$$ separate groups with each containing no more than $$$k-1$$$ numbers, and solve each group separately. (I guess, this is the meaning behind hint 1.2)

This isn't the best way to implement the solution, but this train of thought really helped me to come up with a solution.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can B problem be classified as some sort of Celebrity Problem ?

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

Can someone explain this part of greedy solution for problem E:

We can say more: the rightmost endpoints of these intervals must belong to $$$[x_{i,j}, x_{i,j+1}]$$$; indeed, if it weren't the case for at least one interval $$$[a, b]$$$, the interval $$$[x_{i,j}, x_{i,j+1}]$$$ would come before $$$[a, b]$$$ in the ordering, so it would actually have been selected.

I agree that interval $$$[x_{i,j}, x_{i,j+1}]$$$ would come before $$$[a, b]$$$ in this case. But we might not select it based on requirement #2. Am I missing something?

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

    The contradiction is exactly what happens if we don't choose any segments because of requirement #2.

    For each of the k-1 segments we could choose there was already (n)/(k-1) segments that had their right endpoints inside of [xij,xij+1] (otherwise, it would come before in the ordering and be choosen instead).

    That way there should be (n)/(k-1)*(k-1) distinct segments, or n segments for n-1 colors, leading to a contradiction.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He was asking why $$$[x_{i,j}, x_{i,j+1}]$$$ must have been selected if it comes before $$$[a, b]$$$.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And i was answering that. Funnily enough i think we both said the same thing with different words

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My bad. I didn't fully understand your comment so I wrote my own. Just reread yours and it's much clearer now.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Took me an hour to understand the explanation :D I finally did!

      Thank you!

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

    I think the author meant we can always find $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals with their right endpoints inside $$$[x_{i,j}, x_{i,j+1}]$$$. If it were not the case, at the time we considered $$$[x_{i,j}, x_{i,j+1}]$$$, we would have selected it.

    Now for each of the $$$k-1$$$ intervals for color $$$i$$$, we have $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ distinct intervals. In total, we have $$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$ distinct intervals, leading to a contradiction since we can not have $$$n$$$ intervals for $$$n-1$$$ colors.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B, any two pairs, one must be superior to the other, right?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved problem C differently.

Suppose, total numbers of point is 2n, and there is an unselected point say, P. There is also an array usp[2n+1] where usp[i] contains the total number of unselected points before i th point.

If I can find another unselected point x > P such that value of min(usp[x]-usp[P],total_unselected_points — usp[x]) is maximum, then we can connect P and x. We can do this for all unselected points from 1 to 2n, which will lead to the optimal configuration.

My Submission

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the wrong answer for the submission?submission

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

however you choose 3 chords that connect 3 disjoint pairs of points, no point strictly inside the circle belongs to all 3 chords. what does this means?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That means if you choose any 3 chords, they won't intersect in a single point (like this: "Ж")

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

      even if they intersect at a single point, i think the number of intersection remains the same

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Especially problem D was great.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me the $$$O(3^{n/2})$$$ meet-in-middle solution for D?

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

    we want to check if there is some mask with sum == 0, we can split the array in two and for every mask in the first half with sum = x, we check if we can make sum = -x with the second half. of course if we can make sum = 0 using the first half only or the second half only we are done. you can check my code 124122316

»
7 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

You have nice problem ideas. You have good English skills. You are devoted to the thing you do. Although I just do the virtual contest (and solved only A), I can say: "Nice problemset!" Thank you very much, sir!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does the anti-random case look like on problem G?

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

    Here is how to construct an anti-random case.

    Choose "reasonably" the first $$$k-1$$$ sets $$$S_1, S_2, \dots, S_{k-1}$$$ (reasonably $$$=$$$ each element belongs to at least one such set, they are not sufficient to sort); then execute the solution for this family. You will get a family of $$$(k-1)$$$-achievable functions.

    As in problem A of the contest, for each of them you identify the minimal subsequence that needs to be sorted and you compute the union of these sets. This yields a set $$$Z$$$. Notice that for the family $$$S_1,S_2,\dots, S_{k-1}, Z$$$ the answer would be ACCEPTED.

    Now, you remove from $$$Z$$$ the element $$$z\in Z$$$ which minimizes the number of $$$(k-1)$$$-achievable functions whose "minimal subsequence that needs to be sorted" contains $$$z$$$. Notice that for the family $$$S_1,S_2,\dots, S_{k-1},Z\setminus{z}$$$ the answer would be REJECTED.

    Now you execute your favourite random solution (the most efficient one seems to be the one which simply tries random permutations). If, after $$$2$$$ seconds of computation it cannot find any permutation which is not sorted by $$$S_1,S_2,\dots, S_{k-1},Z\setminus{z}$$$ then you have found your anti-random case. Otherwise, you start again.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the Task I a recurrence of 243E - Matrix? What a shame.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

The solution to I contains a bug.

Observe that the set $$$I$$$ is nonempty. Let us consider various cases:

This doesn't necessarily hold. For example, if $$$(Z_1, \ldots, Z_3) = (\{1\}, \{2\}, \{3\})$$$ and $$$S = \{1, 3\}$$$, we have $$$I = \emptyset$$$.

This is not a critical one though. One can easily extend the solution's idea to the case of $$$I = \emptyset$$$ (and it's done in my submission: https://codeforces.cc/contest/1552/submission/124438016)

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

    Thank you for spotting the mistake in the editorial. Fixed.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

My solution for H isn't based on any proof, only on the expectation that a lot of queried sets will give different answers for different shapes. I don't believe there's a single test where this doesn't hold.

Naturally, I start with finding $$$ab$$$, where $$$a$$$ and $$$b$$$ are the number of rows and number of columns of points belonging to the rectangle (why bother with writing $$$+1$$$). I find all candidate pairs $$$(a,b)$$$; quick testing shows there's at most $$$26$$$ of them, so we only need each query to select up to 1/3 of current candidates to succeed.

Let's pick a set where possible answers for each $$$(a,b)$$$ are simple to find. I go for some integers $$$d_a$$$ and $$$d_b$$$ and points $$$(x,y)$$$ where $$$d_a | x-1$$$ or $$$d_b | y-1$$$: rows with spacing $$$d_a$$$ and columns with spacing $$$d_b$$$. A rectangle with $$$(a,b)$$$ will cover $$$\left\lfloor \frac{a}{d_a} \right\rfloor \le k \le \left\lceil \frac{a}{d_a} \right\rceil$$$ of the selected rows and $$$\left\lfloor \frac{b}{d_b} \right\rfloor \le l \le \left\lceil \frac{b}{d_b} \right\rceil$$$ of the selected columns. That's up to $$$4$$$ answers, each is $$$bk+al-kl$$$.

For each query, I try all possible $$$d_a$$$ and $$$d_b$$$, since there are just $$$40,000$$$ of them. For each of them, I find all possible answers for each remaining candidate $$$(a,b)$$$, then find the answer that corresponds to the largest number of candidates. I pick $$$(d_a,d_b)$$$ which minimises this maximum, ensuring that the number of candidates remaining after the query is small even in the worst case. I ask the query and filter candidates that can give the answer returned by the judge. It works!

»
6 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Very nice problems!

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

In problem B can anyone give me test case where we have more than one potential candidate as winner?