vaaven's blog

Codeforces Round #852 (Div.2, based on Moscow Olympiad for Young Students, rated)
By vaaven, history, 21 month(s) ago, translation, In English

Hi everybody,

This Sunday there will be a Moscow Olympiad for Young Students. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829).

The round will be held at Feb/12/2023 11:35 (Moscow time) and will last for 2 hours. Note the unusual time of the round. The round will be held according to the Codeforces rules and will be rated.

Problems of this competition were prepared by Tikhon228, TheEvilBird, Ormlis, vaaven, Gornak40, Honey_Badger guided by vaaven, grphil and Helen Andreeva.

Thanks to Artyom123 for the round coordination, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Thanks to BucketPotato, KseniaShk, NemanjaSo2005, MagentaCobra, kuertov, prvocislo, 4qqqq, vsinitsynav, FynjyBath, qualdoom, ivanlarin, didedoshka, petyb, PBBx0, Mikhango, charlyk, RP-1, talant, ak2006 for testing.

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

Good luck everybody!

UPD: Score distribution: 500 — 1000 — 1250 — 1750 — 2500 — 3250

UPD2: Еditorial

  • Vote: I like it
  • -493
  • Vote: I do not like it

Comments Comments (155)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +52 Vote: I do not like it

The round will be held according to the Codeforces rules and will be rated for both divisions. Shouldn't it be rated for Division 2 only?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

As a tester I can say that I am a tester (again). Don't hurt me, I hope this time everything will be fine.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +116 Vote: I do not like it

o.O

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, I enjoyed the problem set.

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

    What will be the distribution of points?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Sorry, saw your message late. It is not testers who decide that. As you can probably see, the author made an update to the blog, the distribution is: 500 — 1000 — 1250 — 1750 — 2500 — 3250

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

        Aiming for first 3 problems then!

        Let's see how it goes :)

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          I just could not figure out what was wrong with problem A.

          This was my solution:


          #include <bits/stdc++.h>
#define ll long long
using namespace std;

void solution() {
  ll a = 0, b = 0, n = 0, m = 0, result = 0;

  cin >> a >> b;
  cin >> n >> m;

  ll promotions_available = (n * m / (m + 1));

  if ((promotions_available + promotions_available / m) * b >
      (promotions_available * a)) {
    result += promotions_available * a;
    n -= (promotions_available + promotions_available / m);
  }
  // Buy the rest from the cheapest without the promotion
  if (n > 0) {
    result += min(a, b) * n;
  }

  cout << result << "\n";
}

int32_t main() {
  int t;
  cin >> t;
  while (t--)
    solution();
}
          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            ll promotions_available = (n * m / (m + 1)); should be ll promotions_available = (n / (m + 1)) * m;

            → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            I found some errant cases for you.

            TL; DR -> a = 6, b = 5, n = 9, m = 4, expected output = 44; your output = 45

            You can use the following code for the same.

            Testcase Generator
            AC Code (you can use any other as well)
            Debugging Procedure
            → Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

As a tester I can say that problems are very interesting. Have a good luck on this round:D

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

Note the unusual time i.e. 6hrs before general time.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

is score distribution going to be announced before the contest?

also can it be delayed ? it clashes with Innopolis finals time

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It can't be delayed since it has to be held during Moscow Olympiad for Young Students.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Fingers Crossed for +delta (◠‿◠)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    Don't cross your fingers, it will be difficult for you to type during contest. (◠‿◠)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

I will solve this olympiad. Good luck to everyone at the round and the olympics!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

Friendly time for Vietnamese like me

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

eagerly waiting for a rated contest . Good luck everyone !!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

is this china mathforces round or am i safe?

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

I am looking forward to the problems of this contest, hoping to surprise me.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope we can enjoy ourselves in this contest.Make it Sunday, February 12, 2023 at 16:35(UTC+8)

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

This is at midnight for me. Hopefully I don't brick it :/

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

I have classes T_T... But still good luck awa

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

Hoping to have a great round with great learnings!

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

hope the best for all and to get my cyan color today :)

Edited okay I think I will wait for my cyan for another day :D

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

Good luck everybody, hope problems will be interesting!

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

Is the other contest still ongoing?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -14 Vote: I do not like it

Such a permutationforces.

→ Reply
»
21 month(s) ago, # |
← Rev. 7   Vote: I like it +30 Vote: I do not like it

The problem F is the same as 765F.
My code was copied from https://www.luogu.com.cn/problem/solution/CF765F.

Edit: Please don't upvote this comment.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I don't understand why you upvote this. Firstly,if you notice that a problem is similar with another one in the past,keep it for yourself and don't spoil the contest. Second of all,saying that you copied your code from a solution source is against the values imposed by codeforces(ig).

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

A funnily embarassing contest for me -- A >> B > C for me. I solved the problems in the order C, B, A and got 5 WA on A before getting it. My math solution had a bug I couldn't find, so I tried to binary search the amount potatoes to buy for 'a' coins, which obviously didn't work. Then I thought the function was unimodal, so I tried ternary search on the potatoes, which still didn't work! Finally, I decided to scrap my mess of a code and prove a solution on paper and then implement it. It was less stressful after the 4th WA anyways, since I already hit the maximum penalty for a problem... Finally I solved Problem A, 76 minutes into the contest! I am proud of my persistence and disgusted at my stupidity.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I used binary search for A and it worked. Have no idea how to solve it normally though...

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

      I did the case work on paper: let mx be the most multiples of (m+1) that we can buy without overbuying. Then the answer is the minimum of {n*b, (mx+1)*(a*m), (a*m*mx)+(n-(m+1)*mx)). I wish my binary search solution worked so I could have solved it earlier.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

OMG, B is so hard, can anyone explain the solution problem B for me :((

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I didn't prove it, but I solved it in a few minutes by greedily going max_sum, max_sum-1, max_sum-2... min_sum, min_sum+1, min_sum+2.. max_sum-1. I was surprised it worked.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you so much. The sad contest, I can't solve B.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Same. I'm beginning to question my ability to make observations :(

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

    Note the length of the array is always (x-y)*2 .

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

      I couldn't figure that out, I just had a counter and incremented it by 1 every time I outputted a number lol

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    n = (x — y) * 2. That's because local minimum and local maximum are alternating(x1, y1, x2, y2, x3, y3, ...(that's quite easy to prove)) which means that the quantities of minimums and maximums are equal(that's unimportant to the solution, it's just an interesting fact). So with this information we can easily count n. Lets look at slice [x1...y1..x2). We can easily count the quantity of all elements in the slice [x1...y1...x2): n = x1 — y1 + x2 — y1. Then add n to answer and do such thing till you return to your first slice. We can see that the final result will be ans = 2 * x1 + 2 * x2 + ... + 2 * xm — 2 * y1 — 2 * y2 — ... — 2 * ym = 2 * (x1 + .. xm — y1 — ... — ym) = 2 * (x — y). Finally, we can easily create an appropriate array with only 1 maximum and minimum which are equal x and y.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +42 Vote: I do not like it

How to solve F?

I tried Mo's algorithm, but it won't pass the time-limit. Any nice optimization required in Mo's algo?

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

    Idk if it will pass or not but anyways you should try this optimization: Optimization with Hilbert curve

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    • I've tried F with Mo's algo + multisets, TLE4
    • My multiset solution had high constant factor(10 operations per index) so I decided to come up with a segtree solution(2 calls to update per index) but it still TLEs.
    • I tried with some different block sizes too like N/logN, N/sqrt(q) etc.
    • Also added that zig zag sort. They all TLE lol.
    • Hilbert curve optimization works better with small q, so it's not going to change anything
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Bricked B and then couldn't submit D in time.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Seems that last problem is very popular.

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

the n = 2 case in B is very stupid

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

    agreed i am surprised that the answer for the case when x — y = 1 is just an array of {x , y} :((

    statement so unclear and stupid

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +30 Vote: I do not like it

Make it unrated, unless you play too much genshin.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -26 Vote: I do not like it

Best contest I have ever seen!..

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

what even is pretest 6 for problem D? i tried to use segment tree type of answer and i still don't know the corner case (that or i somehow fluked the 4th and 5th pretest lol). Also tricky problem A ;)

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

    I mistyped min to max when initializing prefix min of positions. However it also squeezed into the first 5 pretests:(

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Segment Tree seems pretty overkill for D. My strategy was to count the #of subsegments such that they share a common MEX by iterating over the MEX value and using 2 pointers to handle everything. I got it to pass the example cases too. Wish I could have submitted it :(

    Edit: It got accepted. Here's the code if anyone's curious: 193333734

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

    One tip is to write a brute force solution for D and compare your submission with the brute force solution.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    Solution
    Code

    note that i used my template here and used cpbooster to parse and submit the code so there are a lot of unnecessary lines. you can assume that solution starts from void solve()

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

    did u find what is pretest 6? mine is also failing

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

How to do F ? I tried using Mo's algo with sets, but that doesn't feel to squeeze in the TL

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

is it sure that F isn't https://mirror.codeforces.com/problemset/problem/765/F?

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

yayy I was able to attempt D this time.. hoping system test pass

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

My solution to $$$C$$$.

For every element $$$l$$$ as left position, there is minimal $$$k$$$, such that it is required to $$$r \ge k$$$ for $$$l$$$ not to be minimum or maximum. Find all these $$$k$$$ in linear time using stack (note, there can be no such $$$k$$$). Let it be $$$left[i]$$$. Then do the same in other direction: $$$right[i]$$$ is rightmost position, at which $$$i$$$ is neither max nor min.

Now we have to find $$$l$$$ and $$$r$$$ such that $$$l \le right[r]$$$ and $$$r \ge left[l]$$$. Fix $$$l$$$. We have to check, if there is $$$r \ge left[l]$$$, such that $$$right[r] \ge l$$$. We can do this using segment tree for maximum and position of maximum.

Whose solution is longer?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I used two pointers -- while(l < r && flag), flag = false, if a[l] or a[r] = min or max, increment l or decrement r, increment min or decrement max, and set flag to true. Then output l and r as the answer,

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I did the exact same thing, even the same variable names.

    But it feels like there is a better sol

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

    I have also overkilled! same idea and used 3 sparse table :)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Why is C easier than A and B?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

Problem E is just beautiful!

Solution sketch:

First sort array $$$a$$$. Henceforth I assume $$$a$$$ is sorted.

We can prove by greedy exchange that the set of satisfied people form a prefix of $$$a$$$. Now, let's fix the prefix of satisfied people.

Let's maximize the number of distinct books that this fixed set of satisfied people can be assigned such that all have to be read by at-least one person

We can prove again, that:

  1. if the set of satisfied people lie in more than $$$1$$$ group, then it is never more optimal to take any unsatisfied person in a group of satisfied people
  2. otherwise the set of satisfied people lie in a single group, and the answer (maximum number of distinct books that can be assigned such that all are read) is trivial to compute.

So for each prefix, we have found the maximum number of distinct books. But the number of books that can be assigned to a prefix is monotonic: if you can assign $$$k$$$ books, you can also assign $$$k-1$$$ books. So if answer for a prefix of size $$$j$$$ is $$$k$$$, update answer for each $$$i<=k$$$ with $$$j$$$. This can be done trivially by maintaining suffix maximums.

193328416

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

brought a permutation p of length n to the zoo This sentence lol!

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

What will happen if you try to hack someone's solution with this test x = 1e9 ,y = -1e9 in problem B ?

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

    solution exist only for n<1e5 (given) so above case will not have any solution

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Yes, absolutely. I think they should have written that the sum of the differences between x and y would not exceed 1e5

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

    First line of the question For his birthday recently Fedya was given an array a of n integers arranged in a circle

    Last line of the question It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Im extremely sad. I just solved question D 5 minutes after contest ended. And the even sadder part is that I joined the contest 30 mins late :((. You can tell because I only solved first question after 35 mins. And solved the next two questions almost immediately.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem C just feels lot easier than Problem B.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

bad problem F

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Difficulty order according to me: B>A>D>C

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I would swap A and D around, but I agree with this lol. Wasted a ridiculous amount of time on B

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

    what was your idea for D that you put is so low on difficulty?

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    my submission

    basic idea is with 3 conditions

    price on first day is a and price on second day is b

    then

    if (a < b) ... you should alway buy on first day

    if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day

    else buy everything on second day

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +68 Vote: I do not like it

Why is problem B such a troll? It says that $$$-10^9 < y < x < 10^9$$$ and the answer has length $$$2 \cdot(x-y)$$$. In my opinion, you should not put this kind of "traps" in Div2 problems, especially in A and B.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    First line of the question For his birthday recently Fedya was given an array a of n integers arranged in a circle

    Last line of the question It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      This is a wrong use of the phrase it is guaranteed.

      See this

      Meaning 2: Make it clear that this ‘guarantee’ is an additional constraint on the input.

      • Input is only allowed if X.
      • In the example above: “Only input for which some C exists is legal input.”
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        oh, thanks for sharing this. Something for me to think about

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

    Exactly , I was wondering how would i even print such a huge sequence even if i get one :/

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Exactly, It had took my lot of time for optimizing number of operations, and I checked constraints on x and y more than 5 times, Also problem statement of A is not well written, it could be written in 2-3 lines. Even F is taken according to me.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Agreed, perhaps the worst Div. 2 B of all time, or at least in recent memory.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I totally agree with this, just this line alone $$$-10^{9} \le y < x \le 10^{9}$$$ can mislead people to think that $$$x = 10^{9}$$$ and $$$y = 10^{-9}$$$ is a valid input, even though the next line says that the sum of $$$n \le 2 * 10^{-5}$$$

    And as such leaving their head scratching that there is a better answer than $$$2*(x-y)$$$ for $$$x = 10^{9}$$$ and $$$y = 10^{-9}$$$ that can fit into the given constraint on $$$n$$$, which can possibly cause them to get stuck forever

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

The problem A is just way too annoying!!

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

A: Divide n potatoes into floor(n/(m+1)) groups and n%(m+1) single potatoes. The price for a group is min(m*a, (m+1)*b), and for a single potato is min(a,b).

B: Go down from x to y by step -1, then go up from y to x by step +1.

C: Recursion. First, check if [1,n] is a good segment. If not, then a[1] or a[n] will be the max or min value on this segment. If a[1]=1 or a[1]=n, then we need to solve recursively on [2,n], otherwise we solve on [1,n-1]. We do this recursively until we find an answer, or the length of the current segment is <4. Also we need to maintain the max and min value on the current segment.

D: Consider for each possible MEX in [1,n+1]. For MEX=1, we need to find the position of 1 in p and q, and count the number of segments which doesn't contain these positions (which is a subsegment of 3 segments splited by positions of 1), and for MEX=n+1 it's trivial (only [1,n] will have MEX=n+1). For MEX in [2,n], we need to find the minimal segment containing numbers in [1,MEX-1] in both p and q (this segment can be updated by expanding previous segment to contain MEX-1), and find the positions of MEX, we can expand the minimal segment in both directions until it touch these position (also, if there's any occurrence of MEX in the minimal segment, the contribution of MEX is 0).

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you prove B?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Let the difference between the sum of local maxima and local minima be $$$d$$$, and let $$$n$$$ represent the optimal solution size (note that $$$n$$$ must be even). Assume that $$$d>1$$$ so that $$$n$$$ must be greater than 2.

      Consider a local maxima — it must occur as $$$\ldots,x,x+1,x,x\pm 1,\ldots$$$ and now, remove the centre two elements, and we have a new sequence $$$\ldots,x,x\pm 1,\ldots$$$ which has $$$d'=d-1$$$, and a solution with $$$n-2$$$ elements, and reduce.

      EDIT: (And a local maxima will always exist)

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

    In A isn't it possible that if we buy x number of the potatoes out of n from a and remaining from b so now we vary this x How can we claim that it is best to divide all n in m+1 groups for a and remaining for b Can't there be any intermediate x out n for which we find the best possible minimum I tried this using binary search but W/A

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

      It's not "divide all n in m+1 groups for a and remaining for b". In fact, there are at least n%(m+1) potatoes we can't buy them by favorable price (so we must buy them by price min(a,b), and we can by at most (m+1)*floor(n/(m+1)) potatoes by favorable price (which is min(a*m/(m+1),b)).

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

        Let c=intmax, l=0,r=n,mid what i am saying is that what if we take i=mid and j=n-mid then we can calculate 'a' for i and 'b' for j

        if this is less than equal to c we do r=mid-1 and else we do l=mid+1

        i have understood that we can give n%(m+1) to min(a,b), but now it is only applicable when we give (n-n/(m+1)) to 'a', so what i am thinking is if we find certain 'mid' which can give a better result by using same distribution formulae?

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

          I can't understand why you think about binary search. But we can consider problem A atart anew:

          --Consider we want to buy only k potatoes where k<m+1, what's the minimal cost? Well, since k<m+1, if we buy them on the 1st day, the price is k*a, on the 2nd day the price is k*b. Therefore, the minimal cost is k*min(a,b).

          --Consider we want to buy only m+1 potatoes, what's the minimal cost? If we buy on the 1st day, we need to pay m*a since the promotion, and on the 2nd day we need to pay (m+1)*b. Therefore, the minimal cost is min(m*a,(m+1)*b).

          --Now consider we want to buy n potatoes, what's the minimal cost? By the previous discussion, we can do 2 kinds of operation:

          1. buy 1 potato, cost min(a,b).

          2. buy m+1 potatoes, cost min(m*a,(m+1)*b).

          Since the 2nd operation includes promotion and 1st does not, it cannot be worse than the 1st operation when there're >= m+1 potatoes we need. So we can do 2nd operation repeatly until we can't do more operations (which means, there're <=m potatoes we need to buy). Then we need to use 1st operation for remaining potatoes.

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

That B problem T_T

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

Is anyone able to tell me why in problem B, in the first test case where the local maximum = 3 and the local minimum = -2 the solution cant be just the numbers 3 and -2?

It doesn't seem to break any of the requirements? Am i missing something?

My submission to problem B

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

    Am i missing something? : Yes

    consecutive numbers should have a difference of 1 :)

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

      The problem says absolute difference and the numbers 3 and -2 seem to have an absolute difference of 1 right?

      Or is it that abs(3-(-2)) = abs(3 + 2) = 5 ?

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

        Absolute difference doesn't mean the difference between the absolute values of the numbers.

        It is the absolute value of the difference

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

        it's the latter one sadly

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone show testcase 6 in D?

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

OMG,D is so hard,can anyone explain the solution of problem D for me :(

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

    FOR（MEX，1，n+1） { Find Range of L in this MEX Find Range of R in this MEX answer += len of Range_L * len of Range_R } you can solve MEX=i by MEX=i-1

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

The fact that there are people who failed to solve D, but were able to solve F in under 30 minutes :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

Why is this getting downvoted, the round was pretty nice?

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

    Cause F problem was present in previous contests. Most probably round gonna get unrated

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

      This round will not get unrated, Mike did a very good blog post as to why it won't get unrated.

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

I managed to solve A-D and I have to say I quite liked all the problems. Sadly, I did not look at E.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Problem B give me [-1e9;1e9] and so I say: Nani? How I can minus one with range 1e9 LOL? Finally, I solved it by subtracting the value by 1 and it worked XD! Sorry for my english !

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

I spent nearly an hour on problem F but now it coincided with another problem in the old round. I don't have time to solve D and E. /kk

→ Reply
»
21 month(s) ago, # |
← Rev. 5   Vote: I like it +5 Vote: I do not like it

you can check the video editorial for

problem C: https://www.youtube.com/watch?v=39LiI3MKack

problem D: https://www.youtube.com/watch?v=H-7tJaW7crI

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -11 Vote: I do not like it

Even without considering that the problem F has appeared in the past round, I think the problems in this round is simpler than usual.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I spent almost 40 mins for solving the problem B for the given constraints. Finally left the contest. One of the worst contests in recent times.

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

two-pointer forces :).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

The objective of the last problem is fairly simple, (not the solution, just the objective), so it makes sense that a similar problem has already been proposed before.
Imo, this coincidence wasn't the only issue with this round, Speedforces rounds are becoming increasingly common these days; though it was indicated beforehand by the problem ratings, still this isn't ideal.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

When will the submissions and testcases open?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

When can we see the source codes of others? I'm DESPERATE to see where did I get wrong

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

    In the standings page you can double-click on their scores

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

      I don't think that this one is open yet.

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

How to solve A? I have tried deperately in contest math, binary search but everytime something got wronged

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

    my submission

    basic idea is with 3 conditions

    price on first day is a and price on second day is b

    then

    if (a < b) ... you should alway buy on first day

    if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day

    else buy everything on second day

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

when will u update editorial please :o

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Is this round Unrated?

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

Approach for D: For MEX 1: we have to find no. of common subarrays which dont include 1. So lets say of the 2 arrays leftmost 1 is at i, and rightmost 1 is at j then all subarrays forming less than index i, in b/n i and j , greater than j will give MEX=1.

Now for MEX=2 : We have to fix the subarray where 1 is present in both so i to j is fixed. Now check how many common subarrays we can form excluding 2. Here 2 can lie in the opposite direction of i,j or at the same direction. If it lies in b/n i,j so MEX=2, doesnt exist. also expand i,j which will include 2 for next MEX calc

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

In my opinion, C is easier than B.

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

unfair contest

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it

In problem B, the statement "It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2⋅10^5$$$" is misleading since it made me believe that for all possible inputs $$$x$$$ and $$$y$$$ $$$(−10^9≤y<x≤10^9)$$$ the answer will never exceed $$$2⋅10^5$$$ which is obviously not true for $$$x=10^9$$$ and $$$y=-10^9$$$ since the minimal length is $$$2x-2y$$$. This lead me to believe that the expected solution was not optimal enough and that the problem had to be solved with some optimal value that minimized the length in order to not exceed $$$2⋅10^5$$$ by spamming something like $$$\sqrt{x}$$$ and $$$\sqrt{y}$$$ or using binary search.

It would've been much better to either:

  1. Rewrite the statement as "It is guaranteed that the sum of $$$x-y$$$ over all test cases does not exceed $$$10^5$$$".

  2. Lower the constraints to $$$(−10^5≤y<x≤10^5)$$$ (same problem, same solution).

  3. Ask the solver to output -1 if the minimum length exceeds $$$2⋅10^5$$$.

  4. Rewrite the statement and make it clear that you will not actually receive all possible inputs $$$x$$$ and $$$y$$$ $$$(−10^9≤y<x≤10^9)$$$, but rather all possible inputs $$$x$$$ and $$$y$$$ $$$(−10^9≤y<x≤10^9)$$$ such that the minimum length of the optimal solution does not exceed $$$2⋅10^5$$$.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

For me this is an inspiring contest with excellent B&E.

And F itself is just a good problem at the wrong time.

None of you done it on purpose,that's enough.I hope that it will not destroy your confidence and courage.

→ Reply