crazyilian's blog

By crazyilian, 2 years ago, translation,

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.

Picture
Tutorial
Solution
Picture
Tutorial
Solution
Picture
Tutorial
Solution
Picture
Tutorial
Solution
Picture
Tutorial
Solution
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!

• -168

 » 2 years ago, # | ← Rev. 4 →   +129 Разбор на русском / Russian tutorialЕще одно решение задачи E, которое мне кажется более простым, чем авторское.Пусть все элементы из второй половины массива $=x$.Пусть $s_k(i) = a_i + a_{i+1} + \ldots + a_{i+k-1}$.Если существует такое $k$, что $k\le\tfrac{n}{2}$, то давайте посмотрим на такие сообщаемые числа: $s_k(i)$ и $s_k(i+k)$. Заметим, что если мы удвоим $k$, то $i$-е сообщаемое число будет равняться $s_{2k}(i) = s_k(i) + s_k(i+k)$. Так как $s_k(i)>0$ и $s_k(i+k)>0$, то $s_{2k}(i)>0$. То есть, после удвоения $k$, новое $k$ всё ещё будет подходить. Поэтому будем искать $k$, удовлетворяющее условию $k>\tfrac{n}{2}$.Так как $k>\tfrac{n}{2}$, то для всех индексов $i$ должно выполняться $i+k>\tfrac{n}{2}$, то есть, все числа справа от отрезка $[i,\ \ldots,\ i+k-1]$ одинаковы и равны $x$.Заметим, что если $x \ge 0$ и какой-то $k$ подходит, то подходит и $k+1$, потому что $s_{k+1}(i) = s_{k}(i) + x \ge s_{k} > 0$, то есть при $x \ge 0$ достаточно проверить случай $k = n$.При $x < 0$ поступим следующим образом. Найдем для каждого $i$ такие числа $p$, что $s_p(i) > 0$. Заметим, что если $s_{p}(i) > 0$, то и $s_{p-1}(i) = s_{p}(i) + (-x) > s_{p}(i) > 0$, то есть, $p$ монотонно. Значит, разрешенные $p$ образуют отрезок от единицы до некоторого ограничения $t[i]$. В силу монотонности его можно узнать легко, используя массив префиксных сумм и бинарный поиск по $t[i]$ за $\mathcal{O}(\log{n})$, или использовать формулу (увеличение $p$ на 1 соответствует уменьшению суммы на $-x$) за $\mathcal{O}(1)$. Если для каких-то индексов никакой $p$ не подходит, будем считать $t[i] = 0$.Итак, теперь заметим, что $k$ подходит тогда и только тогда, когда для всех $i$ от $0$ до $n - k$ выполняется $s_k(i) > 0$ или, что то же самое, $k \le t[i]$. Тогда можно просто перебрать $k$ от $n$ до нуля и проверять, что $k \le \min t[0,\ \ldots,\ n-k]$, поддерживая минимум. Если неравенство достигнуто — выводим $k$ как ответ. Если нет — выводим -1.Итоговая асимптотика — $\mathcal{O}(n \log{n})$ или $\mathcal{O}(n)$, в зависимости от реализации подсчета $t[i]$.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++#include using namespace std; #define int long long signed main() { int n; cin >> n; vector a(n), pref(n); for(int i = 0; i < (n + 1) / 2; i++) { cin >> a[i]; pref[i] = (i == 0 ? 0 : pref[i - 1]) + a[i]; } int x; cin >> x; for(int i = (n + 1) / 2; i < n; i++) { a[i] = x; pref[i] = (i == 0 ? 0 : pref[i - 1]) + a[i]; } if(pref.back() > 0) { cout << n << endl; return 0; } if(x >= 0) { cout << -1 << endl; return 0; } vector maxlimit(n); 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; } int limit = 1000000000000LL; for(int i = 0; i < n; i++) { limit = min(limit, maxlimit[i]); if(n - i <= limit) { cout << limit << endl; return 0; } } cout << -1 << endl; return 0; }  Pythonimport bisect n = int(input()) a = list(map(int, input().split())) x = int(input()) a += [x] * (n // 2) pref = [a[0]] for i in range(1, n): pref.append(pref[-1] + a[i]) if pref[-1] > 0: print(n) raise SystemExit(0) if x >= 0: print(-1) raise SystemExit(0) revpref = list(reversed(pref)) maxlimit = [] for i in range(n): maxlimit.append(n - bisect.bisect(revpref, 0 if i == 0 else pref[i - 1], hi=(n + 1) // 2) - i) limit = 1000000000000 for i in range(n): limit = min(limit, maxlimit[i]) if n - i <= limit: print(limit) raise SystemExit(0) print(-1) 
•  » » 2 years ago, # ^ |   +4 This is really cool. I tried establishing connections between k and k+1, never thought there would exist something between k and 2k.
•  » » 2 years ago, # ^ |   0 Problem D Video editorial. Link
•  » » » 2 years ago, # ^ |   -15 Nice editorial bro :-D
•  » » » 2 years ago, # ^ |   -15 (https://codeforces.com/contest/1358/submission/81578791) Please explain where i am wrong.
•  » » » » 2 years ago, # ^ |   -17 use lower_bound instead of upper_bound. https://codeforces.com/contest/1358/submission/81589987
•  » » » » » 2 years ago, # ^ |   -13 But what is wrong in using upperbound. Please explain.
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   -12 just make int a[n+1] to long long int a[n+1]
•  » » » » » » » 2 years ago, # ^ |   -13 thanks
•  » » » » » » 2 years ago, # ^ |   -12 use long long in place of int when defining a[n+1]. because the result get type cast to int instead of long long
•  » » » » » » » 2 years ago, # ^ |   -13 thanks
•  » » » 2 years ago, # ^ |   +3 Sir, your video tutorials and explanations are well understandable. Can you please make a video tutorial for problem E also :) Thanks in advance for your response. XD
•  » » » » 2 years ago, # ^ |   0 It might help you https://www.youtube.com/watch?v=qSGpFR_IIM0
•  » » 2 years ago, # ^ |   -9 For E why we cann't do k = n and check sum is positive or not? If positive then print k else -1
•  » » » 2 years ago, # ^ |   +3 I can look like -1 -1 -1 5 -1 -1 -1
•  » » 2 years ago, # ^ |   +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.
•  » » » 2 years ago, # ^ |   -10 Why return N-i? Can you explain more detailedly?
•  » » » 2 years ago, # ^ |   0 Thanks I suddenly understand it !
•  » » » » 2 years ago, # ^ |   0 Hey, can you explain that in the proof we are doing everything for some K, but in the code there is no loop for each k?? How does this give correct answer??
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Thanks for this explanation. I found it to be more practically reachable during a contest. Here's my C++ code: 81596230
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thanks for the explanation!!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 why are you returning N-i as k.can you explain?
•  » » » 2 years ago, # ^ |   +3 Excellent solution!Пока пытался разобраться, понял для себя более четкое объяснение:1) С X >= 0 Выше уже было сказано много и все понятно.2) Если X < 0, то будем искать K > N / 2(Очевидно, что K не может быть меньше, т.к. X < 0).3) Начнем перебирать различные K, начиная с N. Тогда на первом шаге минимальная сумма на отрезке длинной K — это сумма всех элементов. Научимся за O(1), находить наименьшую сумму на отрезке длиной на 1 меньше. Возможны следующие варианты: Минимум находится на новом отрезке, который заканчивается в позиции N — 1, т.е. на отрезке [N — K..N — 1], сумму на таких отрезках мы может быстро определять, заранее посчитав суффиксные суммы: suf[N — K]. Минимум находится на отрезке, который получается, если от отрезка с минимальной суммой для предыдущего 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; 
•  » » 2 years ago, # ^ | ← 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 imachug I am not able to understand this code of yours. Could you please elaborate a bit?
•  » » » 2 years ago, # ^ |   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.
•  » » » » 2 years ago, # ^ |   0 Thanks a lot. :)
•  » » 2 years ago, # ^ |   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.
•  » » » 2 years ago, # ^ |   0 N = 5 A = {100,-1,-1} x = -1So array becomes [100 -1 -1 -1 -1]p=5 works but p-1=4 does not!!!
•  » » » » 2 years ago, # ^ |   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$.
•  » » » » » 2 years ago, # ^ |   0 Thanks for explaining it again.(Really appreciate that you responded to my doubt).
•  » » 2 years ago, # ^ |   0 something similar i did too
•  » » 2 years ago, # ^ |   0 imachug what does maxLimit signify in your solution?
•  » » » 2 years ago, # ^ |   +1 It's called $t[i]$ in the tutorial.
•  » » 2 years ago, # ^ |   +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.
•  » » » 2 years ago, # ^ |   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.
•  » » » » 2 years ago, # ^ | ← 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
•  » » » » » 2 years ago, # ^ |   +3 Counter Testcase:Consider the incomes array: -1 2 2 -1 -1 -1Here sum of the array is 0For K = 4, sum of each subarray is not >0For K = 5, sum of each subarray is >0
•  » » 2 years ago, # ^ |   0 I could not understand the part of x<0. and whats t[i]. Can you please elaborate a little?
•  » » » 2 years ago, # ^ | ← 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]$.
•  » » » » 2 years ago, # ^ |   0 great explanation..I understood till here ..now how to find ans from t[i]... logic to find ans from t[]..?
•  » » » » 2 years ago, # ^ |   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...?
•  » » 23 months ago, # ^ | ← 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
 » 2 years ago, # |   +230 Good problems, pathetic memes.
•  » » 2 years ago, # ^ | ← Rev. 8 →   -120 reeeeeeeeeeeeeee downvote my comments u alll reeeeeeeeeeeeeeeee
•  » » » 2 years ago, # ^ |   -30 Alright, guys, you need to make me the most down voted account of all time. Down vote the comment above and this.
 » 2 years ago, # |   +9 Need more memes in upcoming tutorials
 » 2 years ago, # |   +14
•  » » 2 years ago, # ^ |   0 For C, as given in the solution diagram, cant he go from 1 -> 3 -> 5 -> 8 -> 13 ?
•  » » » 2 years ago, # ^ |   +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
•  » » » » 2 years ago, # ^ |   0 Thank you!
 » 2 years ago, # |   0 B explanation ?
•  » » 2 years ago, # ^ |   +4 What exactly don't you understand? I might be able to help.
•  » » » 2 years ago, # ^ |   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
 » 2 years ago, # |   +20 Very good problems! As a participant, I really enjoyed solving this contest! Especially I liked memes in the problems
 » 2 years ago, # |   +4
 » 2 years ago, # | ← Rev. 2 →   0 is it possible to solve C using nCk (binomial coefficient) ?
•  » » 2 years ago, # ^ |   0 Do you mean the binomial coefficient?
•  » » » 2 years ago, # ^ |   0 Yes, I should've made it more clear.
•  » » » » 2 years ago, # ^ |   -12 There's no solution using $C_n^k$ that I know about.
•  » » » » » 2 years ago, # ^ |   -9 Thanks pro
•  » » 2 years ago, # ^ |   0 You would get tle as far as I know because the limits are 1e9
•  » » » 2 years ago, # ^ |   0 I'm interested in learning the approach (if exists) regardless of the TLE, perhaps pre-calculating or DP can solve the TLE problem.
•  » » » » 2 years ago, # ^ |   +3 you can not solve though DP
•  » » » » 2 years ago, # ^ |   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
•  » » » » » 2 years ago, # ^ |   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!
•  » » 2 years ago, # ^ |   +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.
•  » » » 2 years ago, # ^ |   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.
•  » » » » 2 years ago, # ^ |   0 It's because the logic is wrong. The formula stated above is used in general to calculate the number of possible paths from (x1,y1) to (x2, y2) without considering the different sums of paths. We need to find the count of paths with different sums. So the formula you're using will treat two paths with same sum as different but ideally it should be counted as one.
•  » » » » 2 years ago, # ^ |   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.
•  » » » » » 2 years ago, # ^ |   +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.
 » 2 years ago, # | ← Rev. 2 →   -174 i'm in love with those pictures
•  » » 2 years ago, # ^ |   -176 thanks <3
 » 2 years ago, # | ← Rev. 3 →   0 Anyone for TLE/WA uphacking on E? :)81551641Edit: 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.
 » 2 years ago, # |   +4 Video Tutorial B:https://www.youtube.com/watch?v=OMRRHCeYsao
 » 2 years ago, # |   +1 When you check the shorter solution of F first ..and wonder this is the shorter one
•  » » 2 years ago, # ^ |   0 same]]
 » 2 years ago, # |   0 $O(N)$ solution for B (but it's barely within limits): 81499306
•  » » 2 years ago, # ^ |   +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
•  » » » 2 years ago, # ^ |   +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 :)
•  » » 12 months ago, # ^ |   0 would you please see my code and tell why it is giving TLE.118304039 Although i used a range variable to optimise it a bit.
 » 2 years ago, # | ← 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://codeforces.com/contest/1358/submission/81552953UPD: congrats to Kaban-5 for uphacking :)
•  » » 2 years ago, # ^ |   -17 we thought about it and it has some proofs (not strict) that there are no contrtests because second part has same numbers
 » 2 years ago, # |   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 :)
•  » » 2 years ago, # ^ |   +9 The +1 at the end is to ensure the minimum path is included in the answer too.
•  » » 2 years ago, # ^ |   0 plz someone explain this..why it is minimum and maximum sum path??
•  » » » 2 years ago, # ^ |   +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.
•  » » » » 2 years ago, # ^ |   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 ??
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   -7 I was talking about this diagonals. First diagonal contains number 1. Second — 2 and 3. Third — 4, 5, and 6. Etc.
•  » » » » » » 2 years ago, # ^ | ← 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.
 » 2 years ago, # |   +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
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 sweet solution!
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Yes of course, but author of problem thinks it is easier to understand binary search solution
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Can you help me. When I am iterating from 1 to 2*n , I am getting WA verdict. https://codeforces.com/contest/1358/submission/81554812 But when I itaerate upto 2*n-1 I got AC verdict. https://codeforces.com/contest/1358/submission/81554853.I am not able to figure out the issue.
•  » » » 2 years ago, # ^ |   +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.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thanks for giving your time. Nice explanation also. Finally issue resolved
•  » » 2 years ago, # ^ |   0 Thank you.
•  » » 2 years ago, # ^ |   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)
•  » » 2 years ago, # ^ |   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.
•  » » » 2 years ago, # ^ |   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 :)
•  » » » » 2 years ago, # ^ |   0 Understood every thing. Thanks for the explanation and the solution.
•  » » 23 months ago, # ^ |   0 Wow!!It's easy to understand!! :D
 » 2 years ago, # |   +8 amazing tutorial crazyilian !!
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone please check my solution out for problem B and let me know why I got TLE
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I had given wrong link before. I have corrected the link. Please have a look. In my view my solution is O(N) which is better than editorial solution of O(N Log(N)). Correct me if I am wrong.
•  » » 2 years ago, # ^ |   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.
•  » » » 2 years ago, # ^ |   0 Got it. I cleared the pretests and didn't think along this line of thought.
•  » » » 2 years ago, # ^ |   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!
•  » » » » 2 years ago, # ^ |   0 It's guaranteed that the sum of $n$ of all tests is at most $2e5$, so it's actually $2e5 \cdot \log(2e5)$.
•  » » » » » 2 years ago, # ^ |   +5 Got it. Thank you. I will read the question carefully from next time.
 » 2 years ago, # | ← 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.
•  » » 2 years ago, # ^ |   0 that is true. but solution with binary search is easier to understand and write, so we put it in tutorial
•  » » 2 years ago, # ^ |   0 Yes, Please do write in C++.
 » 2 years ago, # |   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?
•  » » 2 years ago, # ^ |   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).
•  » » » 2 years ago, # ^ |   0 Got it. thanks!
•  » » 2 years ago, # ^ |   0 Make sure to read your testcase results. Testcase 3 says:wrong output format Expected integer, but "1e+006" found
•  » » » 2 years ago, # ^ |   0 yeah my bad. will take care from now onwards.
 » 2 years ago, # |   0 LinkCan anyone tell me whats wrong in this logic?
 » 2 years ago, # |   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
•  » » 2 years ago, # ^ |   -22 if(x-a<0||y-a<0) there must be y-b<0, i think
•  » » » 2 years ago, # ^ |   0 well thats really stupid of me. howcome i mixed up a and b. damn that cost me a a couple of hundreds in rank
 » 2 years ago, # |   +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.
 » 2 years ago, # |   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
•  » » 2 years ago, # ^ |   +11 same
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Can you pleas tell me what is wrong in my submission?? https://codeforces.com/contest/1358/submission/81671202
 » 2 years ago, # |   +41 Please ,Remove the picture of problem D .its look like ……….
 » 2 years ago, # |   +1 Very good explanation for problem C.
 » 2 years ago, # |   -166 Memes in problem statement would have been nice!
•  » » 2 years ago, # ^ |   -148 thanks
 » 2 years ago, # |   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.
 » 2 years ago, # |   0 How does https://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 :(
•  » » 2 years ago, # ^ |   0 The for loop runs up to 2e5 times, for every one of the 10000 testcases.
 » 2 years ago, # | ← 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.
•  » » 2 years ago, # ^ | ← 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
•  » » 2 years ago, # ^ |   +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.
•  » » » 2 years ago, # ^ |   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?
•  » » » » 2 years ago, # ^ |   0 Maybe you missed that we see rightmost optimal segment in proof?
•  » » » » » 2 years ago, # ^ |   0 I'm sorry but what difference does that make?
•  » » » » » » 2 years ago, # ^ |   0 If we shift segment to right, sum will strictly decrease
•  » » » » » » » 2 years ago, # ^ | ← 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?
•  » » » » » » » » 2 years ago, # ^ |   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
•  » » » » » » » » » 2 years ago, # ^ | ← 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.
•  » » » » » » » » » 2 years ago, # ^ |   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 :(
 » 2 years ago, # |   +41 Is it a problem — the last line in Excel? Ctrl+↓, and here it is!For the last column, use Ctrl+→.
•  » » 2 years ago, # ^ |   +23 YOU are hired!
•  » » » 2 years ago, # ^ |   +27
•  » » 2 years ago, # ^ |   +15 This man was Albert Einstein.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I just saw it in OpenOffice, and in Excel it suddenly works too. By the way, the tables in OpenOffice are much smaller.Typical IT lesson in the school...
 » 2 years ago, # |   +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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 I think, authors and coordinator responsible for fast publishing
 » 2 years ago, # |   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?
•  » » 2 years ago, # ^ |   0 Do you mean F? And in that case, you have to print the number of pref operations, not the total.
•  » » » 2 years ago, # ^ |   0 Thanks so much! That's so tricky.
 » 2 years ago, # |   0 Why isn't Ternary search applicable in D? Isn't the function a point wise supremum of affine and hence convex functions?
 » 2 years ago, # |   +4 Those grannies are yelling "Go Corona Go"
 » 2 years ago, # | ← Rev. 2 →   +8 D can also be solved in O(n)Link to my submission:https://codeforces.com/contest/1358/submission/81557479
•  » » 2 years ago, # ^ |   0 please explain the logic also..
•  » » » 2 years ago, # ^ |   +4 2 pointers instead of binary search
•  » » » 2 years ago, # ^ | ← 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..
 » 2 years ago, # |   0 anyone plz help me to understand problem B ? thanks
 » 2 years ago, # | ← 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
 » 2 years ago, # |   +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.
•  » » 2 years ago, # ^ |   +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)
•  » » » 2 years ago, # ^ |   0 Nice, i wanted some math/combinatorics solution for it, but yes the same idea as editorial can be used here, thank you.
 » 2 years ago, # | ← Rev. 3 →   +24 Another way to visualize the solution to C : 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.
•  » » 2 years ago, # ^ |   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
•  » » » 2 years ago, # ^ | ← 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..
•  » » » 2 years ago, # ^ |   0 I also solved the same way.
•  » » 2 years ago, # ^ |   0 if it is a rectangle instead of a square?
•  » » » 2 years ago, # ^ | ← 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)
•  » » » » 2 years ago, # ^ |   +4 very thanks！I get it.
•  » » 2 years ago, # ^ |   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
•  » » » 2 years ago, # ^ |   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.
•  » » » » 2 years ago, # ^ |   0 thanks man i got it.great help
•  » » 9 months ago, # ^ |   0 huge thanks bro..i understood
 » 2 years ago, # | ← Rev. 2 →   +8 crazyilian The solution to problem C: Celex Update contains a (q--) instead of a (t--).
 » 2 years ago, # |   0 So is this balanced ? I mean no graphs and no data structures ?
•  » » 2 years ago, # ^ |   +8 Don't forget that 13 problems were redjected
 » 2 years ago, # | ← Rev. 2 →   0 typo in D di=a1(a1+z)2+...+ai(ai+1)2 that must be a1(a1+1) crazyilian
 » 2 years ago, # |   0 https://codeforces.com/contest/1358/submission/81540947 this o(n^2) solution passed D
 » 2 years ago, # |   0
 » 2 years ago, # |   +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: All elements of the resulting array must be positive 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
 » 2 years ago, # |   +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
 » 2 years ago, # |   0 D can be solved by: Doubling the array d[] and reversing it. 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
 » 2 years ago, # |   0 Can anyone suggest more observation-based problems like Problem C?Thank You.
 » 2 years ago, # |   +4
 » 2 years ago, # |   0 C. There are six possible unique sums(on the diagram). But why is the answer 5?(2*2+1)
•  » » 2 years ago, # ^ |   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.
 » 2 years ago, # | ← 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?
•  » » 2 years ago, # ^ |   0 take test case (1,1) (3,3) for exampleif 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
 » 2 years ago, # | ← Rev. 2 →   0 .deleted
 » 2 years ago, # |   0 Can any one tell me why my rating has gone down even though I solved one problem?
•  » » 2 years ago, # ^ |   0 Bro if u performance is poor than your current rating and also people with less ratings have performed better than u then ur rating would probably go down
 » 2 years ago, # |   0 Great Contest!
 » 2 years ago, # |   0 I am facing great difficulty in problem C and not able to visualise the problem in a good way can anyone give better explanation of how to approach the problem it would be great help
 » 2 years ago, # |   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!
•  » » 2 years ago, # ^ | ← 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
•  » » » 2 years ago, # ^ |   0 then how is (c — a) * (d — b) giving unique paths please explain? i think I am a bit weak at p&c
 » 2 years ago, # | ← 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#include using namespace std; typedef long long ll; const int mx = 2e6 + 10; ll n, a[mx], b[mx]; string fans = ""; //fans ==> final_ans void outp() { //since we are changing b to a and the task requires changing a to b, the whole operation queue (fans) should be reversed when outputted. reverse(fans.begin(),fans.end()); int num = count(fans.begin(), fans.end(), 'P'); if (num > 200000) cout << "BIG" << '\n' << num << '\n'; else cout << "SMALL" << '\n' << fans.size() << '\n' << fans << '\n'; exit(0); } //this function checks if array a equals to array b. If so, we add string s (representing some operations) to fans. void if_equal (string s) { for (int i = 1; i <= n; i ++) if (a[i] != b[I]) return ; fans += s; outp(); } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i ++) cin >> a[I]; for (int i = 1; i <= n; i ++) cin >> b[I]; //the following four lines check "if b equals a" and "if b equals to a in reversed order". if_equal(""); reverse(b + 1, b + n + 1); if_equal("R"); reverse(b + 1, b + n + 1); ll ti = 0; //the following loop simulates the first 2000000 'P' operations to change b to a. while ((ti ++) < 2000000) { if (b[1] > b[2]) { //if b[1] > b[2], we know for certain that 'R' must be operated before 'P', so that we don't get negative numbers. fans += 'R'; reverse(b + 1, b + n + 1); } //doing operation 'P'. fans += 'P'; for (int i = n; i >= 2; i --) b[i] -= b[i - 1]; //checking if b is still legal. for (int i = 1; i <= n; i ++) if (b[i] <= 0) { cout << "IMPOSSIBLE" << endl; return 0; } //checking "if b equals a" and "if b equals to a in reversed order". if_equal(""); reverse(b + 1, b + n + 1); if_equal("R"); reverse(b + 1, b + n + 1); } ti --; //when the program reaches this place, it means that t (same meaning as the tutorial mensioned) is larger than 2000000, which also means that n = 2. //the following process is nothing different from what the tutorial said. We just calculate the first 2000000 'P' in brutal-forced way, and it doesn't influence the answer. //n=2 ll x = b[1], y = b[2]; if (a[1] > a[2]) swap (a[1], a[2]); while (true) { if (x < y) swap (x, y); if (y == 0) { cout << "IMPOSSIBLE" << endl; return 0; } if (a[1] == y) { if ((x - a[2]) % y != 0 || x < a[2]) cout << "IMPOSSIBLE" << endl; else cout << "BIG" << endl << ti + (x - a[2]) / y << endl; return 0; } ti += x / y; x -= x / y * y; } // cout << "WTF " << endl; return 0; } Submission 81693390
•  » » 2 years ago, # ^ |   +8 Please hide the code inside spoiler tag.
•  » » » 2 years ago, # ^ |   +5 Thanks for your advice ^_^
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 No problem, I just updated my comments. I'm glad if it helps. ^_^
 » 2 years ago, # |   +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.
 » 2 years ago, # |   0 In the solution of the problem C, there should be while(t--) instead of while(q--). Did anyone notice that?
 » 2 years ago, # |   0 can anyone explain me the why complexity of B problem is O(nlogn)
•  » » 2 years ago, # ^ |   0 as we have used sorting algo which is nlog(n) and finding correct positioning of granny is maximum n so total complexity is O(nlog(n)+n) which can be written as O(nlog(n))
•  » » 2 years ago, # ^ |   0 also if u use binary search then it is nlog(n)+log(n)=nlog(n)
 » 2 years ago, # |   -44 I really liked the idea of using memes:-)
 » 2 years ago, # | ← 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?
 » 2 years ago, # |   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
•  » » 2 years ago, # ^ |   0 The same here with me? How this (x2 — x1) * (y2 — y1) is giving unique no. of path for different sums?
•  » » 2 years ago, # ^ |   +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
•  » » » 2 years ago, # ^ |   0 satisfactory
 » 2 years ago, # |   0 That's an interesting editorial and well explained
 » 2 years ago, # |   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?
 » 2 years ago, # |   0 I think we could make memes out of these memes.
 » 2 years ago, # |   0 https://codeforces.com/contest/1358/submission/81580601 why is it showing TLE i am using a prefix array but it is showing TLE
•  » » 2 years ago, # ^ |   0 You are running loop 200005 times and max test cases are 10^4, that would be 200005 * 10^4 which is more than 2 seconds.
 » 2 years ago, # |   0 Why i am getting TLE in B with this approach : https://codeforces.com/contest/1358/submission/81577715pls help:)
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Its the loop you are running till limit which can be (2 * 10^5) and the test cases can be 10 ^ 4 so that's more than 2 seconds.
 » 2 years ago, # |   0 crazyilian In third solution there would be t-- in while loop instead of q--. Thank You
 » 2 years ago, # |   +3 amazing contest! questions were interesting to solve
 » 2 years ago, # |   0 can anyone see my solution and help me on the celex update.I am not able to find when will the sum be repeated in a path. https://codeforces.com/contest/1358/submission/81527918
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 I don't know what's wrong with the approach but even if its correct it will time out. your m and n can be as big as 10 ^ 9 - 1 and you are running a n * m loop, that won't run under time limit better look for a different approach than waste time on this one.
•  » » » 2 years ago, # ^ |   0 thanks
 » 2 years ago, # |   +258 I just FUCKING don't understand what does the picture mean in D.funny mud pee
•  » » 2 years ago, # ^ |   0 +1
•  » » 2 years ago, # ^ |   +123 I declare that it's only my personal attitude.Someone is saving others' lives, while someone is just slandering.
•  » » » 2 years ago, # ^ |   +76 I think that controversial pictures like this shouldn't appear
•  » » » 2 years ago, # ^ |   +41 It seems that a large number of people disagree with what Chinese people have done.清者自清
•  » » 2 years ago, # ^ |   -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?
•  » » 2 years ago, # ^ |   0 +1
 » 2 years ago, # |   -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://codeforces.com/contest/1358/submission/81573541 #include 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 v(n); for(int i = 0; i < n; i++) { scanf("%lld", &v[i]); maxDays = max(maxDays, v[i]); } vector 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); } 
•  » » 2 years ago, # ^ |   0 Could somebody please tell why it's down voted so much?NOW ITS SUBMITTED https://codeforces.com/contest/1358/submission/81641980
 » 2 years ago, # | ← Rev. 3 →   -31 nmsl
•  » » 2 years ago, # ^ |   +1 How made winds, I love it :)
•  » » 2 years ago, # ^ |   -8 Never mind the scandal and liber❥❥❥❥❥
•  » » 2 years ago, # ^ |   +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!
•  » » » 2 years ago, # ^ |   0 Nah ur not...
 » 2 years ago, # |   +236 I would like to thank 300iq for removing the pictures.
•  » » 2 years ago, # ^ |   -13 They should write a blog apologizing for it.
•  » » » 2 years ago, # ^ |   -12 Don't be so angry.Maybe they just want to joke.I think removing it is proper enough.
•  » » » » 2 years ago, # ^ |   -24 犯我中华者,虽远必诛!
•  » » » » » 2 years ago, # ^ |   +1 Awww man, don't be too serious about this, it'll only intensify the conflict.
•  » » » » 2 years ago, # ^ |   +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.
•  » » » » » 2 years ago, # ^ |   -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.
•  » » » » » » 2 years ago, # ^ |   +8 Yeah, I agree. It's much better to suggest our opinions in a calm way instead of propogating meaningless slogans.
•  » » 2 years ago, # ^ |   +3 indeed
 » 2 years ago, # |   +8 I'm having some weird problems with overflow at problem D (I'm new at C++). Can someone take a look? (https://codeforces.com/contest/1358/submission/81592636)
•  » » 2 years ago, # ^ |   +8 Should have made x long long... Java is way better for debugging lol.
 » 2 years ago, # |   0 can someone explain approach of problem D using simple words, I am unable to understand the editorial...please help
 » 2 years ago, # |   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://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++.
•  » » 2 years ago, # ^ |   0 Should have made x long long... Java is way better for debugging lol.
 » 2 years ago, # |   +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$
•  » » 2 years ago, # ^ |   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.
•  » » » 2 years ago, # ^ |   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).
•  » » » » 2 years ago, # ^ |   +1 testers said that is "hard realization" and we made problem simplier
 » 2 years ago, # |   +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.
•  » » 2 years ago, # ^ |   +10 It was "Nahuw" (it isn't joke). In Russian, it sounds like a swear word, and even "Wuhan" in reverse)
 » 2 years ago, # |   +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?
 » 2 years ago, # |   0 Hey, why isn't the path 1+3+5+8+13 taken into consideration in Problem C ?
•  » » 2 years ago, # ^ |   0 Because it has the same sum as the path 1+2+5+9+13.
 » 2 years ago, # |   0 I have used a similar approach to editorial for some reason my test 12 gives some wrong answer can anyone pls help https://codeforces.com/contest/1358/submission/81605973?
 » 2 years ago, # | ← Rev. 3 →   0 The D can be solved in O(n), I think, just by using something like the inchworm. -81607685
 » 2 years ago, # |   0 i think C is more easier than B.. Though C some tricky but easy ❤By applying distance law (without square)+1 ; ****
•  » » 2 years ago, # ^ |   0 (without square root)
 » 2 years ago, # |   0 In case anyone need Detail explanation for D Here
 » 2 years ago, # |   0 Please anyone explain problem-c. Thanks in advance.
 » 2 years ago, # |   0 I'm not sure whether my solution to F is shorter...Cuz it's a different way of presenting. #include #include #include 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; } 
•  » » 2 years ago, # ^ |   0 You can use spoiler to show your code better. Spoilerowo
•  » » » 2 years ago, # ^ |   0 Ah, yes, thanks.
•  » » » 2 years ago, # ^ |   0 SpoilerNice!!
•  » » 2 years ago, # ^ |   0 https://codeforces.com/contest/1358/submission/81676727 my code is shorter, because most logic is consistant.
•  » » 2 years ago, # ^ |   0 orz. You solved it in the contest.
•  » » » 2 years ago, # ^ |   0 Nah, urs' better. stO qfhy Orz.
 » 2 years ago, # |   0 how u gyies make questions so easy in editorial section.how to think this way easy and clear approach. really these editorials are amazing.
 » 2 years ago, # |   0 I realised that my proof of D was wrong. The proof in the editorial is very nice indeed!
 » 2 years ago, # |   0 Solution of 3rd............ so much small.
 » 2 years ago, # | ← Rev. 6 →   -40 [Deleted]
 » 2 years ago, # |   +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!
 » 2 years ago, # |   0 For D, can we not find the month with greatest mo. of days and then expand about the months till we have any days left for vacation? Can someone help me where my approach 81552573 goes wrong?
 » 2 years ago, # |   +1 Can someone please explain the two pointer approach for problem D?
•  » » 2 years ago, # ^ |   0 This code might be helpful. https://codeforces.com/contest/1358/submission/81562536
 » 2 years ago, # |   0 I can't seem to find the error in my solution so if anyone can spot it: https://codeforces.com/contest/1358/submission/81631720
 » 2 years ago, # |   +10 Why downvotes?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +12 It insulted those who had died fighting a novel coronavirus ！（I'm Come from Wuhan :( ）
 » 2 years ago, # |   0 Can someone tell me what is the time complexity of my code? https://codeforces.com/contest/1358/submission/81649608
 » 2 years ago, # |   -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 :)
 » 2 years ago, # | ← Rev. 4 →   0 Yet another explanation of E: Read proof that k > n/2 from editorial (it's nice and simple) I check every k from n/2+n%2 to n and return the first good k. 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], basebase = t[n-k+1],..,t[n/2],x,..,xThe 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, xt[1],t[2],..,t[n-k-2], base2, x, xsum(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.
•  » » 2 years ago, # ^ |   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.
•  » » » 2 years ago, # ^ |   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).
•  » » » » 2 years ago, # ^ | ← 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?
•  » » » » » 2 years ago, # ^ |   0