cip999's blog

By cip999, 3 years 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

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

Great problems, but too hard for me :,(

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

    Sad round for me, too. ToT

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

    same here, the ideas behind each problem are brilliant, but.... (I can only solve A :'( )

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

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

  • »
    »
    3 years 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"

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

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

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

Great Problems.

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

Tooooooooooooooooooo.. Hard. Yet, very interesting.

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

.

»
3 years 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

  • »
    »
    3 years 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

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

      Thanks Man

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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.

        • »
          »
          »
          »
          »
          3 years 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???

          • »
            »
            »
            »
            »
            »
            3 years 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...

            • »
              »
              »
              »
              »
              »
              »
              3 years 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"; }
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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
                
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit-> defnotmee already answered it above, Thank you

    • »
      »
      »
      3 years 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) ?

»
3 years 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. :)

  • »
    »
    3 years 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)$$$.

»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Great approach but how it works

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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.

        • »
          »
          »
          »
          »
          3 years 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.

          • »
            »
            »
            »
            »
            »
            3 years 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

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

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

  • »
    »
    3 years 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.

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

      Thanku

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

      Thanks!

    • »
      »
      »
      3 years 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?

      • »
        »
        »
        »
        3 years 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.

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

      Thanks!

    • »
      »
      »
      3 years 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

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

      Thanks it helped me a lot

  • »
    »
    3 years 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.

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

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

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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

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

      can u elaborate more??

»
3 years 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.)

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

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

I did problem B using a comparator function 123741857

  • »
    »
    3 years 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?

    • »
      »
      »
      3 years 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.

»
3 years 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

»
3 years 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?

»
3 years 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

»
3 years 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).

»
3 years 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)$$$?

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

»
3 years 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.

»
3 years 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

  • »
    »
    3 years 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

»
3 years 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?

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

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

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

»
3 years 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
»
3 years 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.

»
3 years 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.

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

    Can you explain how does this works?

  • »
    »
    3 years 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?

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

      What do you mean by non-intersecting?

      • »
        »
        »
        »
        3 years 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.

        • »
          »
          »
          »
          »
          3 years 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

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

            Thanks ! Learnt a new thing!

»
3 years 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/

»
3 years 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

  • »
    »
    3 years 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).

»
3 years 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

»
3 years 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!

»
3 years 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 :)

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

Thank you for the contest!

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

bad pretest for B:,(

»
3 years 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 :)

»
3 years 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.net/contest/1552/submission/123730552

  • »
    »
    3 years 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.

»
3 years 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

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

The problem C is very very difficult.

»
3 years 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?

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

»
3 years 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.

  • »
    »
    3 years 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

  • »
    »
    3 years 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.

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

Anyone else try doing B with bitmasks?

»
3 years 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

  • »
    »
    3 years 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 !

    • »
      »
      »
      3 years 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??

      • »
        »
        »
        »
        3 years 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

»
3 years 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?

»
3 years 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.net/contest/1552/submission/123742601
Complexity: O(n*logn)

What are your thoughts?

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

tourist is Lionel Messi of cp. GOAT.

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

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

  • »
    »
    3 years 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.

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

nu cuoi da tat vi mim qua dak

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

Best Editorial I have seen ever, thanks

»
3 years 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 ?

»
3 years 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
»
3 years 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.net/contest/1552/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=G
https://i.ibb.co/YPDkbV9/hacks-1.png

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

»
3 years 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?

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

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

    • »
      »
      »
      3 years 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?

      • »
        »
        »
        »
        3 years 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...

»
3 years 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.

»
3 years 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.

»
3 years 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?

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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]$$$.

      • »
        »
        »
        »
        3 years 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

        • »
          »
          »
          »
          »
          3 years 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.

    • »
      »
      »
      3 years 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!

  • »
    »
    3 years 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.

»
3 years 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?

»
3 years 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?

  • »
    »
    3 years 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: "Ж")

    • »
      »
      »
      3 years 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

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

Especially problem D was great.

»
3 years 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?

  • »
    »
    3 years 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

»
3 years 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!

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

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

  • »
    »
    3 years 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.

»
3 years 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.

»
3 years 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.net/contest/1552/submission/124438016)

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

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

»
3 years 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!

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

Very nice problems!

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

Another way to think of it is to find two disjoint subsets with the same sum, which has complexity $$$ O(n*2^{2n}) $$$ or $$$ O(n*4^n) $$$ and passes in the time.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain what this method is and why it is working on traversing all 3^n states?

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

Best editorial i had ever seen on codeforces. All soutions are explained very clearly and efficiently. UPVOTED.... I wish every editorial on cf would be like this.

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

Can someone explain the solution to my problem E? I just greedily choose the interval with the leftmost right endpoint (an interval refers to two adjacent points with the same color), and then choose it n/(k-1) times. Once a color is chosen, it is not chosen again. It's weird that I passed the problem.211917556

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

Graph solution to D is over complicated.

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

How to solve the bonus for C?