### ilian04's blog

By ilian04, 5 months ago, translation, This is our first contest for the three of us (Alexdat2000, ilian04, Sevlll), 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! Tutorial of Codeforces Round #645 (Div. 2) Comments (309)
 » 5 months ago, # | ← Rev. 3 →   Разбор на русском / 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] 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) 
•  » » This is really cool. I tried establishing connections between k and k+1, never thought there would exist something between k and 2k.
•  » » Problem D Video editorial. Link
•  » » » Nice editorial bro :-D
•  » » » (https://codeforces.com/contest/1358/submission/81578791) Please explain where i am wrong.
•  » » » » use lower_bound instead of upper_bound. https://codeforces.com/contest/1358/submission/81589987
•  » » » » » But what is wrong in using upperbound. Please explain.
•  » » » » » » 5 months ago, # ^ | ← Rev. 3 →   just make int a[n+1] to long long int a[n+1]
•  » » » » » » » thanks
•  » » » » » » use long long in place of int when defining a[n+1]. because the result get type cast to int instead of long long
•  » » » » » » » thanks
•  » » » 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
•  » » For E why we cann't do k = n and check sum is positive or not? If positive then print k else -1
•  » » » I can look like -1 -1 -1 5 -1 -1 -1
•  » » 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.
•  » » » Why return N-i? Can you explain more detailedly?
•  » » » Thanks I suddenly understand it !
•  » » » » 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??
•  » » » 5 months ago, # ^ | ← Rev. 3 →   Thanks for this explanation. I found it to be more practically reachable during a contest. Here's my C++ code: 81596230
•  » » » 5 months ago, # ^ | ← Rev. 2 →   Thanks for the explanation!!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   why are you returning N-i as k.can you explain?
•  » » » 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; 
•  » » 5 months ago, # ^ | ← Rev. 2 →   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?
•  » » » 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.
•  » » » » Thanks a lot. :)
•  » » 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.
•  » » » N = 5 A = {100,-1,-1} x = -1So array becomes [100 -1 -1 -1 -1]p=5 works but p-1=4 does not!!!
•  » » » » 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$.
•  » » » » » Thanks for explaining it again.(Really appreciate that you responded to my doubt).
•  » » something similar i did too
•  » » imachug what does maxLimit signify in your solution?
•  » » » It's called $t[i]$ in the tutorial.
•  » » 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.
•  » » » 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   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
•  » » » » » 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
•  » » I could not understand the part of x<0. and whats t[i]. Can you please elaborate a little?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   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]$.
•  » » » » great explanation..I understood till here ..now how to find ans from t[i]... logic to find ans from t[]..?
•  » » » » 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 months ago, # ^ | ← Rev. 3 →   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
 » Good problems, pathetic memes.
•  » » 5 months ago, # ^ | ← Rev. 8 →   reeeeeeeeeeeeeee downvote my comments u alll reeeeeeeeeeeeeeeee
•  » » » Alright, guys, you need to make me the most down voted account of all time. Down vote the comment above and this.
 » Need more memes in upcoming tutorials
 »
•  » » For C, as given in the solution diagram, cant he go from 1 -> 3 -> 5 -> 8 -> 13 ?
•  » » » 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
•  » » » » Thank you!
 » B explanation ?
•  » » What exactly don't you understand? I might be able to help.
•  » » » 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
 » Very good problems! As a participant, I really enjoyed solving this contest! Especially I liked memes in the problems
 »
 » 5 months ago, # | ← Rev. 2 →   is it possible to solve C using nCk (binomial coefficient) ?
•  » » Do you mean the binomial coefficient?
•  » » » Yes, I should've made it more clear.
•  » » » » There's no solution using $C_n^k$ that I know about.
•  » » » » » Thanks pro
•  » » You would get tle as far as I know because the limits are 1e9
•  » » » I'm interested in learning the approach (if exists) regardless of the TLE, perhaps pre-calculating or DP can solve the TLE problem.
•  » » » » you can not solve though DP
•  » » » » 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
•  » » » » » 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!
•  » » 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.
•  » » » 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.
•  » » » » 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.
•  » » » » 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.
•  » » » » » 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.
 » 5 months ago, # | ← Rev. 2 →   i'm in love with those pictures
•  » » thanks <3
 » 5 months ago, # | ← Rev. 3 →   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.
 » When you check the shorter solution of F first ..and wonder this is the shorter one
•  » » same]]
 » $O(N)$ solution for B (but it's barely within limits): 81499306
•  » » 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
•  » » » 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 :)
 » 5 months ago, # | ← Rev. 2 →   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 :)
•  » » we thought about it and it has some proofs (not strict) that there are no contrtests because second part has same numbers
 » 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 :)
•  » » The +1 at the end is to ensure the minimum path is included in the answer too.
•  » » plz someone explain this..why it is minimum and maximum sum path??
•  » » » 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.
•  » » » » @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 ??
•  » » » » » 5 months ago, # ^ | ← Rev. 2 → I was talking about this diagonals. First diagonal contains number 1. Second — 2 and 3. Third — 4, 5, and 6. Etc.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   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.
 » 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
•  » » 5 months ago, # ^ | ← Rev. 2 →   sweet solution!
•  » » 5 months ago, # ^ | ← Rev. 2 →   Yes of course, but author of problem thinks it is easier to understand binary search solution
•  » » 5 months ago, # ^ | ← Rev. 2 →   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.
•  » » » 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   Thanks for giving your time. Nice explanation also. Finally issue resolved
•  » » Thank you.
•  » » 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)
•  » » 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.
•  » » » 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 :)
•  » » » » Understood every thing. Thanks for the explanation and the solution.
•  » » Wow!!It's easy to understand!! :D
 » amazing tutorial ilian04 !!
 » 5 months ago, # | ← Rev. 2 →   Can anyone please check my solution out for problem B and let me know why I got TLE
•  » » 5 months ago, # ^ | ← Rev. 2 →   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.
•  » » time complexity of 'int a={0}' = 200001, and the number of test cases = 10000 so total complexity of your code = 10000 * 200001 > 2 seconds.
•  » » » Got it. I cleared the pretests and didn't think along this line of thought.
•  » » » 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!
•  » » » » It's guaranteed that the sum of $n$ of all tests is at most $2e5$, so it's actually $2e5 \cdot \log(2e5)$.
•  » » » » » Got it. Thank you. I will read the question carefully from next time.
 » 5 months ago, # | ← Rev. 2 →   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.
•  » » that is true. but solution with binary search is easier to understand and write, so we put it in tutorial
•  » » Yes, Please do write in C++.
 » 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?
•  » » 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).
•  » » » Got it. thanks!
•  » » Make sure to read your testcase results. Testcase 3 says:wrong output format Expected integer, but "1e+006" found
•  » » » yeah my bad. will take care from now onwards.
 » LinkCan anyone tell me whats wrong in this logic?
 » 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
•  » » if(x-a<0||y-a<0) there must be y-b<0, i think
•  » » » well thats really stupid of me. howcome i mixed up a and b. damn that cost me a a couple of hundreds in rank
 » 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.
 » Am I the only one who solved D without noticing that the end of the vacation coincides with the end of some month? 81543406
•  » » same
•  » » » 5 months ago, # ^ | ← Rev. 3 →   Can you pleas tell me what is wrong in my submission?? https://codeforces.com/contest/1358/submission/81671202
 » Please ,Remove the picture of problem D .its look like ……….
 » Very good explanation for problem C.
 » Memes in problem statement would have been nice!
•  » » thanks
 » 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.
 » 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 :(
•  » » The for loop runs up to 2e5 times, for every one of the 10000 testcases.
 » 5 months ago, # | ← Rev. 3 →   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.
•  » » 5 months ago, # ^ | ← Rev. 3 →   Also, one of the optimal answers will 2 3 4 5 1 2 3 4 1 2 3 1 2 1 2 3 4
•  » » 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.
•  » » » 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?
•  » » » » Maybe you missed that we see rightmost optimal segment in proof?
•  » » » » » I'm sorry but what difference does that make?
•  » » » » » » If we shift segment to right, sum will strictly decrease
•  » » » » » » » 5 months ago, # ^ | ← Rev. 3 →   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?
•  » » » » » » » » 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
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » » » » » 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 :(
 » Is it a problem — the last line in Excel? Ctrl+↓, and here it is!For the last column, use Ctrl+→. •  » » YOU are hired!
•  » » » •  » » This man was Albert Einstein.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   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... » 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   I think, authors and coordinator responsible for fast publishing
 » 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?
•  » » Do you mean F? And in that case, you have to print the number of pref operations, not the total.
•  » » » Thanks so much! That's so tricky.
 » Why isn't Ternary search applicable in D? Isn't the function a point wise supremum of affine and hence convex functions?
 » Those grannies are yelling "Go Corona Go"
 » 5 months ago, # | ← Rev. 2 →   D can also be solved in O(n)Link to my submission:https://codeforces.com/contest/1358/submission/81557479
•  » » please explain the logic also..
•  » » » 2 pointers instead of binary search
•  » » » 5 months ago, # ^ | ← Rev. 3 →   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..
 » anyone plz help me to understand problem B ? thanks
 » 5 months ago, # | ← Rev. 2 →   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
 » 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.
•  » » 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)
•  » » » Nice, i wanted some math/combinatorics solution for it, but yes the same idea as editorial can be used here, thank you.
 » 5 months ago, # | ← Rev. 3 →   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.
•  » » 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
•  » » » 5 months ago, # ^ | ← Rev. 2 →   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..
•  » » » I also solved the same way.
•  » » if it is a rectangle instead of a square?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   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)
•  » » » » very thanks！I get it.
•  » » thanks bro for this great visualization but sorry that I am still unable to get how does that make us reach to (c — a) * (d — b) result
•  » » » 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.
•  » » » » thanks man i got it.great help
 » 5 months ago, # | ← Rev. 2 →   ilian04 The solution to problem C: Celex Update contains a (q--) instead of a (t--).
 » So is this balanced ? I mean no graphs and no data structures ?
•  » » Don't forget that 13 problems were redjected
 » 5 months ago, # | ← Rev. 2 →   typo in D di=a1(a1+z)2+...+ai(ai+1)2 that must be a1(a1+1) ilian04
 » https://codeforces.com/contest/1358/submission/81540947 this o(n^2) solution passed D
 »
 » 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
 » 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
 » 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
 » Can anyone suggest more observation-based problems like Problem C?Thank You.
 » » C. There are six possible unique sums(on the diagram). But why is the answer 5?(2*2+1)
•  » » 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.
 » 5 months ago, # | ← Rev. 3 →   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?
•  » » 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
 » 5 months ago, # | ← Rev. 2 →   .deleted
 » Can any one tell me why my rating has gone down even though I solved one problem?
•  » » 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
 » Great Contest!
 » 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
 » 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!
•  » » 5 months ago, # ^ | ← Rev. 2 →   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
•  » » » then how is (c — a) * (d — b) giving unique paths please explain? i think I am a bit weak at p&c
 » 5 months ago, # | ← Rev. 29 →   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 > b) { //if b > b, 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, y = b; if (a > a) swap (a, a); while (true) { if (x < y) swap (x, y); if (y == 0) { cout << "IMPOSSIBLE" << endl; return 0; } if (a == y) { if ((x - a) % y != 0 || x < a) cout << "IMPOSSIBLE" << endl; else cout << "BIG" << endl << ti + (x - a) / y << endl; return 0; } ti += x / y; x -= x / y * y; } // cout << "WTF " << endl; return 0; } Submission 81693390
•  » » Please hide the code inside spoiler tag.
•  » » HackerDemon 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.
•  » » » No problem, I just updated my comments. I'm glad if it helps. ^_^
 » 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.
 » In the solution of the problem C, there should be while(t--) instead of while(q--). Did anyone notice that?
 » can anyone explain me the why complexity of B problem is O(nlogn)
•  » » 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))
•  » » also if u use binary search then it is nlog(n)+log(n)=nlog(n)
 » I really liked the idea of using memes:-)
 » 5 months ago, # | ← Rev. 2 →   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?
 » 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
•  » » The same here with me? How this (x2 — x1) * (y2 — y1) is giving unique no. of path for different sums?
•  » » 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
•  » » » satisfactory
 » That's an interesting editorial and well explained
 » 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?
 » I think we could make memes out of these memes.
 » https://codeforces.com/contest/1358/submission/81580601 why is it showing TLE i am using a prefix array but it is showing TLE
•  » » 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.
 » Why i am getting TLE in B with this approach : https://codeforces.com/contest/1358/submission/81577715pls help:)
•  » » 5 months ago, # ^ | ← Rev. 3 →   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.
 » ilian04 In third solution there would be t-- in while loop instead of q--. Thank You
 » amazing contest! questions were interesting to solve
 » 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
•  » » 5 months ago, # ^ | ← Rev. 3 →   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.
•  » » » thanks
 » I just FUCKING don't understand what does the picture mean in D.funny mud pee
•  » » +1
•  » » I declare that it's only my personal attitude.Someone is saving others' lives, while someone is just slandering.
•  » » » I think that controversial pictures like this shouldn't appear
•  » » » It seems that a large number of people disagree with what Chinese people have done.清者自清
•  » » 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?
•  » » +1
 » 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); } 
•  » » Could somebody please tell why it's down voted so much?NOW ITS SUBMITTED https://codeforces.com/contest/1358/submission/81641980
 » 5 months ago, # | ← Rev. 3 →   nmsl •  » » How made winds, I love it :)
•  » » Never mind the scandal and liber❥❥❥❥❥
•  » » 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!
•  » » » Nah ur not...
 » I would like to thank 300iq for removing the pictures.
•  » » They should write a blog apologizing for it.
•  » » » Don't be so angry.Maybe they just want to joke.I think removing it is proper enough.
•  » » » » 犯我中华者,虽远必诛!
•  » » » » » Awww man, don't be too serious about this, it'll only intensify the conflict.
•  » » » » 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.
•  » » » » » 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.
•  » » » » » » Yeah, I agree. It's much better to suggest our opinions in a calm way instead of propogating meaningless slogans.
•  » » indeed
 » 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)
•  » » Should have made x long long... Java is way better for debugging lol.
 » can someone explain approach of problem D using simple words, I am unable to understand the editorial...please help
 » 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++.
•  » » Should have made x long long... Java is way better for debugging lol.
 » $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$
•  » » 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.
•  » » » 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).
•  » » » » testers said that is "hard realization" and we made problem simplier
 » 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.
•  » » It was "Nahuw" (it isn't joke). In Russian, it sounds like a swear word, and even "Wuhan" in reverse)
 » 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?
 » Hey, why isn't the path 1+3+5+8+13 taken into consideration in Problem C ?
•  » » Because it has the same sum as the path 1+2+5+9+13.
 » 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?
 » 5 months ago, # | ← Rev. 3 →   The D can be solved in O(n), I think, just by using something like the inchworm. -81607685
 » i think C is more easier than B.. Though C some tricky but easy ❤By applying distance law (without square)+1 ; ****
•  » » (without square root)
 » In case anyone need Detail explanation for D Here
 » 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 == B) puts("SMALL\n0\n"); else puts("IMPOSSIBLE"); return 0; } if (N == 2) { if (B == B) return puts("IMPOSSIBLE"), 0; while (1) { // printf("(%lld, %lld)\n", B, B); if (B > B) std::swap(B, B), Ans[++C] = -1; if (A == B) { LL diff = B - A; if (diff < 0 || diff % B != 0) return puts("IMPOSSIBLE"), 0; Ans[++C] = diff / B; break; } if (A == B) { LL diff = B - A; if (diff < 0 || diff % B != 0) return puts("IMPOSSIBLE"), 0; Ans[++C] = diff / B; Ans[++C] = -1; break; } if (B % B == 0) return puts("IMPOSSIBLE"), 0; Ans[++C] = B / B; B %= B; } 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 == B[N]) return puts("IMPOSSIBLE"), 0; if (B > 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; } 
•  » » You can use spoiler to show your code better. Spoilerowo
•  » » » Ah, yes, thanks.
•  » » » SpoilerNice!!
•  » » https://codeforces.com/contest/1358/submission/81676727 my code is shorter, because most logic is consistant.
•  » » orz. You solved it in the contest.
•  » » » Nah, urs' better. stO qfhy Orz.
 » how u gyies make questions so easy in editorial section.how to think this way easy and clear approach. really these editorials are amazing.
 » I realised that my proof of D was wrong. The proof in the editorial is very nice indeed!
 » Solution of 3rd............ so much small.
 » 5 months ago, # | ← Rev. 6 →   [Deleted]
 » 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!
 » 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?
 » Can someone please explain the two pointer approach for problem D?
•  » » This code might be helpful. https://codeforces.com/contest/1358/submission/81562536
 » I can't seem to find the error in my solution so if anyone can spot it: https://codeforces.com/contest/1358/submission/81631720
•  » » 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   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?