### RDDCCD's blog

By RDDCCD, history, 2 months ago, A. Beautiful Sequence

Hint
Tutorial
Solution

B. Candies

Hint
Tutorial
Solution

C.Make It Permutation

Hint 1
Hint 2
Tutorial
Solution

D.Climbing the Tree

Hint
Tutorial
Solution

E.Monsters

Hint 1
Hint 2
Tutorial
Solution

F.M-tree

Hint 1
Hint 2
Tutorial
Solution

G. The Maximum Prefix

Hint
Tutorial
Solution

H.Last Number

Hint
Tutorial
Solution 1(floor sum)
Solution 2(fibonacci)  Comments (99)
 » Wow. Tutorial was released even before system testing was over. Nice contest overall <3
 » super fast editorial. Thanks!
 » well prepared !
 » dp for C?
•  » » it is possible without dp also link
 » Wow! . Very Fast . Excellent Contest . Jiangly is new No. 1 :)
 » OMG!Jiangly rk 1!
•  » » Yeah! He might cross 4000 soon
 » Jiangly is very cool
 » The announcement has disappeared?
•  » »
 » 2 months ago, # | ← Rev. 2 →   Problem F is basically a generalization of 1705E - Mark and Professor Koro. I described a segment tree-free solution here that can easily be generalized to this problem.
•  » » Thanks for sharing the solution. It is really elegant.
•  » » 2 months ago, # ^ | ← Rev. 2 →   Bro, can you help me debug my code... I cannot find what's wrong in my approach for the problem E. My submission
•  » » https://codeforces.com/contest/1810/submission/200562761generalized map implementation for F of this round just in case someone wants to take a look
 » 2 months ago, # | ← Rev. 2 →   Can someone please help me with problem C My approach was to find the upper bound for each value and calculating values required to be removed and added using it Code
•  » » work with lower bound
•  » » » Could you please help me with a tc where this might fail. Or why does this fail.Thank you for your time
•  » » 1 2 813259240 924953903 21 100 run this.... 
•  » » » Thank you so much bro. I multiplied insert twice :((
 » Well prepared for the contest .
 » 2 months ago, # | ← Rev. 4 →   Can anyone help me with my code in problem C https://codeforces.com/contest/1810/submission/200013025
 » Nice problems and fast editorial.
 » In problem E, how do they come to conclusion that |S(u′)|>2|S(u)|?
•  » » If $u'$ can reach any vertex in $S(u)$ then it can reach all vertices $v$ in $S(u)$. Before reaching $v$, $|S(u')| > |S(u)|$ and after visiting all of $S(u)$, $|S(u')| > 2|S(u)|$
•  » » » It has to visit all of $S(u)$ angin, why eventually one vertex can not be visited more than $log(n)$ times
•  » » » » Lets say $v$ is visited by $u_1,u_2,...,u_i$, then $|S(u_i)|>2^i|S(v)|$.
•  » » » Also, the reason why $|S(u')| > |S(u)|$ before reaching $v$ is because there must be some $x$ which we could not reach from $u$ (because $a_x > |S(u)|$) and $x$ was in $E(S(u))$ i.e $x$ was one of the neighbour of $S(u)$.
•  » » » » Are you saying that $|S(u')| > |S(u)|$ because we reach this $x$ that is not in $S(u)$ before we reach any vertex of $S(u)$? And reaching such an $x$ would require the above condition. But is it not possible that $x$ could only be reached after visiting some vertices in $S(u)$. Or am I understanding it wrong? Could you please explain
•  » » » » » To clear up your confusion, I will list two lemmas, which would help you understand my above claim if you put them together. If you can reach some vertex of $S(u)$ from $u'$, then you can reach all the vertices in $S(u)$ from $u'$. If there exists some vertex $x$ with smallest $a_x$ which is not part of $S(u)$ and this vertex $x$ can be reached by $u'$, it means $|S(u')|$ before defeating $x$ should be at least $a_x$.
•  » » » » » » Right, I understand these two lemmas. Now from what I get, you can get to $x$ from $u'$ before touching any vertices of $S(u)$, which gives you $|S(u')| > |S(u)|$ by Lemma-2 Then you touch all the vertices of $S(u)$ by Lemma-1 since you can reach $v$ from $u$ and this gives you the extra $|S(u)|$ in $|S(u')|$. However I still don't get why we can reach $x$ before touching any of the vertices in $S(u)$ necessarily. Could you explain that?
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   Oh, now I get what your confusion is. We will always reach x before reaching any vertices in $S(u)$ because these vertices form the boundary of $S(u)$. We cannot reach an internal vertex without going through the boundary.Example:- let's say the minimum $a_x$ value of a vertex $x$ which is not reachable from $u$ is $10$ and assume that $|S(u)|$ is $6$. Then it is impossible to reach any vertex in $|S(u)|$ without passing through a vertex with $a_i$ less than $10$.Also, we assume that the answer exists. Meaning that we can defeat all the monsters.
•  » » » » » » » » Thanks!!
 » In problem B, "Then consider how the binary representation changes..." — I mean, all of a sudden people have to consider binary representation of a number? :) I find this kind of problem a bit weird. I know that the idea and solution is nice and neat but when you solve it you kind of expect more general approaches to work here like backtracking or some easy calculations but this kind of reasoning seem to be not suitable for problem B. I solved it exactly the way it is described in the solution, but it was just kind of a luck.
•  » » When $n$ is odd, either one of $\frac{n + 1}{2}$ or $\frac{n - 1}{2}$ is odd. You can perform the operation that makes $n$ remain in odd, eventually $n$ will end at $1$.
•  » » » yeah, that's how I did it too
•  » » » Oh, you mean (n+1)/2 or (n−1)/2 is literally the recursive binary representation of a number :)
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   YES, if you figure out the binary representation of those number, you will clear see op 1 and 2 are related in 0,1 bit. You can see my code [submission:https://codeforces.com/contest/1810/submission/200007742]
 » is there any reason as to why we do not consider the 40 spell limit in the 2nd question?
•  » » 2 months ago, # ^ | ← Rev. 2 →   Each operation you might want to do increases the number of significant bits in the number's binary representation. As the maximum value of $n$ we might want is $10^9$ which has only $31$ bits, we would need at most $31$ operations (+/-1 if my logic has some off-by-one error) which is clearly less than $40$.
 » Can anyone help me in my solution for C. https://codeforces.com/contest/1810/submission/200018474. Spoiler I removed the same elements adding their cost to the Ans and saved the unique elements in temp. Then I iterated over every element and found the minimum cost for insertion if adjacent elements are not same and removing all elements from that index. In the end I minimized the Ans between keeping 1 and removing all elements and adding the missing elements from 1 to the minimum element.
•  » » sort the input array first
 » 2 months ago, # | ← Rev. 6 →   Cheers to authors. Overall Great round. I wanted to share my opinion on problem D.Problem D is the little bit bad for C++ users compared to python. There is a formula to find number of days require to reach height 'h'. But instead of using formula, if we use BINARY SEARCH , then there is very stupid long long overflow. Sincere request to authors to avoid these kind of problems which are language specific. In this problem, using binary search in c++ is 10x more difficult than using python. RDDCCDBelow is my implementation in c++, EVEN AFTER USING LONG LONG, I am getting overflow. is there any way to overcome this ? // "ll" stands for long long ll getDays(ll h, ll a , ll b) { // returns minimum number of days required to reach height 'h' ll l = 1LL , r = h; while(l < r) { ll m = (l+r)/2LL; ll climb = (m-1LL) * (a-b) + a; // this line gets overflow if(climb >= h) { r = m; } else { l = m+1LL; } } return l; } 
•  » » One possible way is to set $r = \lceil \frac{h}{a-b} \rceil$ I think. Or using int128. You can also detect whether overflow occurs, like checking (climb > (8e18/(a-b)). If it occurs, just set r = m.
•  » » » sure, thanks, will give it try.
•  » » » » Yes , I also got the same signed integer overflow and int128 doesn't work in c++17 so , r=h/(a-b)+1 works fine.
•  » » 2 months ago, # ^ | ← Rev. 2 →   There exists 128-bit integer in C++ which is big enough since you aren't crossing ~$10^{27}$ and 128-bit integer can hold numbers up to ~$10^{38}$.
•  » » 2 months ago, # ^ | ← Rev. 2 →   You can also use the thing I used to get AC : 200027884. This prevents overflow. I got this idea from ' binary search — edu section ' of codeforces. codebool ok(int mid,int a,int b,int H){// if on mid th day, H height can be achieved? int h=mid*a; h-=(mid-1)*b; return h>=H; } int fun(int a,int b,int H){ int l=0,r=1; while(!ok(r,a,b,H))r=r<<1; while(r-l>1){ int mid=(l+r)>>1; if(ok(mid,a,b,H))r=mid; else l=mid; } return r; } 
•  » » 2 months ago, # ^ | ← Rev. 2 →   I faced a similar problem, so I just decided to use math to compute the #of days and it got AC. Not until I had like 10 WA's tho lol (mostly b/c i kept changing the bounds of my binary search)
 » Great round, thank you problemsetters!
 » The proof of the time complexity of E is quite an impressive part of this problem. I like it very much. (I came up with this solution in the last 20 minutes, but I thought that was $O(n^2log\ n)$ and lost the chance for a nice rating change. T_T)ABCD are a little too easy, considering the difficulty difference between D and E. I was somehow slower on ABCD than usual, and then my rank fell down a lot.Anyway, a nice contest. Really enjoyed it.
•  » » the proof is similar to tree-dsu, basically we can merge sets from small to large and our complexity will stay nlogn, something like that.
•  » » » Right. In this problem it's easy to find we're merging sets, but the fact that $\vert S(u') \vert \gt \vert S(u) \vert$ before adding vertex $v$ , is not that obvious, I think.
 » 2 months ago, # | ← Rev. 2 →   200033270 I am getting the wrong answer in test case 7. I think there is some overflow error, but I cannot get it. I am using long long everywhere still. It will be helpful if somebody can find out what I am doing wrong. Thanks in advance.
 » 2 months ago, # | ← Rev. 2 →   Today's Codeforces contest crossed the mark of 200 million submissions, what a coincidence! Congratulations!
•  » » May be 200 million submissions?
 » In problem D, the tutorial and the solution use different formulas to compute n, given h, a and b. When I tried, the tutorial formula gives Wrong Answer on Test Case 7 or something. Can someone please help me understand how to arrive at the formula given in the solution code? Also, please confirm if the tutorial formula is wrong. Thanks in advance :)
•  » » 2 months ago, # ^ | ← Rev. 2 →   It is correct,see my code there.
•  » » They are actually the same, based on the fact that $\lceil \frac{x}{y} \rceil = \lfloor \frac{x+y-1}{y} \rfloor$.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Thank you so much for the proof RDDCCD, and the confirmation oyyfcy. After a lot of struggle, I finally figured out that the issue was with Python's floating point precision in the division of large numbers using the division / operator. The integer division // operation somehow doesn't suffer from the same precision problem. And hence gets Accepted! My Wild guess: " Perhaps the // operator knows ahead of time that the return value is going to be an integer, and hence can allocate all the precision to the integer part of the answer". Using floor or ceil after a / operation is simply not foolproof, because the first division operation will give us imprecise results. Conclusion: Use C++, or just learn more about the limitations and features of your language better.
•  » » » » with c++ also you can get the same thing , may be one case better than yours haha,
•  » » You can check my simple solution 200085618. I hope it helps.
•  » » » Thanks mate. The issue was not with the formula but with the precision of my programming language(Python).
 » 2 months ago, # | ← Rev. 4 →   Can someone tell me what is wrong with the code for problem E? Am i missing something? I am getting WA on TC 3Linkedit1 = why are there so many downvotes? Is asking doubt crime here?
 » 2 months ago, # | ← Rev. 3 →   Problem B is exactly the same as problem D from yesterday's Constructor University contest.D. Mana
 » in problem B , why loop started from 29
•  » » oohh , 10 to the power 9 has 29 bits
 » Thanks for Contest!
 » In Problem C, if we take c = 1, d = 1 and a = [3, 5, 6, 7, 4, 5]. The algorithm in tutorial gives answer 3 while according to me, the answer should be 5 calculated manually. Can someone explain how the minimum cost is 3?
•  » » If you add $1$ and $2$ and remove $5$ the array will be $[1,2,3,5,6,7,4]$, which is a permutation. You added two numbers and removed one number so the total cost is $3$.
•  » » » Thanks for the explanation. I was somehow assuming that it had to be a sorted permutation. I feel silly now.
 » First time ever editorial released this fast. Thanks RDDCCD
 » 2 months ago, # | ← Rev. 2 →   Can someone explain this part in editorial solution for problem C?"But for all the n∈[ai,ai+1), the smaller n has a smaller cost. (see that (m−i)⋅a do not change, and (n−i)⋅b decreases)."Update : I understood later. Thanks.
 » Anyone solved problem C using DP ? If yes please provide the solution.
•  » » solution I didn't name the arrays (rm -- cost to remove all the elements behind, and is -- cost to insert to the current element) dp, but I guess it could be expressed as a dp method
 » For Problem D why is it ll ans1 = max(1LL, (L - b - 1) / (a - b) + 1) , ans2 = max(1LL, (R - b - 1) / (a - b) + 1); and not ll ans1 = max(1LL, ceil((double)(L - a) / (a - b)) + 1) , ans2 = max(1LL, ceil((double)(R - a) / (a - b)) + 1); 
•  » » These two could mean the same thing, but we always prefer to process integers only, because double (float number) has error from its essence.P.S. In my submission 200018265 I usedll nl = max(0LL,l-a)/(a-b) + (max(0LL,l-a)%(a-b)!=0) + 1;ll nh = max(0LL,h-a)/(a-b) + (max(0LL,h-a)%(a-b)!=0) + 1;which might seem more natural
•  » » » Thanks! I changed from ceil to integer division + (if remainder exists) and it passed.
 » 2 months ago, # | ← Rev. 2 →   Here's my solution to E, which I find pretty beautiful too :We'll add vertices one by one by danger increasing, keeping connected components with a dsu. For each component, we remember if we can visit all of it starting from one vertex (say it is good).Initially, all vertices of danger 0 are marked as good.When we add a new vertex, for each of its neighbors (smaller than him), if its component is smaller than the current danger, it becomes bad, since all of its neighbors are stronger than its size. Then we merge, the new component being good if one of the two was.At the end, we just check if only one component is left and if it is good.This gives a $O(nlog(n))$ solution, which is little more to implement than a dsu.
•  » » Thank you for the solution. Much easier to understand.
 » What is $mdash$ doing in code for F?
•  » » That's a format error. Fixed now.
 » Hello I am here to solve problem C using Binary Search. 1. First Step of Binary Search to choose minimum and a maximum of the answer:- we know that we have two operations:- 1. remove an element from array a of length n (c cost per remove) 2. insert from array a of length n (d cost per insert at any position)So, if the array is initially in the permutation form then we need zero operation but if not then we need a maximum operation to convert the array into permutation form by removing all the elements and inserting only one element which is 1 i.e** n*c+d **.This means we need minimum operation zero(0) and maximum operation n*c+d. The second step of the Binary Search approach is to find the bool function:- parameter for bool function -> (array->a,c,d,k) this function will return that is it possible to convert an array 'a' into permutation array in 'k' cost. first, we have to check that many different elements are present in the array because, in the permutation array, no duplicate elements are allowed. let array 'x' contain a different element of the array 'a' in sorted order. So we have to remove the (n-x.size()) element from an array 'a' because no duplicate elements are allowed, which takes cost c*(n-x.size()). and array 'x' must contain 1 element because without one permutation array is not possible. therefore, if x does not contain 1 then we have to insert 1 in the first place which takes cost 'd'. Finally, we come to the last operation of this problem where we have to convert the 'x' array into a permutation array:- we declare a variable 'cnt' which is initialized by one. we traverse in the array 'x' and check if x[i]-cnt>0 if yes then means we have inserted the element in this position to make permutation array till index 'i' or we remove all the from i to n-1 inclusive. we have to update cnt accordingly which statement we choose. Code for bool function :- bool helper(ll n,ll cost,set&s,ll c,ll d){ cost -= (n-s.size())*c; std::vectorans; for(auto i : s){ ans.push_back(i); } if(ans != 1){ ans.insert(ans.begin(),1); cost -= d; } if(cost < 0){ return false; } ll cnt = 1; for(ll i=0;i 0){ ll temp = ans[i]-cnt; ll temp1 = ans.size()-i; if(temp1*c <= cost){ cost -= temp1*c; break; }else if(temp*d <= cost){ cost -= temp*d; cnt += temp+1; }else{ return false; } }else{ cnt += 1; } } return cost >= 0;}My Code for this Solution using Binary Search:- https://codeforces.com/contest/1810/submission/200121687
 » Is it possible to solve problem E with the algorithm for finding bridges online?
 » I am getting WA in TC 4, I don't know why? Can somebody help me? Solution:https://codeforces.com/contest/1810/submission/200348409
 » My codes Why will it overflow?And I don't no what's wrong will my solution.
 » in problem B in the solution of editorial why did they start i from 29.why cant i start it from 31 to 0?
 » How to use binary search for D?
 » It seems that there is a problematic test case in test 2 for E. I received a strange out-of-bounds error and discovered from the exit code that there is a scenario where n equals 3 while u equals 4.
 » I guess using a pairing heap could also pass E because merging is O(logN)
 » Can anyone explain in problem H, how the formula $d_i = n - \lceil\frac{i}{\phi}\rceil + 1$ pops out from $\sum_{j=1}^k{[d_j-j \ge d_k]} + n - d_k + 1 = k$ in the second lemma proof? Is this a known fact and does it have any name on it? You have to at least come up with shape of the formula in order to proceed through the proof further anyway...
•  » » Actually it's: find the rule by making observation, then try to prove it.
•  » » » Alright. Thanks for you reply.
 » 2 months ago, # | ← Rev. 3 →   Can we solve problem F using Huffman Tree? Although they seems similar I still have no idea about that. I can only do it in $O(qnlogn)$.
 » 2 months ago, # | ← Rev. 2 →   In editorial of problem E, v is add into S(u′) again . We are considering only the case when v is add. We would be processing v also when we add it to some E(S(u')). In this case, the condition |S(u′)|>2|S(u)|` might fail.What am I missing?
•  » » Ah, you can try to think in another way: if we only consider adding v to some $S(u)$, it will not exceed $log(n)$ times per vertex. And what happened when we add v to some $S(u)$? We visit all it's neighbors and (possibly) add them to $E(S(u))$. That would not exceed $deg(v)$ times. Overall, it will not exceed $log(n) \cdot \sum{deg(v)} = m log(n)$.
 » Can anyone please tell me in the B.Candies solution why the loop is from 29 to 1 only?
 » Note that in H, $O(N_{max}+T)$ time and space works as well. We sort the queries and simulate the part before $x$. Since the part after $x$ is just an alternating-sign sum and we're adding/removing elements from the sum in 2-pointers style, it's easy to maintain the current sum until the last duplicate element and extend it to all required elements for each query. The only tricky part is implementation since there's some casework based on parity and $O(N_{max})$ space is a lot, I used bitset to denote which elements are duplicated.
 » 46 hours 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; } Can somebody figure out what is wrong with my solution of Problem C. It got failed on testcase 2-7552nd number. 208058723