crazyilian's blog

By crazyilian, 4 years ago, translation, In English

This is our first contest for the three of us (Alexdat2000, crazyilian, sevlll777), so we would like to share our impressions of creating this contest. Check it if you want to!

ROUND LOG

And, of course, here's the tutorial of the round.

1358A - Park Lighting
Idea: Alexdat2000

Picture
Tutorial
Solution

1358B - Maria Breaks the Self-isolation
Idea: crazyilian

Picture
Tutorial
Solution

1358C - Celex Update
Idea: crazyilian

Picture
Tutorial
Solution

1358D - The Best Vacation
Idea: sevlll777

Picture
Tutorial
Solution

1358E - Are You Fired?
Idea: sevlll777 и crazyilian

Picture
Tutorial
Solution

1358F - Tasty Cookie
Idea: sevlll777 и crazyilian

Picture
Tutorial
Solution by Alexdat2000
Solution by Alivk06 (much shorter)

Thank you, everyone, for participating in the round! We hope you've raised your rating! And if you haven't, don't be sad, you'll do it!

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

| Write comment?
»
4 years ago, # |
Rev. 4   Vote: I like it +129 Vote: I do not like it
Разбор на русском / Russian tutorial

Another solution to E which seems simpler to me.

Let's call the value of all elements in the second half of the array $$$x$$$.

Let $$$s_k(i) = a_i + a_{i+1} + \ldots + a_{i+k-1}$$$ — the reported incomes.

Pretend there exists such a $$$k$$$ that $$$k\le\tfrac{n}{2}$$$. Consider the following reported incomes: $$$s_k(i)$$$ и $$$s_k(i+k)$$$. Notice that if we double $$$k$$$, the $$$i$$$-th reported income will be equal to $$$s_{2k}(i) = s_k(i)+s_k(i+k)$$$. $$$s_k(i)>0$$$ and $$$s_k(i+k)>0$$$ imply $$$s_{2k}(i)>0$$$. It means that after doubling $$$k$$$, the new value will still be correct. So let's search for such $$$k$$$ that $$$k > \frac{n}{2}$$$.

As $$$k > \frac{n}{2}$$$, then $$$i + k > \frac{n}{2}$$$ holds for all $$$i$$$. It means that all numbers to the right of $$$[i,\ \ldots,\ i + k - 1]$$$ are equal to $$$x$$$.

Notice that if $$$x \ge 0$$$ and some $$$k$$$ is correct, then $$$k + 1$$$ is correct as well, because $$$s_{k+1}(i) = s_{k}(i) + x \ge s_k > 0$$$. So if $$$x \ge 0$$$, it's enough to check $$$k = n$$$.

If $$$x < 0$$$, we do the following. For all $$$i$$$ we find such numbers $$$p$$$ that $$$s_p(i) > 0$$$. Notice that if $$$s_p(i) > 0$$$, then $$$s_{p-1}(i) = s_p(i) + (-x) > s_p(i) > 0$$$. It means that if $$$p$$$ works, then $$$p-1$$$ works as well, so, actually $$$p$$$ can be any number from $$$1$$$ to some limit $$$t[i]$$$. It's easy to find $$$t[i]$$$ using prefix sums array and binary search in $$$\mathcal{O}(\log n)$$$, or use a formula (increasing $$$p$$$ by $$$1$$$ decreases the sum by $$$-x$$$) in $$$\mathcal{O}(1)$$$. If $$$s_p(i)$$$ doesn't hold for any $$$p$$$, assume $$$t[i] = 0$$$.

Finally, notice that $$$k$$$ is a correct answer if and only if $$$s_k(i) > 0$$$ holds for all $$$i$$$ from $$$0$$$ to $$$n-k$$$, or, using the precalculated array, $$$k \le t[i]$$$ for all $$$i$$$ from $$$0$$$ to $$$n-k$$$. It means we can just loop through $$$k$$$ from $$$n$$$ to zero and check if $$$k \le \min t[0,\ \ldots,\ n-k]$$$, maintining the current minimum. If the inequality holds, we output $$$k$$$ as an answer. If it doesn't hold for any $$$k$$$, we output $$$-1$$$.

The overall complexity is $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n)$$$, depending on $$$t[i]$$$ calculation implementation.

C++
Python
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    This is really cool. I tried establishing connections between k and k+1, never thought there would exist something between k and 2k.

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

    Problem D Video editorial. Link

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    For E why we cann't do k = n and check sum is positive or not? If positive then print k else -1

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

    Another explanation for E:

    Case 1: If total of all N elements is greater than 0, report N.

    Case 2: If X >= 0, report -1. Because assume for the sake of contradiction some K works. Cover N with non-overlapping windows of size K until there are only X's remaining. Since each of these windows have positive sum and the uncovered X's are all >= 0, the total is greater than 0, which is a contradiction (since we would've returned in case 1 already)

    Case 3: If X < 0, then K must be greater than N / 2 or else it will have a window of all X which are negative. This means the window must start in the front half and end in the second half. This leads to some easy formulas.

    For some K, for all 0 <= i <= N - K, the following are equivalent:


    0 < prefix[i + K] - prefix[i] // Formula for sum of a window starting at i prefix[i] < prefix[i + K] // Rearrange prefix[i] < prefix[N] - X * (N - K - i) // Because tail end are Xs prefix[i] + X * (N - i) < prefix[N] + X * K // Rearrange

    So track all the LHS you've seen so far for [0, i] and if the max is less than prefix[N] + X * (N - i), you can return N - i as your K.

    Python code: https://mirror.codeforces.com/contest/1358/submission/81555323

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

      Why return N-i? Can you explain more detailedly?

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

      Thanks I suddenly understand it !

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

      Thanks for this explanation. I found it to be more practically reachable during a contest. Here's my C++ code: 81596230

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

      Excellent solution!

      Пока пытался разобраться, понял для себя более четкое объяснение:

      1) С X >= 0 Выше уже было сказано много и все понятно.

      2) Если X < 0, то будем искать K > N / 2(Очевидно, что K не может быть меньше, т.к. X < 0).

      3) Начнем перебирать различные K, начиная с N. Тогда на первом шаге минимальная сумма на отрезке длинной K — это сумма всех элементов. Научимся за O(1), находить наименьшую сумму на отрезке длиной на 1 меньше. Возможны следующие варианты:

      1. Минимум находится на новом отрезке, который заканчивается в позиции N — 1, т.е. на отрезке [N — K..N — 1], сумму на таких отрезках мы может быстро определять, заранее посчитав суффиксные суммы: suf[N — K].

      2. Минимум находится на отрезке, который получается, если от отрезка с минимальной суммой для предыдущего K(который был на 1 больше) отрезать самый правый элемент(Отрезать левый элемент нет смысла, т.к. сумма гарантированно будет больше, чем при отсечении самого правого элемента. Доказательство достаточно тривиально.). Заметим, что, поскольку K > N / 2, то отрезанный элемент гарантированно равен X, и новая сумма равна: minSum — x

      Таким образом, как только мы найдем состояние, в котором минимальная сумма для текущего K стала положительной — можно выводить ответ.

      ll minSum = prefix[n - 1];
      for (int i = 1; i < n / 2 + 1; i++){
      	minSum = min(prefix[n - 1] - prefix[i - 1], minSum - x);
      	if (minSum > 0){
      		cout << n - i;
      		return 0;
      	}
      }
      cout << -1;
      
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    for(int i = 0; i < n; i++) { maxlimit[i] = (pref.rend() — upper_bound(pref.rbegin(), pref.rbegin() + (n + 1) / 2, (i == 0 ? 0 : pref[i — 1]))) — i; }

    Hi purplesyringa I am not able to understand this code of yours. Could you please elaborate a bit?

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

      upper_bound is a standard binary search function. However, it works only on increasing arrays, and that's not the case for us because x is negative. There are two solutions to this problem: either reverse the array beforehand or use reverse iterators which make upper_bound think that the array is actually reversed. The first solution is used in the Python implementation, the second one is used in C++.

      So, the following codes are equivalent (I haven't compiled them though so there might be some minor issues):

      for(int i = 0; i < n; i++) {
          maxlimit[i] = (pref.rend() - upper_bound(pref.rbegin(), pref.rbegin() + (n + 1) / 2, (i == 0 ? 0 : pref[i — 1]))) - i;
      }
      
      auto revpref = pref;
      reverse(revpref.begin(), revpref.end());
      for(int i = 0; i < n; i++) {
          maxlimit[i] = n - (upper_bound(revpref.begin(), revpref.begin() + (n + 1) / 2 - 1, (i == 0 ? 0 : pref[i - 1])) - revpref.begin());
      }
      

      Now to the code itself. I want to find such maximum $$$maxlimit[i]$$$ that $$$a[i] + \ldots + a[i + maxlimit[i] - 1] > 0$$$. We can rewrite this as $$$pref[i + maxlimit[i] - 1$$$ > pref[i — 1]$ (assuming $$$pref[-1] = 0$$$). So we just want to find the last position which is greater than some constant, which is equivalent to finding the first position which is greater than some constant in a reversed array, this is exactly what upper_bound does.

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

    How can you say that if p works then p-1 also works because there will an extra element s(p-1)(n-p).. So please can you explain that.

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

      N = 5 A = {100,-1,-1} x = -1

      So array becomes [100 -1 -1 -1 -1]

      p=5 works but p-1=4 does not!!!

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

        Notice that $$$k$$$ is some 'global' value, i.e. it's the same for all segments. But $$$p$$$ is 'local' to $$$i$$$, i.e. segments that start at different indicies may have different length. That's the case in your example: what exactly $$$p$$$ are you talking about? You say that $$$p=5$$$ works, but you didn't mention $$$i$$$, so I can just guess that you actually meant that $$$p=5$$$ works for $$$i=0$$$, i.e. the sum of $$$[100, -1, -1, -1, -1] > 0$$$ which is obviously true. Notice that $$$p=4$$$ works for i=0 too: sum of $$$[100, -1, -1, -1] > 0$$$. However, $$$p=4$$$ doesn't work for $$$i=0$$$.

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

          Thanks for explaining it again.(Really appreciate that you responded to my doubt).

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

    something similar i did too

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

    purplesyringa what does maxLimit signify in your solution?

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

    why dont we directly check for k=(n+1)/2 if x<=0, and k=n for x>0...??
    Correct me if I am wrong.

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

      It's enough to check that $$$k=n$$$ for $$$x>0$$$. But it's not enough to check $$$k=\lceil \frac{n}{2} \rceil$$$ for $$$x \le 0$$$, there's a countertest to this.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        sp−1(i)=sp(i)+(−x)>sp(i)>0. It means that if p works, then p−1 works as well...(if p-1>=⌈n/2⌉). SO if at all if sp(i)>0, and p>⌈n/2⌉, this should also be true for p=⌈n/2⌉. Am I missing something..? Or please provide the counter testcase

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

          Counter Testcase:

          Consider the incomes array: -1 2 2 -1 -1 -1

          Here sum of the array is 0

          For K = 4, sum of each subarray is not >0

          For K = 5, sum of each subarray is >0

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

    I could not understand the part of x<0. and whats t[i]. Can you please elaborate a little?

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

      The simple case of $$$k=n$$$ only works for $$$x \ge 0$$$, so we have to handle $$$x < 0$$$ separately. We do that by calculating how much we can extend a segment starting in $$$i$$$ so that the sum of the segment $$$[i,\ \ldots,\ i + t[i] - 1]$$$ is positive. For example, for the array $$$[1, 2, 3, -2, -2, -2]$$$, $$$x$$$ equals $$$-2$$$, and $$$t$$$ equals $$$[5, 4, 2, 0, 0, 0]$$$.

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

        great explanation..I understood till here ..now how to find ans from t[i]... logic to find ans from t[]..?

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

        I can understand that from i till length t[i] we have positive sum.But this positive sum of length t[i] should be positive for all subarrays of length t[i].. how to check that within time constraints..as there may be many t[i]>0...?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    prefix sum cannot be monotonic, it maybe increasing somewhere, decreasing elsewhere. how can you find maxlimit with prefix sum?

    can you please explain a little bit more? i appreciate in advance

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

Good problems, pathetic memes.

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

Need more memes in upcoming tutorials

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

    For C, as given in the solution diagram, cant he go from 1 -> 3 -> 5 -> 8 -> 13 ?

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

      We are trying to find different sums on way from 1 to 13. So the sum 1+3+5+8+13 has already been covered in 1 -> 2 ->5 ->9 ->13

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

B explanation ?

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

    What exactly don't you understand? I might be able to help.

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

      please can you explain problem D. I know that how every optimal segment ends in some end of month.But i am unable to implement,and can't understand where to use binary search or 2 pointer

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

Very good problems! As a participant, I really enjoyed solving this contest! Especially I liked memes in the problems

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

is it possible to solve C using nCk (binomial coefficient) ?

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

    Do you mean the binomial coefficient?

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

    You would get tle as far as I know because the limits are 1e9

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

      I'm interested in learning the approach (if exists) regardless of the TLE, perhaps pre-calculating or DP can solve the TLE problem.

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

        you can not solve though DP

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

        technically you can solve with dp, because each previous case you add y (or x depending on if you're incrementing row or column), but in the end you can represent all cases with x*y+1

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

          Yeah, I first built the dp matrix and then figured out that each row in this matrix is an Arithmetic Progression, hence the formula x*y+1 comes from there too!

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

    i feel you bro i came up with a formula (n-m+2)!/((n-1)!*(m-1)!) only to get disappointed, although it ran through the test cases in questions.

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

      but I am just thinking that why this formula isn't working here and was fetching a wrong answer in second pretest only. Can someone point out the issue with this formula when we have already taken care of the fact that calculating factorial doesn't leads to overflow.

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

        Yeah about that!! Actually, the formula you calculated was for the total number of paths but in the question, we were asked to count only those paths whose sum's are different, i.e. in simple words we were not expected to count that path sum which we have already included. So, to do that we needed to optimise our solution which the author has achieved by calculating the subsequent path whose sum was increasing by 1 consecutively.

        P.S: It would be better if go through this video tutorial. This guy has explained in a very intuitive way. If still not able to understand ping me personally.

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

          Ok cool let's say I want to move from (1,2) to (4,5), can you give me an example of two different paths but producing the same sum.

»
4 years ago, # |
Rev. 2   Vote: I like it -174 Vote: I do not like it

i'm in love with those pictures

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

Anyone for TLE/WA uphacking on E? :)

81551641

Edit: Idea is — for x > 0 check k = n. For x <= 0 check shortest, longest, and maximum sum subarrays that contain all numbers in second half. If those 3 don't give a result check all possible lengths that have sum greater than any previous sum for intervals ending at n — 1.

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

When you check the shorter solution of F first ..and wonder this is the shorter one

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

$$$O(N)$$$ solution for B (but it's barely within limits): 81499306

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

    You iterate up to 10^5 for every test case regardless the given N for that test case so your solution is technically 10^5*10^4 for a test where every N=1

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

      Yes, I realised. But after locking my solution. I was disgusted because I also came up with the editorial solution but thought this was better and just quickly submitted. The bright side is that it luckily passed and that now I know CF can handle about 5*10^8 operations in one second (although I won't be relying on it much in the future and will try to make better judgements about the solutions I implement). Good luck :)

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

For problem E, one could also eliminate some values of $$$k$$$ by randomly testing some starting points, then naively test each $$$k$$$ not eliminated: https://mirror.codeforces.com/contest/1358/submission/81552953

UPD: congrats to Kaban-5 for uphacking :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    we thought about it and it has some proofs (not strict) that there are no contrtests because second part has same numbers

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

I am still not getting (x2-x1)*(y2-y1) + 1 formula for problem C. like I understand row diff and col diff product gives a number of ways. but why we need + 1 at last. Can anyone explain? thanks in advance :)

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

    The +1 at the end is to ensure the minimum path is included in the answer too.

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

    plz someone explain this..why it is minimum and maximum sum path??

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

      We will go through each diagonal exactly 1 time. The minimum on each diagonal is the upper right cell. And we can go through all of this cells. Similar for maximum.

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

        @ilian04 could u plz clear meaning of "each diagonal" .plz because i am not getting what are u treying to convey by this word? there are just 2 diaginals ??

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it -7 Vote: I do not like it

          I was talking about this diagonals. First diagonal contains number 1. Second — 2 and 3. Third — 4, 5, and 6. Etc.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 2   Vote: I like it +17 Vote: I do not like it

            Thanks for this problem. I didn't get it in the contest but I enjoyed thinking about it afterwards.

            I would suggest for next time to put some English text about how exactly the grid was generated (maybe some formal math stuff like $$$i+j$$$ uniquely defines a diagonal or whatever) instead of distracting stories about accounting and "Celex-2021".

            In the contest I didn't make the trivial observation from the picture that each diagonal has increasing numbers (maybe that's my fault, and I'm supposed to infer that from the diagram with the color gradients).

            But I was re-reading the problem statement multiple times looking for some explanation about how the grid was generated, and eventually guessed some random pattern about how the columns and rows have incrementally increasing numbers.

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

For Problem D, I believe you can do in O(n) time. You don't need to use Binary Search, can also use two pointers approach. 81531917

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

    Yes of course, but author of problem thinks it is easier to understand binary search solution

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

    Can you help me. When I am iterating from 1 to 2*n , I am getting WA verdict. https://mirror.codeforces.com/contest/1358/submission/81554812 But when I itaerate upto 2*n-1 I got AC verdict. https://mirror.codeforces.com/contest/1358/submission/81554853.

    I am not able to figure out the issue.

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

      Take a look at 81557505

      • I pre-filled your arrays w/ zeros (maybe this isn't needed, but good habit I guess?)
      • Your sum and pre arrays should be size 2n+1 instead of 2n+2.

      When you run lower_bound or upper_bound, the your arrays / vectors need to be sorted in increasing order. If you have an extra 0 element at the end (or is otherwise unsorted), the binary search has undefined behaviour. I would guess both your submissions technically have undefined behaviour, but one of them just happens to pass.

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

        Thanks for giving your time. Nice explanation also. Finally issue resolved

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

    Thank you.

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

    yeah i was thinking that as well, but the sliding window implementation was getting cancerous so i just gave up. i think author's solution is easier to implement but harder to understand, the 2 pointer method is more intuitive to come up with but holy hell, is it hard to implement (or i need more experience implementing weird 2 pointer problems)

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

    It took me some time to understand how and why the nested loop while works. Great solution btw. Just please tell me your reasoning for making size of d as 2*n and the condition of first while loop.

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

      Basically, you want d as 2*n because it the trip starts in month n, the trip might extend into the next year (eg: if a trip starts in year 1 month n-1, it could end in year 2 month 2) This is why d is the same array repeated twice. Basically, d stores the number of days of every month in year 1 and year 2.

      Ptr2 tracks the month the trip ENDS. ptr2 <= 2n-1 means the trip must end in year 1 or year 2.

      How do we know the trip cannot end in year 3 or later? Let's suppose the trip ends in year 3, month x. Since we know the trip must have only been under 1 year, then the trip must've started in year 2 month x or later. We know that an equivalent trip exists where you can start after year 1 month x, and end at year 2, month x.

      Let me know if you have any questions about this explanation. Obviously not as rigorous as whatever the authors can come up with :)

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

    Wow!!It's easy to understand!! :D

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

amazing tutorial crazyilian !!

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

Can anyone please check my solution out for problem B and let me know why I got TLE

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

    time complexity of 'int a[200001]={0}' = 200001, and the number of test cases = 10000 so total complexity of your code = 10000 * 200001 > 2 seconds.

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

      Wait...the editorial solution is O(N Log(N)) per test. which is 2e5*log(2e5). There are 1e5 testcases. That's 2e10*log(2e5) which is even greater!

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

        It's guaranteed that the sum of $$$n$$$ of all tests is at most $$$2e5$$$, so it's actually $$$2e5 \cdot \log(2e5)$$$.

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

          Got it. Thank you. I will read the question carefully from next time.

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

For D, you don't need binsearch. You can do a loop by which month you end on where you keep track of the the number of days left in the starting month and do a little casework on how many days you're advancing each loop. This is easier done going backwards.

Complexity: improved from $$$O(n \log n)$$$ to $$$O(n)$$$. Not that anybody really cares about that log factor.

81538134 — Here's my solution in weird, overabstracted Haskell. If, say, three people ask, I might write up a more readable C++ implementation.

EDIT: Apparently arthurg has already done that; refer to his post.

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

    that is true. but solution with binary search is easier to understand and write, so we put it in tutorial

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

Ques A 81487617 Can anyone help I don't get what is difference between my solution and official solution.

official solution says m*n+1/2 whereas i wrote ceil((m*n)/2.0) is there any diff?

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

    Your idea is correct, but you forgot that $$$ceil$$$ returns a float, not an integer. So if you try to output $$$1000000.0$$$, you'll actually get $$$1e+006$$$. You should round the float to integer (e.g. with int(x+0.5)), or, even better, always use integers (e.g. (n*m+1)/2).

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

    Make sure to read your testcase results. Testcase 3 says:

    wrong output format Expected integer, but "1e+006" found

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

Link

Can anyone tell me whats wrong in this logic?

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

In C I put in a redundant condition to check if x1<=x2 and y1<=y2. But this fails certain testcases. Why would that be can anyone help me with this? What could I be missing here. 81523820

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    if(x-a<0||y-a<0) there must be y-b<0, i think

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

      well thats really stupid of me. howcome i mixed up a and b. damn that cost me a a couple of hundreds in rank

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

I would like to recommend everyone (or maybe those who are not into problem-setting) to read round log just to get an idea of how much efforts go down in making a good quality official Codeforces round.

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

Am I the only one who solved D without noticing that the end of the vacation coincides with the end of some month? 81543406

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

Please ,Remove the picture of problem D .

its look like ……….

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

Very good explanation for problem C.

»
4 years ago, # |
  Vote: I like it -166 Vote: I do not like it

Memes in problem statement would have been nice!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In the end, we came up with E, and the old E moved to D.

Thank you, that explains why I found it so hard.

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

How does https://mirror.codeforces.com/contest/1358/submission/81520389 exceed time limit? since max of a is 2*10^5 or just O(2n) how does it exceed TL?? It passed the pretests during the contest, but i saw that after the contest i got it wrong :(

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

    The for loop runs up to 2e5 times, for every one of the 10000 testcases.

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

I solved D using the idea that optimal answer coincides with end of a month. But now I have an issue. Let's say after concatenating 2 arrays to consider the whole array as one year we get 1 2 1 2 1 2 1 2 1 2 1 2 (insert more 1 2 over here)... 1 2 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1 2 3 4 1 2 3 4. Now let's say we consider the segment 1 2 3 4 1 2 3 1 2 1 2 3 4 1 2 3 4 (the segment after 5). It ends at 4 right. So if we move this to left by 1 the answer should decrease because then it would not be end of an array(month). But when we shift it to left by 1 we subtract 4 and add 5(see in original array.. 5 is before 1) so in total we end up adding 1 to the answer. So how to we prove that optimal answer should have end of a month when this is failing over here.

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

    Also, one of the optimal answers will 2 3 4 5 1 2 3 4 1 2 3 1 2 1 2 3 4

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

    You're right, we can shift it to the left by 1 and increase the answer. However, you can continue shifting it to the left and get 2 3 4 5 1 2 3 4 1 2 3 1 2 1 2 3 4, which does end at the end of the month.

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

      So basically we can't just prove it by using one segments right. It's kind of ternary search. Got confused because in editorial you explain using just one segment and shift it. That is not always the case right? We have to show that it will decrease and increase both and form some sort of concave function. Am I missing something? Basically I want to know that if I came up with that case during the contest how(how to prove it then) and why would I proceed with the same approach of optimal answer ending in a month?

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

        Maybe you missed that we see rightmost optimal segment in proof?

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

          I'm sorry but what difference does that make?

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

            If we shift segment to right, sum will strictly decrease

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

              Yes that's what I exactly get from the editorial that we can't shift rightmost segment to further right. But the thing I'm not getting is that how to prove that it'll end up at the end of some month while shifting to the left? How does the editorial prove that fact?

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

                It is proved by contradiction,if this statement (about end of the month) not true we have contradiction, so that's impossible, and statement is true.... I can't explain it clearly

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

                  I can't understand it clearly either. Contradiction is shifting it to left by 1 thus increasing the answer. But it's not proving that it'll stop at some endpoint. Maybe I'm missing something but I'm not at all clear with that. Because otherwise if I make a statement that the answer will not lie at the endpoint and then consider a segment like above and prove by contradiction by the same test case above then I don't think that proves anything. Please tell me what am I missing.

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

                  In editorial there is a proof, that shows we can shift segment only left or right only 1 time, and it will be incorrect. We don't shift it infinitely,only one time. Please reread the editorial, I am really sorry, that I can't explain it :(

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

Is it a problem — the last line in Excel? Ctrl+, and here it is!

For the last column, use Ctrl+.

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

Kudos codeforces team and the authors very fast tutorial and the rating was also updated very soon. I don't think both of these took place so fast ever. codeforces gets better every day.

thank you @MikeMirzayanov.

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

I'm having a hard time understanding test case #14 for problem E

3
1 1 1
908617379176 908617379175 908616031128

We'll need 1348046 ops to pref() 1 1 1 to

1 1348047 908616031128

and 1 op of reverse to make it to

908616031128 1348047 1

and 1 op of pref():

908616031128 908617379175 908617379176

and 1 op of reverse() to be the target array. How come the answer be 1348047?

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

    Do you mean F? And in that case, you have to print the number of pref operations, not the total.

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

Why isn't Ternary search applicable in D? Isn't the function a point wise supremum of affine and hence convex functions?

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

Those grannies are yelling "Go Corona Go"

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

D can also be solved in O(n)

Link to my submission:
https://mirror.codeforces.com/contest/1358/submission/81557479

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

    please explain the logic also..

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

      2 pointers instead of binary search

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

      Somewhat similar to Circular Kadane's Algorithm. Just instead of when sum become negative resetting to zero, remove that value of last month added if your sum exceeds x... kind of two pointer approach as the guy below has mentioned..

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

anyone plz help me to understand problem B ? thanks

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

For problem E I wrote a code which got WA in test 58 but I will share my idea : as mentioned in the editorial if a solution exists so it is >n/2 let's calculate the prefix array sum since in the second half of the array we have same values so we have two cases: either the accumulative sum will increase if value in second hlaf called x is greater than 0 or it will decrease so in both cases the array accumulative sum will either have a suffix(maybe empty) containing only strictly positive values or negative ones depending on the starting index here is my submission

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

Here i have something about problem C, which i was trying to solve but couldn't. First $$$x$$$ is for row and $$$y$$$ is for column.

A path can be seen as this, a binary sequence of length $$$x2-x1+y2-y1$$$, with number of ones equal to $$$x2-x1$$$. How this happens? oky see, when we want to choose a path, we are now in cell $$$[x1,\,y1]$$$ we can go down or right, if we go down then the head(the number on the cell we are, comparing to the number on the last cell we were) will be increased by $$$x+y+1$$$, and if we go right then the head will increase by $$$x+y$$$ so the difference between them is 1, and so it also applies to next numbers. So we have a sequence of ones and zeroes of length $$$x2-x1+y2-y1$$$ with $$$x2-x1$$$ ones(number of times we go down) and $$$y2-y1$$$ zeroes(number of times we go right).

Now the magic begins, two path's sums are different if and only if the sum of suffix sums of they're sequences are different. And so the answer to the problem is the number of different sum of suffix sums a binary sequences of length $$$x2-x1+y2-y1$$$ with $$$x2-x1$$$ ones can get, YAY, we turned our D1A problem to a literally harder problem. Please let me know if you could solve it that way.

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

    Actually i did C the way you described above.

    But after noticing, that when we go to the right, number in the cell will increase by x + y, and when we go down it will increase by x + y + 1. Due to one to one correspondence i replaced it with the sequence we would get, if number in the cell increased by 1 when we go down and stayed unchanged after going to the right.We will concider 2 new sequences distinct if their sums are different. Lets concider a path: once we go down the number in the cell increases, and this 1 will be added up to each cell in path, starting from this cell. So we can calculate the sum of the elements of the new sequence as a sum of l for all l, where l is the serial number(calculating from the end) of the turn we go down from in path. 1 <= l <= (x2 — x1 + y2 — y1) . So our task is reduced to finding number of different sums of x2 — x1 numbers(number of times we go down), where numbers are distinct natural numbers from the segment [1; (x2 — x1 + y2 — y1)]. The smallest possible sum is S1 = 1 + 2 + ... + (x2 — x1) and the largest possible sum is S2 = (y2 — y1 + x2 — x1) + (y2 — y1 + x2 — x1 — 1) + (y2 — y + x2 — x1 — 2) + ... + (y2 — y1 — 1). It is obvious that any sum between is reachable, it means that number of distinct sums is equal to S2 — S1 + 1. Using well known fromulas of summation , we get that answer is (x2 — x1)(y2 — y1) + 1.

    The problem you proposed could be solved similarly. Actually, the sum of suffix sums of your sequence is equal to the sum of elements of my new sequence(see above). (Because if we replace numbers in your sequnce by their suffix sums, we get my new sequence. And new criteria of distinctivity of sequences would be distinctivity of their sums of elements)

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

      Nice, i wanted some math/combinatorics solution for it, but yes the same idea as editorial can be used here, thank you.

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

Another way to visualize the solution to C : Imgur

The difference between max sum and min sum is shown in the last matrix. This difference is sum(green) — sum(blue). Hence total number of sums between the two is (max_sum — min_sum + 1) = 10 for this 4x4 example.

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

    LOL i'm glad that someone else saw it like that, i just needed to find a reliable way to actually calculate it so i wrote out each case on a grid and guessed the answer once i saw the x*y+1 pattern

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

      Yea it's one of those problems where people could sort of get away with a lucky guess, I suppose. It was certainly very time consuming to prove during the contest. I think a better strategy for such problems would be to just guess 1-2 times based on intuition, before going the long route of proving the solution..

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

      I also solved the same way.

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

    if it is a rectangle instead of a square?

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

      Take a 3x4 :

      Range of sums is from 0 to 6. Answer: is calculated as the (sum of numbers along green path) — (sum of numbers along blue path) + 1 :

      (0 + 1 + 2 + 2 + 1 + 0) - (0 + 0 + 0 + 0 + 0 + 0) + 1 = 7
      

      Basically, it doesn't matter what numbers are in the rectangle (i.e. x1, x2, y1, y2 are irrelevant. All that matters is x2-x1 and y2-y1). All 3x4 rectangles boil down to the numbers in the third diagram. The path with the smallest sum runs along the blue cells (right on row 1 and then down on column n) and the path with the largest sum runs along the green cells (down on column 1 and then right on row m)

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

    thanks bro for this great visualization but sorry that I am still unable to get how does that make us reach to (c — a) * (d — b) result

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

      The visualization was actually more of the proof and how to think about the solution.

      To get the m * n formula, consider that you have a 2x4 matrix (2 rows, 4 columns), so you can move down 2 times and right 4 times. The smallest sum path is: DDRRRR and largest sum path is RRRRDD. Every other path in between needs to be included. So here are all the paths (from smallest to largest) :

      RRRRDD
      RRRDRD
      RRDRRD
      RDRRRD
      DRRRRD
      DRRRDR
      DRRDRR
      DRDRRR
      DDRRRR
      

      This comes to: (number of downs) * (number of rights) + 1 = 9 for this 2x4 example.

      I had solved it using a different method by counting the number of diagonals and adding their "lengths" (as each diagonal "length" represents the difference between the smallest and largest elements on that diagonal). So the visualization was more pertinent to that solution.

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

    huge thanks bro..i understood

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

crazyilian The solution to problem C: Celex Update contains a (q--) instead of a (t--).

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

So is this balanced ? I mean no graphs and no data structures ?

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

typo in D di=a1(a1+z)2+...+ai(ai+1)2 that must be a1(a1+1) crazyilian

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Problem F can be solved in $$$O(\log^2 C \cdot n \cdot min(n, t))$$$.

It is possible to show that after applying $$$k$$$ operations of "rollback" the elements of $$$b$$$ will change as follows:

$$$b_{i} = \sum_{j=0}^{min(i, k)}(-1)^{j} \cdot \binom{k}{j} \cdot b_{i-j}$$$

This calculation takes $$$O(n \cdot min(n, k))$$$ time.

Instead of applying a list of rollback operations in a row one-by-one, I want to make a binsearch to calculate the maximal number of operations I can apply.

In details, these two conditions must hold if it's possible to apply some number of rollbacks:

  1. All elements of the resulting array must be positive

  2. The sum of all elements must be not less than the sum of elements in $$$a$$$.

It can be proven that while applying rollbacks if at some point a negative element appears in an array, then it will stay there forever.

So, this solution works in $$$O(\log C \cdot n \cdot min(n, t) \cdot R)$$$, where $$$R$$$ — number of reverses in the optimal answer.

If $$$n = 2$$$, $$$R = O(\log C)$$$, hence it holds for the bigger values of $$$n$$$.

In order to overcome overflow problems, the binsearch can work similarly to binary lifting (firstly, we increase the step by $$$1$$$, $$$2$$$, $$$4$$$, ... and then decrease it in the reverse order).

This solution doesn't require separate consideration of the case $$$n = 2$$$.

My code: 81528455

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

E also can be solved using min segment tree with push updates. As In solution k >= n/2, we iterate k from n/2 to n,add x on prefix 0...n-k and check if it > 0 81558894

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

D can be solved by:

  1. Doubling the array d[] and reversing it.
  2. Using two pointers to find the maximal score for any given starting month (this will really be the ending month since the array was reversed) in O(n) time.

81566497

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

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

C. There are six possible unique sums(on the diagram). But why is the answer 5?(2*2+1)

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

    take test case (1,1) and (3,3), down right right down sum = right down down right sum even though they are two different paths.

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

Can someone pls explain how is Problem C different from the standard Find number of ways to reach one point from another in a grid which has an answer of (M+N)!/(M)! (N)! after shifting x1, y1, to origin?

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

    take test case (1,1) (3,3) for example

    if you go: right down down right and down right right down, they result in the same sum. thus, you cannot count that.

    instead, take the minimum sum possible (go all right then all down), and then the maximum sum (all down then all right) and subtract them. i wrote out all the test cases (represented as xdelta and ydelta) and guessed that it was xdelta * ydelta after seeing the pattern

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

Great Contest!

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

Why are we not solving problem C in this way Let D1=x1-x2 D2=y1-y2 Ans would be arrangement of D1 no of x and D2 no of y So why we not directly write the ways of d1 x and d2 y Eg D1 is 3x-xxx and D2 is yyy ie 3y So ans is (3+3)! and also there are repeatitions of x and y so (3+3)!/3!3!

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

    you are solving for the no of distinct paths between starting and ending points but not for the distinct sum paths and also you cant find the factorial of 10^9 without a mod

»
4 years ago, # |
Rev. 29   Vote: I like it +7 Vote: I do not like it

I have a bit shorter solution for Problem F. The idea is approximately the same as the tutorial. I notice that when $$$n>2$$$, n*t is always smaller than 10^8, so we can implement the $$$n>2$$$ parts together. In my code, I just simulate the first 2000000 'P' operations regardless of n, which I think makes my code neater. Then I deal with n=2 specifically.

My Code

Submission 81693390

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

    Please hide the code inside spoiler tag.

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

    HackerMonk Can you just add comments in your code 81570956 so it is more understandable, since your code seems to be much simpler and nice, in comparison to the editorial one.

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

      No problem, I just updated my comments. I'm glad if it helps. ^_^

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

Thanks a lot for sharing your experience as first-time problemsetters! I'm currently waiting on a proposal I made, so your story helps me know more or less what to expect from the coordinator (patience, more than anything :P). This is specially cool since I've never seen anyone write about their experience with the coordinator or with Mike, they're kind of an unspoken secret throughout setters, so thanks for breaking the ice on that.

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

For problem C, I calculated the actual minimum and maximum sum possible and got TLE for using big integer in C++. My solution This might help in future in such diagonal filling problems if constraints are a little lower. P.S. — I 90% sure my solution gives the correct answer. Can someone give me assurance of 100% or tell me it is wrong for some cases?

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

how is (c — a) * (d — b) giving unique paths in problem C please explain? I think I am a bit weak at p&c so explain in easy language please

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

    Ok let me explain this to u ... may it helps u!! See first of all u go through the first row up to the last coloum (that path of minimum sum). Now all u need to do is that go up to the second last coloumn and move down and go right again and u will see that u are matching with the same path. Now take the same turn for third last column(go down) and then go right staight and then u will be in the last coloumn matched up with the initial path...u will better find this in the editorial .. by doing this u can see that every time u are making change in the (y2 — y1) coloumn and reaching the the last coloumn by going straing right. The same thing can be done for the rows also u will make changes in (x2 — x1) rows. so the number of path would by the multiplication of (x2 — x1) * (y2 — y1) + 1. NOw why +1? because we are merging into the path of minimum sum and we calculated all possible path to merge into it but we haven't count the original path (path of minimum sum) so +1 is for that. EDIT1 — sorry for any grammatical mistake. EDIT2 — see something else if u don't find proper help by this THANKS U

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

That's an interesting editorial and well explained

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

I used 2 pointer for D but it gives WA because of overflow in C++, i tried unsigned long long too 81577649

I think it's overflow because my exactly same python sol is getting AC 81577330.

Can anyone plz tell me where I can improve?

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

I think we could make memes out of these memes.

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

amazing contest! questions were interesting to solve

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

I just FUCKING don't understand what does the picture mean in D.

funny mud pee

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

    +1

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

    I declare that it's only my personal attitude.

    Someone is saving others' lives, while someone is just slandering.

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

      I think that controversial pictures like this shouldn't appear

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

      It seems that a large number of people disagree with what Chinese people have done.

      清者自清

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

    Language...It's true that this picture makes an insulting presence, but that f-word does not solve the problem. Shouldn't we just contact the authors for a declarement?

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

    +1

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

D in O(N): I know I'm dumb, Can someone please tell me the problem with my lame attempt to solve D.

https://mirror.codeforces.com/contest/1358/submission/81573541

#include <bits/stdc++.h>
 
using namespace std;
 
long long sum(long long e, long long s)
{
  return (e * (e + 1) / 2) - (s * (s + 1) / 2);
}
 
int main()
{
  long long n, x;
  scanf("%lld %lld", &n, &x);
 
  long long maxDays = 0;
  vector<long long> v(n);
  for(int i = 0; i < n; i++)
  {
    scanf("%lld", &v[i]);
    maxDays = max(maxDays, v[i]);
  }
 
  vector<long long> v2;
  v2.insert(v2.end(), v.begin(), v.end());
  v2.insert(v2.end(), v.begin(), v.end());
 
  int start = v2.size() - 1;
  int end = start;
  long long tx = x;
  long long ans = 0;
  long long h = 0;
  if(maxDays >= x)
    ans = sum(maxDays, maxDays - x);
  else
  {
    while(end >= 0)
    {
      long long diff;
      while(tx && end > 0)
      {
        diff = min(v2[end], tx);
        h = h + sum(v2[end], v2[end] - diff);
        tx = tx - diff;
        if(tx)
          end--;
 
        // cout << "tx " << tx << " diff " << diff << " h " << h << " end " << end << " start " << start << endl;
      }
 
      ans = max(ans, h);
      if(end < 0)
        break;
      h = h - sum(v2[end], v2[end] - diff);
      tx = tx + diff;
      if(start == end)
        break;
      else
      {
        h = h - sum(v2[start], 0);
        tx = tx + v2[start--];
      }
 
      // cout << "tx " << tx << " diff " << diff << endl;
    }
  }
 
  printf("%lld\n", ans);
}
»
4 years ago, # |
Rev. 3   Vote: I like it -31 Vote: I do not like it

nmsl

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

    How made winds, I love it :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Never mind the scandal and liber❥❥❥❥❥

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

    I just like the spirit of War Wolf. Although I am a Japanese, I still learned a lot from this man. I hope you can spread this kind of ideology globally, so that all human beings can be saved from the imperialism! China No.1!

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

I would like to thank 300iq for removing the pictures.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    They should write a blog apologizing for it.

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

      Don't be so angry.Maybe they just want to joke.I think removing it is proper enough.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -24 Vote: I do not like it

        犯我中华者,虽远必诛!

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

          Awww man, don't be too serious about this, it'll only intensify the conflict.

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

        Indifferently insisting on presenting the "joke" anyway is not.

        A blog might be too much but at least consider the feelings of the masses who have suffered. Humankind should be kind. Humankind needs to unite in the face of the pandemic.

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

          I agree that they shouldn't post that picture.

          But I am not defending for them. I mean, some people aren't sensitive enough that they cannot realize how serious this problem is. Removing the picture and apologizing is necessary, but being much angrier than usual can't solve anything.

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

            Yeah, I agree. It's much better to suggest our opinions in a calm way instead of propogating meaningless slogans.

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

    indeed

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

I'm having some weird problems with overflow at problem D (I'm new at C++). Can someone take a look? (https://mirror.codeforces.com/contest/1358/submission/81592636)

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

    Should have made x long long... Java is way better for debugging lol.

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

At problem D at test 12, my program doesn't for some reason take the correct numbers of days as input, instead it takes just straight 0s... (https://mirror.codeforces.com/contest/1358/submission/81596666). Does anyone have any idea what could it be, since the program surprisingly works for earlier tests? I'm new to c++.

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

    Should have made x long long... Java is way better for debugging lol.

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

$$$t = O(\sqrt[n - 1]{C(n - 1)!})$$$. What? Using Stirling formula we can estimate, that $$$\sqrt[n]{n!} \approx \frac ne$$$, so whole solution will be $$$O(n^2)$$$

If we apply operation R $$$t$$$ times on array $$$[1, 1, \ldots 1]$$$ of length $$$n$$$ we get that last element equals $$${n + t - 1 \choose n - 1}$$$. I guess you used bound $$${n \choose k} \leq \frac{n^k}{k!}$$$, which works fine if $$$k$$$ is way smaller than $$$n$$$, but is an insane overestimate in our case, when $$$n = 2\cdot 10^5$$$, $$$t = 3$$$

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

    In fact the task was harded before (the limit was $$$10^{18}$$$, not $$$10^{12}$$$), but almost no one solved it so $$$C$$$ was reduced. So we did come up with $$$C_{n+t-1}^{n-1}$$$ which was used in the solution of the harder task. You're right, the complexity is definitely overestimated. We had a smaller bound before which worked well but we didn't have a solid proof, so we used this one. I'll try to prove it and fix the issue.

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

      Is it really that harder? For $$$n \geq 4$$$ largest number of steps before exceeding $$$10^{18}$$$ is $$$1817118$$$, which should be small enough. The only case left is $$$n = 3$$$. Within $$$k$$$ steps of R operations $$$[a, b, c]$$$ transforms into $$$[a', b', c'] = [a, b + ka, c + kb + \frac{k(k + 1)}{2}a]$$$.

      Solving for $$$a, b, c$$$ in terms of $$$a', b', c'$$$ (or substituting $$$-k$$$ for $$$k$$$) we get, that if we run $$$k$$$ reverse operations on $$$[a, b, c]$$$ we get $$$[a, b - ka, c - kb + \frac{k(k - 1)}{2}a]$$$. For the second value we can do basic binary search to find largest $$$k$$$ for which it is positive. Third is bitonic in terms of $$$k$$$, so to find where it is positive we can for example use ternary search to find minimum, and then on interval from $$$0$$$ to that maximal value binary search where it is positive (or use quadratic formula to find this segment).

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

        testers said that is "hard realization" and we made problem simplier

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

He also suddenly renamed problem F and city in the English version of problem D.

I wonder what was the original version of the city where Coronavirus-chan lives in.

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

    It was "Nahuw" (it isn't joke). In Russian, it sounds like a swear word, and even "Wuhan" in reverse)

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

I can't imagine what if it weren't 300iq that coordinated the round.

Will you feel good if someone else "just made some cool memes" about Chernobyl?

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

Hey, why isn't the path 1+3+5+8+13 taken into consideration in Problem C ?

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

In case anyone need Detail explanation for D Here

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

I'm not sure whether my solution to F is shorter...

Cuz it's a different way of presenting.

#include <cstdio>
#include <algorithm>
#include <cstdlib>
 
typedef long long LL;
const int MN = 200005, MS = 10000005;
 
int N;
LL A[MN], B[MN];
LL Ans[MS]; int C;
 
inline void check() {
	int ok1 = 1, ok2 = 1;
	for (int i = 1; i <= N; ++i) {
		if (A[i] != B[i]) ok1 = 0;
		if (A[i] != B[N - i + 1]) ok2 = 0;
	}
	if (!ok1 && ok2) ok1 = 1, Ans[++C] = -1;
	if (ok1) {
		LL tot1 = 0, tot2 = 0;
		for (int i = 1; i <= C; ++i)
			tot1 += Ans[i] == -1 ? 1 : Ans[i],
			tot2 += Ans[i] == -1 ? 0 : Ans[i];
		if (tot2 > 200000) printf("BIG\n%lld\n", tot2);
		else {
			printf("SMALL\n%lld\n", tot1);
			for (int i = C; i >= 1; --i) {
				if (Ans[i] == -1) putchar('R');
				else {
					int x = Ans[i];
					while (x) putchar('P'), --x;
				}
			}
			putchar('\n');
		}
		exit(0);
	}
}
 
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
	for (int i = 1; i <= N; ++i) scanf("%lld", &B[i]);
	check();
	if (N == 1) {
		if (A[1] == B[1]) puts("SMALL\n0\n");
		else puts("IMPOSSIBLE");
		return 0;
	}
	if (N == 2) {
		if (B[1] == B[2]) return puts("IMPOSSIBLE"), 0;
		while (1) {
//			printf("(%lld, %lld)\n", B[1], B[2]);
			if (B[1] > B[2]) std::swap(B[1], B[2]), Ans[++C] = -1;
			if (A[1] == B[1]) {
				LL diff = B[2] - A[2];
				if (diff < 0 || diff % B[1] != 0) return puts("IMPOSSIBLE"), 0;
				Ans[++C] = diff / B[1];
				break;
			}
			if (A[2] == B[1]) {
				LL diff = B[2] - A[1];
				if (diff < 0 || diff % B[1] != 0) return puts("IMPOSSIBLE"), 0;
				Ans[++C] = diff / B[1];
				Ans[++C] = -1;
				break;
			}
			if (B[2] % B[1] == 0) return puts("IMPOSSIBLE"), 0;
			Ans[++C] = B[2] / B[1];
			B[2] %= B[1];
		}
		LL tot1 = 0, tot2 = 0;
		for (int i = 1; i <= C; ++i)
			tot1 += Ans[i] == -1 ? 1 : Ans[i],
			tot2 += Ans[i] == -1 ? 0 : Ans[i];
		if (tot2 > 200000) printf("BIG\n%lld\n\n", tot2);
		else {
			printf("SMALL\n%lld\n", tot1);
			for (int i = C; i >= 1; --i) {
				if (Ans[i] == -1) putchar('R');
				else {
					int x = Ans[i];
					while (x) putchar('P'), --x;
				}
			}
			putchar('\n');
		}
		return 0;
	}
	while (1) {
		if (B[1] == B[N]) return puts("IMPOSSIBLE"), 0;
		if (B[1] > B[N]) {
			std::reverse(B + 1, B + N + 1), Ans[++C] = -1;
		} else {
			int ok = 1;
			for (int i = 2; i <= N; ++i)
				if (B[i - 1] >= B[i]) ok = 0;
			if (!ok) return puts("IMPOSSIBLE"), 0;
			for (int i = N; i >= 2; --i)
				B[i] -= B[i - 1];
			Ans[++C] = 1;
		}
//		printf("\t\t\t"); for (int i = 1; i <= N; ++i) printf("%lld, ", B[i]); puts("");
		check();
	}
	return 0;
}
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I realised that my proof of D was wrong. The proof in the editorial is very nice indeed!

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

In my view, codeforces is a great training platform with high quality problems. Please do not make it politicized.

Thank 300iq for his wise decision!

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

Can someone please explain the two pointer approach for problem D?

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

I can't seem to find the error in my solution so if anyone can spot it: https://mirror.codeforces.com/contest/1358/submission/81631720

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

Why downvotes?

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

Can someone tell me what is the time complexity of my code? https://mirror.codeforces.com/contest/1358/submission/81649608

»
4 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Great work guys, thanks for the contest. It requires a lot of work to host a contests on Codeforces. Problems were really interesting, had fun solving it.

It's sad that editorial is being downvoted so badly after such a hard work by problem setters,testers and codeforces. Hope it gets upvoted!! It motivates problem setters, we get more great contests :)

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

Yet another explanation of E:

  1. Read proof that k > n/2 from editorial (it's nice and simple)

  2. I check every k from n/2+n%2 to n and return the first good k.

  3. I always start at the end with the last k characters. Let's take a look (for simplicity assume that n is even):

t[1],t[2],..,t[n-k-1], t[n-k], base

base = t[n-k+1],..,t[n/2],x,..,x

The base is initially at the end and I will move it to the left. Let's look at the first 2 shifts:

t[1],t[2],..,t[n-k-1], base1, x

t[1],t[2],..,t[n-k-2], base2, x, x

sum(base1) = sum(base) + (t[n-k]-x)

sum(base2) = sum(base) + (t[n-k]-x) + (t[n-k-1]-x)

and so on. We see that the shift by l positions equals to adding a continuous subarray of values: (t[n-k]-x) +..+(t[n-k-l+1]-x) to sum of our initial base. In order to find the worst segment, we should find a minimum continuous subarray ending at an appropriate position (it is a standard subproblem — here we allow empty array).

So we can check if the k is ok by if(sum(base)+worst_subarray[n-k] > 0) in O(1) and we run it for all candidates.

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

    So, you wrote that we need to find the continuous subarray (t[n-k]-x) +..+(t[n-k-l+1]-x). I just wanted to confirm that will the worst_segment be of size l? If yes, then you also wrote that to find the worst segment, we have to find the minimum continuous subarray ending at an appropriate position(doesn't this take O(n) because we have to iterate by sliding window of size l to make sure that size of each segment is l and then take the one that gives minimum segment sum? And if this really takes O(n) then we do this for every possible k from n/2+n%2 to n and later return the first good k.)

    Can I get the link to the above explanation too?

    Thanx in advance.

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

      l is the size of the shift — from the end, we shift l times to the left. The size of the window is k.

      The shift of the window with size k by l positions to the left can be expressed as (t[n-k]-x) + (t[n-k-1]-x) +..+ (t[n-k-l+1]-x) + base. In order to find the worst shift (the position of the window, with the smallest sum) we need to find the smallest continuous subarray ending at n-k. We can pre-compute these values and for each k we find the position of the window in O(1).

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

        ok got you. So, isn't this quite brute force, because we are doing this for k between n/2 to n and for each k we are shifting the window by a total of l positions so isn't the total time complexity equal to O(n/2*l). Can you help in finding the effective time complexity of O(n/2*l). I don't know why I get the feeling that this is O(n*n). If so, can you correct me?

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

          You check each k in O(1). You find the worst shift by adding the minimum continuous subarray (each shift is represented by the continuous subarray, so the worst one is the minimum subarray). You can check my submission.

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

bad memes

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

I wonder whether the writers of this round are idiots.

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

I think the tutorial of problem E is too tedious...

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

    In E's editorial there are some inconsistent statements like "Notice that the minimum reported income (some number from $$$s$$$) doesn't depend on the first element of $$$p$$$", while next sentence says explicitly that if we change $$$p_1$$$ then all of the $$$s_i$$$ would change as well. So these $$$s_i$$$ do actually depend on $$$p_1$$$ while what is meant for $$$s_i$$$ is that its $$$\sum_{j=2}^{i} p_j$$$ part would never change.

    Anyways, do you have some easier solution/explanation?

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

      In my opinion, the first step is the key of this problem and its proof is given in the tutorial.

      Then let K=(n/2)+1 which is the minimum possible k, and then we let b[] = {s_1, s_2, ... , s_{n-k+1}} (s_i means a_i+a_{i+1}+...+a_{i+k-1}). And this can be calculated in O(n).

      Consider how b[] changes when K=K+1. It is obvious that b[] changes into b'[] = {s_1+x, s_2+x, ... , s_{n-k}+x} (or we can say we add b[] by x and remove the last element). Notice that if min_element(b[])>0 we get a valid answer, than we can solve this problem without the tedious mathematical derivation. And I think it is much more intuitive maybe?

      My code: https://mirror.codeforces.com/contest/1358/submission/81881217

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

        nice !! much intuitive as compared to all other solutions.

        Some did it by Segment trees, can you explain how can we do it using segment trees?

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

I just tried to use lower_bound instead of upper_bound in problem D. Still it got accepted. Can anyone explain the reason? Thanks in advance!! Submission--> 81893828

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

r

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

O(logn) solution for B

104247218 If you want explaination comment it and I will