### RDDCCD's blog

By RDDCCD, history, 15 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)
• +269

| Write comment?
 » 15 months ago, # |   +14 Wow. Tutorial was released even before system testing was over. Nice contest overall <3
 » 15 months ago, # |   +2 well prepared !
 » 15 months ago, # |   +8 Wow! . Very Fast . Excellent Contest . Jiangly is new No. 1 :)
 » 15 months ago, # |   +4 OMG!Jiangly rk 1!
•  » » 15 months ago, # ^ |   0 Yeah! He might cross 4000 soon
 » 15 months ago, # |   +5 The announcement has disappeared?
•  » » 15 months ago, # ^ |   0
 » 15 months ago, # | ← Rev. 2 →   +32 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.
•  » » 15 months ago, # ^ |   +9 Thanks for sharing the solution. It is really elegant.
•  » » 14 months ago, # ^ |   0 https://codeforces.com/contest/1810/submission/200562761generalized map implementation for F of this round just in case someone wants to take a look
 » 15 months ago, # | ← Rev. 2 →   0 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
•  » » 15 months ago, # ^ |   0 work with lower bound
•  » » » 15 months ago, # ^ |   0 Could you please help me with a tc where this might fail. Or why does this fail.Thank you for your time
•  » » 15 months ago, # ^ |   0 1 2 813259240 924953903 21 100 run this.... 
•  » » » 15 months ago, # ^ |   0 Thank you so much bro. I multiplied insert twice :((
 » 15 months ago, # |   +1 Nice problems and fast editorial.
 » 15 months ago, # |   +8 In problem E, how do they come to conclusion that |S(u′)|>2|S(u)|?
•  » » 15 months ago, # ^ |   +33 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)|$
•  » » » 15 months ago, # ^ |   0 It has to visit all of $S(u)$ angin, why eventually one vertex can not be visited more than $log(n)$ times
•  » » » » 15 months ago, # ^ |   +13 Lets say $v$ is visited by $u_1,u_2,...,u_i$, then $|S(u_i)|>2^i|S(v)|$.
•  » » » 15 months ago, # ^ |   +4 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)$.
•  » » » » 14 months ago, # ^ |   0 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
•  » » » » » 14 months ago, # ^ |   0 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$.
•  » » » » » » 14 months ago, # ^ |   0 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?
•  » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » » » » » 14 months ago, # ^ |   +1 Thanks!!
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   +9 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$.
•  » » » 15 months ago, # ^ |   0 yeah, that's how I did it too
 » 15 months ago, # |   0 is there any reason as to why we do not consider the 40 spell limit in the 2nd question?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 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$.
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 sort the input array first
 » 15 months ago, # | ← Rev. 6 →   -72 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; } 
•  » » 15 months ago, # ^ |   +3 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.
•  » » » 15 months ago, # ^ |   0 sure, thanks, will give it try.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 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}$.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 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; } 
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 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)
 » 15 months ago, # |   +10 Great round, thank you problemsetters!
 » 15 months ago, # |   +29 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.
•  » » 15 months ago, # ^ |   0 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.
•  » » » 15 months ago, # ^ |   +1 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.
 » 15 months ago, # | ← Rev. 2 →   0 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.
 » 15 months ago, # | ← Rev. 2 →   +16 Today's Codeforces contest crossed the mark of 200 million submissions, what a coincidence! Congratulations!
•  » » 15 months ago, # ^ |   0 May be 200 million submissions?
 » 15 months ago, # |   +1 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 :)
•  » » 15 months ago, # ^ | ← Rev. 2 →   +1 It is correct,see my code there.
•  » » 15 months ago, # ^ |   +8 They are actually the same, based on the fact that $\lceil \frac{x}{y} \rceil = \lfloor \frac{x+y-1}{y} \rfloor$.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +10 Thank you so much for the proof RDDCCD, and the confirmation HELLO2024. 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.
•  » » » » 15 months ago, # ^ |   +1 with c++ also you can get the same thing , may be one case better than yours haha,
•  » » 15 months ago, # ^ |   +1 You can check my simple solution 200085618. I hope it helps.
•  » » » 15 months ago, # ^ |   0 Thanks mate. The issue was not with the formula but with the precision of my programming language(Python).
 » 15 months ago, # | ← Rev. 3 →   0 Problem B is exactly the same as problem D from yesterday's Constructor University contest.D. Mana
 » 15 months ago, # |   0 in problem B , why loop started from 29
•  » » 15 months ago, # ^ |   +1 oohh , 10 to the power 9 has 29 bits
 » 15 months ago, # |   0 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?
•  » » 15 months ago, # ^ |   0 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$.
 » 15 months ago, # |   +6 First time ever editorial released this fast. Thanks RDDCCD
 » 15 months ago, # |   0 Anyone solved problem C using DP ? If yes please provide the solution.
•  » » 15 months ago, # ^ |   0 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
 » 15 months ago, # |   0 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); 
•  » » 15 months ago, # ^ |   0 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
 » 15 months ago, # | ← Rev. 2 →   +40 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.
•  » » 15 months ago, # ^ |   0 Thank you for the solution. Much easier to understand.
 » 15 months ago, # |   0 What is $mdash$ doing in code for F?
•  » » 15 months ago, # ^ |   +8 That's a format error. Fixed now.
 » 15 months ago, # |   +10 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[0] != 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
 » 15 months ago, # |   0 Is it possible to solve problem E with the algorithm for finding bridges online?
•  » » 10 months ago, # ^ |   0 i think impossible
 » 15 months ago, # |   0 I am getting WA in TC 4, I don't know why? Can somebody help me? Solution:https://codeforces.com/contest/1810/submission/200348409
 » 15 months ago, # |   0 My codes Why will it overflow?And I don't no what's wrong will my solution.
 » 14 months ago, # |   0 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...
•  » » 14 months ago, # ^ |   +8 Actually it's: find the rule by making observation, then try to prove it.
•  » » » 14 months ago, # ^ |   0 Alright. Thanks for you reply.
 » 14 months ago, # | ← Rev. 3 →   0 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)$.
 » 14 months ago, # | ← Rev. 2 →   0 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?
•  » » 14 months ago, # ^ |   0 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)$.
 » 14 months ago, # |   +10 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.
 » 12 months ago, # |   0 What kind of test is testcase 4 : [5189th token] in problem E? (wrong answer expected YES, found NO)
 » 10 months ago, # |   0 In Q2, why only 29....it works for 32 as well but it fails for 64 .... why so ?
 » 6 months ago, # | ← Rev. 2 →   -23 Nice Explanations