### ch_egor's blog

By ch_egor, 21 month(s) ago, translation, Thanks for the participation!

1649A - Game was authored by Jeffrey and prepared by DmitryGrigorev

1649B - Game of Ball Passing was authored by low_ and prepared by low_ and DmitryGrigorev

1648A - Weird Sum was authored and prepared by cookiedoth

1648B - Integral Array was authored by grphil and prepared by shishyando

1648C - Tyler and Strings was authored and prepared by Tikhon228

1648D - Serious Business was authored and prepared by ligaydima

1648E - Air Reform was authored and prepared by grphil

1648F - Two Avenues was authored by I_love_myself and prepared by isaf27    Comments (61)
| Write comment?
 » It would also be interesting to see a tutorial on how to recreate test 61 from Div1C (the one that breaks ++ans without taking mod at the end).
•  » » really really curious about this case. I didn't use such algorithm so didn't meet this problem.
•  » » I'm not an author, but if I needed to generate such test, that's how I would do itEssentially you just need to find some group of possible tests such that there exists a test with a needed property and you can calculate an answer in $O(1)$, then you can generate random tests of this type until you find the one that satisfies the condition.For example, in this problem, consider $s =  \times a +  \times b$, $t = s + $. Then it almost works, except the answer is $\binom{a+b}{a}$, which can't be zero. So instead of this $t$, take a string, which is lexicographically previous: $\times (a-1) +  +  + \times b$. Then the answer is $\binom{a+b}{a} - 1$ and now you can generate random $a$ and $b$ until you get answer $0$.Also maybe there is a faster way to find $a$ and $b$ such that $\binom{a+b}{a} = 1$, or maybe there is another type of tests where the formula is easier and you can directly find parameters for it without random generation, but it's not needed here
•  » » » Thanks for the writeup! I've finally got around to trying this approach myself. After five minutes of random generation, the smallest value I got was 114 for a=4706, b=11894. Maybe I should've run it in C++ instead of Python, but 114 is good enough anyway: we can just call prev_permutation 114 times and obtain the test. :)
•  » » » » Since the expected number of random generations is $\frac{mod}{2} \approx 5\times 10^8$, it's definitely better to pick faster language. For example, this code in C++ performs $10^9$ iterations in around 30 seconds in ideone and gives $a = 54993$, $b = 97144$
 » If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.Div 2 Div 1 If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
•  » » This is great! Helped me find why my D submission was failing. Just one line change and AC :_)
•  » » loved it brother
 » Can I ask that why we can prove the statement in Div2B ?
•  » » Consider the $i$ corresponding to maximum $a_i$. By letting $i$ pass the ball to any other person, and these people then pass back to $i$, we can maximize the $i$'s passes. And if even in that case, the passes don't meet his requirement, one ball can definitely not complete the task, and the extra ball we need is the rest passes required. However, if we can use all the passes or even the passes is not enough, we can turn to another person and keep the process, which will make one ball acceptable.
•  » » » Excuse me but can I ask that for the condition when the maximum is not enough, by saying turn to another person,do you mean the the maximun person among all the people that are left after eliminating the first one？ In this case don't we have to prove that the rest of the people still requires the condition that the maximum is not enough？
•  » » » » if $max(a) \times 2 •  » » » » » Now I get it,Thank you so much!  » 21 month(s) ago, # | ← Rev. 2 → In 1D/2F, why you define$dp_i$as the maximum profit for going from$(1,1)$to$(2,i)$, but relax it with$\min$? I'm completely confused about that. Could anyone please provide a further explanation of the$dp_i$qwq •  » » I'm also confused about this place. •  » » Excuse me but when we relax$dp_i$by$dp_j$, maybe we should pay attention to$pref_{1,i}-pref_{1,j}$, or I misunderstand the algorithm?Sorry for my poor English. •  » » » Well, seeing your comment make me completely confused now and discover some problems with my idea, so I deleted it.But I think the$dp_i$may have the similar meaning to the$s_i$, so the$pref_{1,i}-pref_{1,j}$is calculated in the final step? •  » » » » In my opinion, when we relax$dp_i$by$dp_j$, that means we move from$(2,j)$to$(2,i)$, besides$s_i$means moving from$(1,1)$to$(2,i)$, if$dp_i$is similar to$s_i$, then the way we relax$dp_i$maybe only unlocked the segment$[j+1,i]$,but didn't moved from$j$to$i$. Sorry for the parhap incorrect grammars. •  » » » » » From my point of view, in the process of calculating the answer, we take$f_j$into considering, which represents for the correct sum of 3rd floor and the prefix sum of the 2nd floor. So in the$dp$, we should maintain the left side of the segment we passed in the 2nd floor to correctly get the final the$a_{1,i..j}$. •  » » » » » » Oh sorry for my mistake, I forgot the$f_i$! Then your idea to relax$dp_i$may be right. Thank you! •  » » » » » » » Maybe they are right, but I can't be that sure. :(Anyway, thank you for discussion with me! •  » » Yes, you are right. We fixed this mistake, sorry. •  » » » 4 days ago, # ^ | 0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } ojo  » The only case where the resulting string$x$can be lexicographically less than$t$which we will not count, is when it is a prefix of the string$t$but has a shorter length. CMIIW but for this statement in editorial div 2E/1C why do we need to "not count" this case?For example when$x = "abc"$and$t = "abcd"$,$x$is a prefix of$t$and it has a shorter length. But isn't in this case,$x$is lexicographically smaller than$t$? •  » » Maybe you misunderstand the tutorial.By saying "not count", he don't mean that the answer don't include the case, but mean that the algorithm can't take the case into considering. •  » » » Oh I see. Thanks  » I tried to prove problem B during the contest but failed. Until now, I don't know how to prove it. Can anyone help me, please.  » Plz show editorial code for Problem C (Div.2) •  » » 21 month(s) ago, # ^ | ← Rev. 2 → Here is my submission which is a little difference to the editorial, but uses the same ideas. 148564648 •  » » » Thanks!  » in questions : "Game of Ball Passing" who can prove that 2 * max(a) <= sum(a) why answer is 1 •  » » 21 month(s) ago, # ^ | ← Rev. 2 → Consider this expression as max <= sum — max. Now it's obvious for an optimal solution, if we can complete the passes of the player with max passes, all other players' passes have been completed by that time. So consider the following pattern of passes:____ M ____ M ____ M ____ M ......... ____ MThe above pattern represents the order in which the ball was passed. Here, M represents the player who made max passes. Now obviously, we will want to have atleast one player make a pass between two consecutive passes by the player M. And we can notice that there are max blanks available to fill in. Also, the value sum-max represents the total number of passes made apart from the player with max passes. Therefore, we can say that if remaining passes(sum-max) >= number of blanks(max), then all our blanks can be filled easily and the entire pattern will represent a single chain of passes. However, if sum-max < max, then some blanks will remain empty, which would mean that the chain of passes broke at that point, and we needed an extra ball to begin a new chain. I hope you understood the point. Try working out some examples by this logic and you'll get the logic •  » » 21 month(s) ago, # ^ | ← Rev. 2 → Actually, I did not know how to prove, but my gut feeling told that answer is either max(1,2*mx-s) or 0. F****** adhock  » 21 month(s) ago, # | ← Rev. 2 → Remember that$O(10^{6}\sqrt{10^{6}})+10^{6} * log(10^{6}))$gets AC in 2 seconds with$C++20$! https://codeforces.com/contest/1648/submission/148611843 •  » » Are you sure ? mine didn't get accepted •  » » » 21 month(s) ago, # ^ | ← Rev. 2 → Don't use push_back for storing the non-duplicate numbers which are in your array because sometimes it may leed to$O(n)$in each push_back, Write a vector of size n like this$vector a(n)$and read input and then use this code : sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); This will store the non-duplicate numbers in a good time. •  » » » My submission : 150868540 Which has$O(C√\overline{C})$doesn't work too, can anyone explain why it fails? Or is it meant to fail since it only accepts$O(ClogC)$?  » 21 month(s) ago, # | ← Rev. 2 → getting tle on test 9 for problem E help https://codeforces.com/contest/1649/submission/148661424  » For problem B(div2), how to prove "If max(a)⋅2≤sum(a), we can always prove that we can only use one ball."? •  » »  » I'm trying to understand the editorial to div1D, could someone explain to me what the term 'relax' means? More specifically, I'd like more detail at:"The calculation of dp is as follows: for all i look through each segment, which ends at i, and relax$dp[i]$with$\max_{l−1≤j
 » 21 month(s) ago, # | ← Rev. 2 →   Testcases of div2 D seems to be weak, $\mathcal{O}(n\sqrt C)$ combined with randomization could get AcceptedCould anyone provide a hack? I can't find one myself. Thanks a lot
 » The tutorial 1D/2F is confusing. For example, why it write $dp[i]+f[j]+k$ at first line last part, then relax the answer by $dp[i]+f[j]-k$?
•  » » And when we relax the overall answer, how can we get the $k$? Besides both $i$ and $j$ are uncertain.
 » in D1 D/D2 F, I understood the above part , but after calculating all the DP,in last part editorial says "So we can bruteforce the rightmost segment in our answer and relax the overall answer with $maxl≤i≤j≤r$ $dp[i]+f[j]−k$."How do we calculate $maxl≤i≤j≤r$ $dp[i]+f[j]−k$without making it O(n^2) with all values of $i<=j$ $pair(i,j)$
•  » » Not sure if you figured it out. I finally understood by reading other's submission (https://codeforces.com/contest/1648/submission/148574211).Let's state the sub-problem this way: given two arrays $a$ and $b$, we are to answer queries $(L,R)$ with $max_{L<=i<=j<=R}{a_i+b_j}$.Suppose we already have a segment tree, and on each tree node (corresponding to interval $[l,r]$), we maintain three values: $maxa$ (the maximum of $a$ in this interval), $maxb$ (the maximum of $b$ in this interval), $max$ ($max_{l<=i<=j<=r}{a_i+b_j}$). $maxa$ and $maxb$ can be calculated straightforwardly.We will come to $max$ later.Now let's consider how to answer queries, and this is the tricky part. It's using the property of the recursion. In the example below, we are answering the query $[0,6]$ on the given tree. Boxes next to the tree node mean the interval, green means it's not matching the whole interval on the node, and red means it is matching. You can see we process, in order, $[0,3]$, $[3,5]$, $[5,6]$. So we can maintain a running variable, of the maximum values of $maxa$ seen in the nodes we already processed. The pseudocode is: void query( int c /*index*/, int cl, int cr, /*the interval of the node*/ int l, int r /*the interval to query*/ int& runningMaxa, int& result ) { if (cl + 1 == cr || (l == cl && r == cr)) { result = max(result, v[c].max); result = max(result, runningMaxa + v[c].maxb); runningMaxa = max(runningMaxa, v[c].maxa); return; } int mid = (cl + cr) / 2; if (l < mid) { query(c * 2, cl, mid, l, min(r, mid), runningMaxa, result); } if (r > mid) { query(c * 2 + 1, mid, cr, max(l, mid), r, runningMaxa, result); } } When we are at node $[3,5]$, at this moment, $runningMaxa$ is the maximum of $a$ in $[0,3]$. So the above logic give us $max_{0<=i<=j<=3}{a_i+b_j}$, $max_{3<=i<=j<=5}{a_i+b_j}$, and finally $max_{0<=i<=3, 3<=j<=5}{a_i+b_j}$. You can see it's exhaustive for all possible pairs. And for maintenance of $max$ on nodes, you just do the same as querying when propagating from child to parent.
 » Can someone provide a proof of how Div 2 D has time complexity of C log C according to editorial?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   For every $r$ you check each $y \leq \frac{c}{r}$. In other words you do at most $\frac{c}{1} + \frac{c}{2}+\cdots+\frac{c}{c} = c\cdot h_c$ iterations. $h_c$ is the harmonic series. Search it up, it's a very important series which is almost equal to $\log c$ as $c$ grows large.
 » Can someone explain why I am getting TLE in div2 D prob https://codeforces.com/contest/1649/submission/148733037
•  » » Don't reassign the whole arrays prefix, exist in the test cases. That's $t\cdot 2 \cdot 10^6$ operations. That's why there is a bound on $C$.
•  » » » Thanks. The changes I did were removed  memset(prefix , 0 , sizeof prefix);  and did prefix = 0; But it will still give TLE. I then made int exist[1000000+1]; to bool exist[1000000+1]; which passed.I still don't understand why changing exist from int to bool got me AC.I know bool takes less memory and is faster than int, but is the difference significant enough to give TLE??
 » One interesting approach & implementation to Div1C/Div2E without segment tree or fenwick tree, using PBDS We don't need to do anything for repetition of elements, we can simply compute the answer considering every number to be unique. What I mean is let's say we want to permute 1 2 2 2 3 3, we can consider this as 1 2a 2b 2c 3a 3b, then once we have permuted which is 6!, we can then divide the answer by factorial of the repetitions, so at every step we need not bother about it and we can do this step just once at the end. So now at any index i in b[i], we will see how many smaller elements we have, and what is the count of same elements. for smaller elements we can place any one from the options, and permute the rest array. and for equal elements we can select any one and find the answer from the next index, this can be done using pbds and for any element we need to know count of elements smaller than it.Here is my code for the same, you can reply if you want any clarification: 148711861
 » In the problem integral array how can i check for the existence of x in constant time ?
•  » » It is done by considering array $cnt_x$ — the amount of occurrences of $x$ in $a$, and prefix sums for that array. By using prefix sums.
•  » » » I'm kind of a noob here, so how can I do that using prefix sum ?
•  » » » » We create an array named sum, and let each $sum_i=sum_{i-1}+cnt_i$, then this is prefix sum.for integers $i  » The editorial of 1F said It is possible to recalculate this segment tree with$O(n+k)$updates during the dfs tree traversal. But I don't understand it. Can someone tell me how to implement this? Thanks a lot. •  » » 21 month(s) ago, # ^ | ← Rev. 2 → Now I have understood it and got accepted.Its main idea is, we maintain the number of chains that cover$e_2$but not cover$e_1$(then we can calculate the answer for$e_1$and$e_2$since we know$c_{e_1}$and$c_{e_2}$), and we only need to make sure that this value is correct for$e_1$which$h_{e_1}=h_{e_2}$. So we can show that for some chain there is only$O(1)e_2$that will update the segment tree.The Russian editorial has explained the details of how we can find these edges that will update the segment tree. If you are good at Russian or you have a nice translator, I advise you to read the Russian editorial. XDThank isaf27 very much for his guidance.  » Is there anyone accepted 1D by divide and conquer and minimal path? The complexity is$O(n\log^2n)\$.
•  » » What do you mean by "minimal path"?
 » 21 month(s) ago, # | ← Rev. 2 →   https://codeforces.com/contest/1648/submission/150657004 Why doesn't this work? I understand that time complexity is worse than editorial, but I probably would've been able to figure that out if I TLE'd; instead, it's a WA on 2933rd token and I have no idea why (for TC 3 too). Isn't this identical logic to editorial, just using sets instead of a precalc array? edit: nvm, me being a noob in c++