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

Автор cip999, 3 года назад, По-английски

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.

Разбор задач Codeforces Global Round 15
  • Проголосовать: нравится
  • +533
  • Проголосовать: не нравится

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

Great problems, but too hard for me :,(

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

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

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

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

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

Great Problems.

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

Tooooooooooooooooooo.. Hard. Yet, very interesting.

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

.

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

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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

      Thanks Man

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

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

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

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

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

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

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

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

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

    Edit-> defnotmee already answered it above, Thank you

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

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

    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 года назад, # |
Rev. 2   Проголосовать: нравится +64 Проголосовать: не нравится

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

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

    Great approach but how it works

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

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

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

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

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

            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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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

      Thanku

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

      Thanks!

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

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

      Can you explain this line?

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

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

      Thanks!

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

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

      Thanks it helped me a lot

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

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

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

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

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

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

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

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

I did problem B using a comparator function 123741857

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

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

      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 года назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

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

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 года назад, # |
Rev. 6   Проголосовать: нравится +9 Проголосовать: не нравится

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

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

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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

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

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 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

    Can you explain how does this works?

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

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

      What do you mean by non-intersecting?

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

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

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

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

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

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

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

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

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

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

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

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

Thank you for the contest!

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

bad pretest for B:,(

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

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

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

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.com/contest/1552/submission/123730552

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

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

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

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

The problem C is very very difficult.

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

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

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

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

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

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

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

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

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

Anyone else try doing B with bitmasks?

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

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

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

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

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

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

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

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

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

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

What are your thoughts?

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

tourist is Lionel Messi of cp. GOAT.

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

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

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

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

nu cuoi da tat vi mim qua dak

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

Best Editorial I have seen ever, thanks

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

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 года назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

O(N log N) solution for problem C:

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

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

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

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

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

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

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

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

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

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

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

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

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 года назад, # |
Rev. 3   Проголосовать: нравится +33 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

      Thank you!

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

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

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

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

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

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

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

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

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

Especially problem D was great.

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

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

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

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

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

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

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

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

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

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

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.com/contest/1552/submission/124438016)

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

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 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

Very nice problems!

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

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.

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

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

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

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.

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

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