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

Автор crazyilian, 4 года назад, По-русски

Это первый наш контест для нас троих (Alexdat2000, crazyilian, sevlll777), поэтому хотелось бы поделиться впечатлениями от создания этого контеста. Если хотите — прочитайте!

ROUND LOG

Ну и, конечно, вот сам разбор раунда.

1358A - Освещение парка
Идея: Alexdat2000

Картинка
Разбор
Решение

1358B - Марья Ивановна нарушает самоизоляцию
Идея: crazyilian

Картинка
Разбор
Решение

1358C - Обновление Celex
Идея: crazyilian

Картинка
Разбор
Решение

1358D - Лучший отпуск
Идея: sevlll777

Картинка
Разбор
Решение

1358E - Вы уволены?
Идея: sevlll777 и crazyilian

Картинка
Разбор
Решение

1358F - Вкусная печенька
Идея: sevlll777 и crazyilian

Картинка
Разбор
Решение от Alexdat2000
Решение от Alivk06 (более короткое)

Спасибо всем, кто участвовал в раунде! Надеемся, что вы подняли рейтинг! А если нет, то не огорчайтесь, у вас всё получится!

Разбор задач Codeforces Round 645 (Div. 2)
  • Проголосовать: нравится
  • -168
  • Проголосовать: не нравится

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

[deleted]

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +129 Проголосовать: не нравится
Разбор на русском / 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 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

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

    Problem D Video editorial. Link

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

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

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

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

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

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

      Thanks I suddenly understand it !

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

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

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

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

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

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

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

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

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

    something similar i did too

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

    purplesyringa what does maxLimit signify in your solution?

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

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

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

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

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

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

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

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

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

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

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

Good problems, pathetic memes.

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

Need more memes in upcoming tutorials

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

Can someone explain the B?

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

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

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

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

B explanation ?

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

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

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

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

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

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

Pictures were amazing!

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

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

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

    Do you mean the binomial coefficient?

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

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

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

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

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

        you can not solve though DP

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

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

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

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

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

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

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

i'm in love with those pictures

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Thank you.

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

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

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

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

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

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

amazing tutorial crazyilian !!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Link

Can anyone tell me whats wrong in this logic?

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

Я, как автор контеста, хотел бы выразиться по поводу слишком длинных условий, как считают некоторые участники раунда.

С самого начала написания контеста наши задачи были приурочены к каким-то явлениям, вещам, событиям, содержали много отсылок. К сожалению, первые задачи не дожили до сегодняшних дней, так как были отклонены координатором. Но мы поняли, что для нас интересно придумывать истории, какие-то мини вселенные, в которых происходит действие задачи. После одной задачи про изобретение вакцины (которую успешно отклонили), мы поняли, что тема коронавируса сейчас актуальна и стали придерживаться её. Мы понимали, что длинные условия нравятся не всем, некоторые тестеры нам об этом говорили. Но мы считали и до сих пор уверены, что в таком деле как программирование важно и вдохновение, погружение в атмосферу. Мы максимально старались приблизить перевод к оригиналу.

Тема использования коронавируса как объекта фольклора достаточно щепетильная. Мы осознаём всю его опасность, но это не причина накладывать табу на его обсуждение. Ещё ни разу в истории не было проблемы, которая бы решилась благодаря тому, что на неё не обращали внимание.

Надеемся, что, несмотря на длинные условия, вам всё равно понравились задачи и вы получили удовольствие от их решения.

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

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

    Хочется сказать что мне, как участнику во время раунда не хочется читать «истории» и «погружаться во вселенную», и, тем более, искать отсылки. Хочется получить удовольствие от решения задач, а для этого нужно все-таки решать, а не читать и пытаться понять условия.

    Также интересно в какую атмосферу погружает «коронавирус-тян»?

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

      Также интересно в какую атмосферу погружает «коронавирус-тян»?

      Романтическую.

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

        Мне вот лично не хочется чувствовать романтическую атмосферу во время тура и кажется я в этом не одинок

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

      ну у каждого по этому поводу своё мнение и всем сразу никак не угодить

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

        Нейтральные условия (как, например, на AtCoder) всем подходят.

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

          Ну если бы мы делали контест на AtCoder, то и сделали бы их нейтральными, как вы и хотите.

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

            С такими задачами на AtCoder никогда не пустят.

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

    Можно было написать легенды к задачам в отдельном абзаце. Авторы раунда 635 поступили именно так и многим это понравилось.

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

      Это, кончено, хорошее предложение, но в этом раунде легенды — 1-2 предложения, а у нас легенда вшита в саму задачу. Писать 2 раза условие на одной странице тоже как то не очень, ведь тогда участникам придётся искать где заканчивается одно условие и начинается то же самое, но в другом формате.

      Илиан предложил хорошее решение данной проблемы

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

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

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

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

sorry to say , after watching picture of problem D it seems like p**nforces !!

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

Please ,Remove the picture of problem D .

its look like ……….

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

Very good explanation for problem C.

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

I wrote a weird randomized solution, but it passes

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

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

Memes in problem statement would have been nice!

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

Я не понимаю решение задачи В.

Ну например, был дан такой массив бабушек: {10, 10, 10, 10, 10}. И получается, что функция сразу остановится на 5 бабушке и напишет в ответ 5? Но ведь предыдущие бабушки тоже не могут выйти, и на самом деле правильный ответ 1.

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

    почему остановится? Цикл остановится при a[i] <= i + 1

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

      А, понял, спасибо. Я куда-то не туда посмотрел

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

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

crazyilian, в задаче F написано что должно выполняться Y[i]>=Y[i-1], хотя имелось в виду Y[i]>Y[i-1].

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

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

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

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

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

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

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

          I'm sorry but what difference does that make?

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

            If we shift segment to right, sum will strictly decrease

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

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

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

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

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

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

For the last column, use Ctrl+.

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

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

For each of the n ends, let's make a binsearch to find which month contains --------->> its <<--(what is its in this ??)------- left border (k days less than the right one). You can use array ci to check whether the left border lies to the left/in the block/to the right, and use array di to restore the answer.

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

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

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

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

Those grannies are yelling "Go Corona Go"

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

D can also be solved in O(n)

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

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

    please explain the logic also..

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

      2 pointers instead of binary search

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

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

Это мое решение задачи Е 81526056. crazyilian есть ли у тебя или у кого-то предположение как это сломать? Потому что по-моему почти очевидное решение, которое первым приходит в голову, когда пытаешься запихать. Я не смог придумать тест. Коротко опишу решение, если x>0, то k=n должно подойти, иначе ответ -1. Если x<0, то я проверяю все k при которых сумма на суффиксе будет >0.

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

anyone plz help me to understand problem B ? thanks

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

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

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

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

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

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

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

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

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

      I also solved the same way.

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

    if it is a rectangle instead of a square?

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

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

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

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

    huge thanks bro..i understood

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

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

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

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

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

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

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

ну очевидно почему картинки убрали.коронавирус-чан выглядит совсем не так

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

    А как она выглядит? Мне даже интересно стало

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

      штуки на волосах зеленые а не чёрные,и не такая лолиподобная.

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

        Не понял что зелёное, но оригинал этой картинки выглядел не так.

        ориг

        А удалили только за 18 часов до начала. Примерно месяц она успешно была в условиях.

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

          А, зелёные пучки, осознал. Ну у каждого свои вкусы и взгляды¯_(ツ)_/¯

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

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

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

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

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

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

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

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

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

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

Great Contest!

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

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

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

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

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

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

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

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

That's an interesting editorial and well explained

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

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

I think we could make memes out of these memes.

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

May be there is another solution to D which seems O(n), does not need vector

Idea is sliding window , please see the code

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

typedef long long ll;
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _ref(i,a,b) for(int i=a;i>=b;i--)
#define MAXN 555555

#define ff(i) ((1+(ll)(i))*(ll)(i)/2)
ll n;
ll a[MAXN];
ll sum=0, ans=0,quit=0, x;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>x;
    _for(i,0,n)cin>>a[i];
    ll l=0, r=0, que=0, quitl=0, quitr=0;
    while(1){
        while(que<x){
            que+=a[r];
            sum+=ff(a[r]);
            r++;
            if(r==n){r=0;quitr=1;}
        }
        while(que>=x){
            que-=a[l];
            sum-=ff(a[l]);
            l++;
            if(l==n){l=0;quitl=1;}
        }
        if(que<x){
            if(l>=1)ans=max(ans, sum+ff(a[l-1])-ff(que+a[l-1]-x));
            else ans=max(ans, sum+ff(a[n-1])-ff(que+a[n-1]-x));
        }
        if(quitl&&quitr)break;
    }
    cout<<ans<<endl;
}
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

amazing contest! questions were interesting to solve

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

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

funny mud pee

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

    +1

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

    I declare that it's only my personal attitude.

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

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

      I think that controversial pictures like this shouldn't appear

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

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

      清者自清

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

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

    +1

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

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

nmsl

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

    How made winds, I love it :)

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

    Never mind the scandal and liber❥❥❥❥❥

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

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

nmsl

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

I'm having some weird problems with overflow or something at the problem D (i'm new to c++). Does anyone know what could be the problem? (https://mirror.codeforces.com/contest/1358/submission/81592636)

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

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

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

    They should write a blog apologizing for it.

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

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

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

        犯我中华者,虽远必诛!

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

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

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

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

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

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

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

    indeed

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

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

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

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

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

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

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

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

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

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

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

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

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

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

In case anyone need Detail explanation for D Here

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

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

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

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

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

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

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

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

Why downvotes?

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

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

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

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

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

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

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

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

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

bad memes

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

I wonder whether the writers of this round are idiots.

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

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

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

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

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

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

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

r

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

O(logn) solution for B

104247218 If you want explaination comment it and I will