Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### Imakf's blog

By Imakf, history, 5 weeks ago, 1890A - Doremy's Paint 3

idea: Cocoly1990

Solution
Code

1890B - Qingshan Loves Strings

idea: Imakf

Solution
Code

1889A - Qingshan Loves Strings 2

idea: Imakf

Solution
Code

1889B - Doremy's Connecting Plan

idea: Cocoly1990

Solution
Code

1889C2 - Doremy's Drying Plan (Hard Version)

idea: waaitg, Imakf

Easy Solution
Hard Solution
Code

1889D - Game of Stacks

idea: waaitg

Solution
Code

1889E - Doremy's Swapping Trees

idea: waaitg

Solution
Code

1889F - Doremy's Average Tree

idea: waaitg, Imakf

Solution
Code Tutorial of Codeforces Round 906 (Div. 1) Tutorial of Codeforces Round 906 (Div. 2)  Comments (84)
 » i love solving observation problems like c , i just tried some cases and came up with the soluion .
•  » » Your implementation for c is very straightforward,can you explain me the approach?
•  » » » I just checked for the extreme ends of string and if one end is 1 and other is 0 or vice versa then that means they are in correct position and we can forget about them , now we will have some new extreme points if the extreme points are 0 and 0 then it means we have to do something, so inserting 0 1 to last will help us and again after inserting we can remove the extreme characters, same for 1 1 but this time insert 0 1 at the beginning. I hope I was able to convey my approach
•  » » but i tried many cases without caming up a solution:\
•  » » » deque is a good tool
 » Very fast editorial!
 » 5 weeks ago, # | ← Rev. 3 →   Thanks for the super fast editorial and great round ! As usual, here is my advice about the problems I solved :) AThat's one of the best, if not the best, div2 A I've ever seen! It requires a very small idea, have simple implementation, and it's kinda cute. Like even if the idea is simple, it is still somewhat interesting BMaybe a bit too easy for a div2 B ? It's very hard to get the right difficulty for these problems as it should be a little bit harder than A, but not too much harder. The problem is still cool though. CIt felt a bit too easy for div2 C ? Although I liked the problem. DThat's a great problem ! It felt very natural: as there are too much edges, there must be a way to restrict the construction by considering nodes with special properties (such as smallest i). E1Well I somehow have a bug in my implementation but the problem was cool (noticing that there is only O(n) intersections to check if you want to remove some rain that comes from 2 ranges).UPD: funny how my bug was just writtingif () { } else { do x }instead of if () { } else { } do xE2 looks neat too, although I have no clue of how to do it :))Thank you for the round, looking forward to take part in another one
•  » » I felt C was difficult to implement, maybe I suck at implementation and have more admiration for mathematical problems. Back to specialist now :/
 » good contest — good problems, except b was kinda troll (i found it funny though)
 » Div. 1 B and C1 are great! (Maybe also C2 but I didn't solve it) I like the way to optimize the algorithm.
 » I think in C2 segments where dp transition works the same way can only be merged together or a new one may be created at the end. So to support maximums on segments we don't need any data structure, we just need to store these segments and merge them sometimes (there are at most $10$ segments, so we can do it by just storing an array of these segments and deleting elements from it).
 » My mind went blank and did not notice the $i=1$ thing in B so I accidentally solved a more complicated version of the problem where indices of vertices may be arbitrary numbers. I think it is a good exercise if you wish to think about it.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   Is it something like only edges from $(1,2),(1,3),....,(1,n)$ and $(2,3),(3,4),...,(n-1,n)$ edges matter? I solved using this approach, kept on deleting the edge having the least value of $c*i*j - a[i] - a[j]$, and updating the edge values. Or it's even more complicated? Proof of the approachAssume $i < j < k$. Now the condition for $i$ can't form an edge with $k$, but $j$ can form an edge with $k$ : $a[j] + a[k] >= c*j*k$ $c*i*k > a[i] + a[k]$Adding both inequalities, $a[j] - a[i] > c*(j-i)*k$ So for a fixed $i$ and $j$, it's always good to choose least $k$, which will be $k = j + 1$ in this case.
•  » » » I think your approach won't work for the generalized version. In your proof, the condition $a_j - a_i > c\cdot (j-i)\cdot k$ is just necessary but not sufficient. For example, if we have $(5, 1), (6, 25), (7, 1), (8, 25)$, you'll find that we can only connect 6 and 8 in the first step.
 » the problems are so smart that I feel like I'm idiot D: anyway, that is a good round, thanks!
 » In Div2C/Div1A, I didn't understand why would it take at most 300 operations. I'd be grateful if someone can explain.
•  » » We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most 300 operations. Because the problem tells you
•  » » » Technically that doesn't tell you that this particular algorithm produces a solution with at most 300 insertions (or that it terminates at all).I know it's common to meta-game problems like this (I do it myself too) along the lines of: “Hmm, this problem is div1-A, so it can't be too difficult. There must be a solution that is not too hard. I've come up with an approach that gives the right answer for the samples and a few other cases I can think of, so it's probably the correct algorithm, so I'll just submit it and hope the pretests warn me if it's wrong.”This often works, but it's not the same as proving that it works.
•  » » You perform at most one insertion per character originally in the string
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   The clue is in this sentence: “This operation is actually equivalent to moving the last 1 to the front or moving the first 0 to the end.”The algorithm can be summed up as: 0s1 → s 1s0 → s 0s0 → 0s001 (append "01") → s00 (apply rule 1) 1s1 → 011s1 (prepend "01") → 11s (apply rule 1) The problem is that the third and fourth rule, even after expanding them as I did above, do not reduce the problem size. This raises the question if the algorithm terminates at all, and if so, how many insertions there can be.The key is to observe that the rule 3 effectively does a left rotation (0s0 → s00) and rule 4 a right rotation (1s1 → 11s). Since s contains an equal number of 0s and 1s, you can do at most $|s|/2-1$ rotations before the first and last character are different (example: $s=000001111110$ takes 5 turns), and you can reduce the problem size with rule 1 or 2. This shows that the algorithm does terminate, and you can already infer a quadratic upper bound on the number of insertions.But this can be improved to $\mathcal{O}(N)$ as follows. When you've applied rule 3 $n$ times in a row, then you know that $s$ ends with at least $n$ 0s, and you cannot apply rule 4 until all those zeros have been removed, which can only happen by applying rule 1. This shows that every application of rule 3 and 4 must be paired with an eventual application of rule 1.That's how we know we need at most $|s|/2-1 = 49$ insertions in total.
•  » » » Woowww! You and your explanation are amazing. Thanks a lot. I'd been having headache over this since the contest.
•  » » Because at first point 1) if count of zeroes = count of ones, then only the answer is possible. 2) So if thats not the case no matter how many times you perform the operation its not going to be good string. 3) So they have given at max we can do 300 operations i guess. Correct me if i was wrong!
 » C1 (easy) unlucky for python, same solution accepted in C++ (even a slower version). Yes there were people who solved it, but only 3.
 » I tried my best to came up with a solution for at least 1 problem. I almost solved the 1st Problem. Man i feel so demotivated now !! (:
•  » » It's just beginning my brother. If you remember this day, message me after 6 month. You might be in pupil then inshallah.
 » 5 weeks ago, # | ← Rev. 2 →   In Div2 E1/ Div1 C1 if we take test case 5 3 2 1 4 2 5 2 4 According to editorial [1 4] and [2 5] should not be considered as they intersect and there is no position i which is covered by exactly these two intervals, but the answer is obtained by taking these two segments. Can someone correct me if I am wrong?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   In the "no intersection" case we aren't considering only pairs which don't intersect, but any pairs of segments. Since we don't know if they intersect, we assume they don't and calculate the answer based on that. If those segments did in fact intersect in a way that made the answer larger, it would get counted in the second case anyway.
 » Can someone explain how in problem Div. 1 D the idea for the easy version is extended to the original problem?
 » In Div2E1 editorial, I still haven't figure out how to handle the case when two interval intersect using array or set. Could someone explain for me this case, or it could be nice to see the actual implementation
•  » » You check check my implementation. https://codeforces.com/contest/1890/submission/230287888 It currently runs in O(3*n). But with casework on mx1,mx2 and using the fact from editorial that there are at most n useful intersection. You bring it to O(n)
•  » » » Could you explain this part:  int mx1 = -1, mx2 = -1; rep(j,i,to){ if(sz(rain[j]) == 0) continue; if(j != i){ if(mx2 == -1 || rain[mx2].back() <= rain[j].back()){ mx2 = j; if(mx1 == -1 || rain[mx1].back() <= rain[mx2].back()) swap(mx1,mx2); } } int ct = rain[j].back(); int c2 = pre[min(ct,to)]-pre[j-1]; c2 += pre[max(ct,to)]-pre[i-1]; two = max(two, c2); } 
•  » » » » This part is searching through all intersection of rain starting from i. In the second part of code, I am calculating the answer as number of 2s on intersection part + number of 1 in entire covered part. In the first part I am trying to find the next rain index to search. Among all rain with rightEnd >= to, You only care about the largest two ending points, because all other will always have > 2 intersection. I have stored it as mx1 and mx2. You can ignore the search on mx1 and mx2 if its right end is before "to". In my implementation, I am not ignoring
 » Please someone explain Div2 E1 solution with the code. I couldn’t understand the editorial.
 » Any advice on How to solve problem D using UnionFind and counting the population with DFS? My submission: 230232830I know that it can be solved using PQ, but I have the doubt if it is possible to solve it with this approach
•  » » Take a look at Ticket 17118 from CF Stress for a counter example.
•  » » » Thanks!, can u test with this one? 230397805
 » why does s_i + s_j >= i + j — 1 imply that either s_i >= i and s_j >= j have to be true, why cant s_i >= j and s_j >= i ?
•  » » You say $s_i \geq j$ and $s_j \geq i$.If $i \leq j$, then $s_i \geq i$.If $i \geq j$, then $s_j \geq j$.So either $s_i \geq i$ or $s_j \geq j$ is true.
 » Problem B is easier than I expected in Div 2 :D
 » Can anyone please explain the logic behind problem A. I’m completely confused about how the code is written.
 » In div1 C1/div2 E1 how to optimise the taking best interval and taking intersection of intervals. you should have also posted the implementation code of the solution
 » Can someone help me where my code is failing for Div 2 C problem? Submission id 230209550
 » This was a wonderful contest Problems were mainly based on observations and less on standard techniques. Thank you for such contest.
 » :((
 » Please go through the given youtube video for the explanation of problem A(Doremy's Paint 3) with proof asked in codeforces round 906 div 2! https://youtu.be/Dt0L3vhSToU?si=CCXd_fzo2_ILvpHm
 » Please go through the given youtube video for the explanation of 1890B — Qingshan Loves Strings with proof asked in codeforces round 906 div 2! https://youtu.be/Pk83WXo1eUY?si=6iIO5NdPG6o_TtZZ
 » 1889A — Qingshan Loves Strings 2 In this question we are allowed to insert only "01" then why it the tutorial suggesting to insert "10".
•  » » typo
 » Can smb explain what this mean in D from div2 906? iota (p + 1, p + n + 1, 1); I read the solution and it wasn't mention there, so I'm a little bit confused
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   https://en.cppreference.com/w/cpp/algorithm/iotaTL;DR: the array $p$ will be initialized as $p = [\text{unaffected}, 1, 2, 3,\dots, n-1, n]$
 » in problem c1(easy) i cant understand this word "In the "no intersection" case, we can just simply pick two best intervals."i don't think it can solve simply:(
 » for problem D we say that I always connect with the 1st city to minimize the multiplication i * j * c , but how can i be certain that this always right since taking other two cities may have a bigger Sum(ak)?can anyone please explain this!!
•  » » Let's consider a pair of singleton vertices $i$ and $j$. The claim is that if we can connect $i$ and $j$, then we can connect either $i$ or $j$ to $1$. If $i=1$ or $j=1$ that's trivially true. Otherwise, we know $i, j ≥ 2$ and we can assume without loss of generality that $a_i ≤ a_j$ (otherwise just swap $i$ and $j$).We want to prove $a_i + a_j ≥ ijc$ implies $a_1 + a_j ≥ 1jc$ or simpler $a_j ≥ jc$ (since worst case, $a_1 = 0$). steps of proof$a_i + a_j ≥ ijc$ (given)$a_i + a_j ≥ 2jc$ (because $i ≥ 2$)$2a_j ≥ 2jc$ (because $a_i ≤ a_j$)$a_j ≥ jc$ (QED)The same logic also works for sums of connected components, but we don't even need it, because the above shows that it's enough to connect singleton vertices to vertex 1.
•  » » » Amazing proof !!!
•  » » » » اي قلة ادب دي
•  » » » » » صاحب الكمنت دا لازم يتحاسب
•  » » » How will I be able to intuitively think this in the context?
 » 5 weeks ago, # | ← Rev. 3 →   I don't see how to "see" the solution for Div2C... Can someone explain the intuition?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   .
•  » » » So sorry, I meant Div2C
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   For C you can observe the fact that the condition described in the problem is opposite of what the condition for palindrome is i.e for each i : [0, s.size()/2], s[i] == s[s.size()-i-1]. Keeping this in mind the condition for problem becomes for...., s[i] != s[s.size()-i-1]. Now consider a case when length of the string is ODD. In this case you can observe that no matter what you do the character at the position (s.size())/2 will always be equal to itself hence you have to give up i.e for odd string or for strings that only have unique character that answer can never be formed.Now when the answer can be formed, Notice two things:1. when s[i] == s[n-i-1], s[i] == '0', in this case the only thing you can do is add "01" at the n-i-1 position making -> s[i] = '0' s[new] = '1'.2. when s[i] == s[n-i-1], s[i] == '1', in this case you have to add "01" before the ith position making s[new] = '0' and s[n-i-1] = '1'.Keep doing the above for 301 iterations, if in the end the result array has a size > 300, that means answer was never possible otherwise it print the answer.
•  » » » » » Thank you very much!
 » In problem D of div-2 does the given constant actually have any impact ? Like whats the significance of c?
•  » » With $c = 1$ the tests would be weak.
•  » » » ok thanks.
•  » » » why does this not work, if we sort the array based on c = 1 from which we are getting the order and then check if we can build the tree using that order? here is my submission for the same.
•  » » » » It works, but giving $c = 1$ in the statement would mean that it's harder to kill wrong solutions.
•  » » » » » It is not working I have tried or I have done something wrong but I am unable to find any mistakes in my solution so I am still confused as to why it is not working can you have a look at my solution
 » 5 weeks ago, # | ← Rev. 4 →   For div1 F, we can solve it faster in $O(n\log{n})$. To get a prefix of an array $a_1, a_2, a_3, \ldots a_t$, where $a_i$ is the value on node $i$, we should consider all valid nodes, and find if there exists a covering with $\le k$ nodes. A node covers all nodes in it's subtree. Then to do this fast, we consider an auxillary graph. We should only consider the nodes, such that they're on the path $[a, r]$ for $1 \le a \le t$. We can see, that since $a$ is forced, all the valid nodes on the path from $a$ to $r$ must have the same value. So this leads us into splitting the path of $[t+1, n]$ into 2 parts. The one already in auxillary tree, and the one that isn't. For the part that isn't, we can simply find it and work with it directly, since it is amortised $O(n)$. We can easily find the closest ancestor valid node in the auxillary tree too.Now we consider 3 cases, either no operation, an operation with the value of the path in the auxillary tree, or an operation with a value of the added path. For no operation, we should invalidate as usual, and mark this path as unneeded, i.e. it doesn't need to be covered, but it can be.For an operation with the value of the added path, we need to remove all the nodes in path to the current node. We can notice that this is a simple function of the degrees of the needed nodes of ancestor, as we split each old cover into the children covers. Additionally, if we have to delete them, we can do so directly as it again amortises to $O(n)$.For an operation with the value of the auxllary tree, we can simply connect it to the auxillary tree. If the auxillary tree currently doesn't need a covering, we need a covering now, so we can make the values force need it. Again, doing this explicitly amortises to $O(n)$. Most of the difficulty is maintaining the moving parts, but here is a full implementation 230451211 (My implementation is 400 lines :p)
 » Could somebody explain Div1C2/Div2E2 in more detail, after we understood dp in O(n^2k)?
•  » » I ended up using k splay trees to keep the dp stored and find the max. the t-th splay tree contains all dp values that need exactly t segment removals. so, whenever a new segment [l,r] is being processed, all the dp[l][t] up to dp[r][t] are moved from splay tree t to splay tree t+1 (for all t from 0 to k), because now they need 1 more removal of a segment to be reachable. and now i calculate dp[r+1][t] = 1 + max value in splay tree t.because these removals are log n amortized, the complexity is also O(n k log n)
 » Wow. Just learned from div1c one can simply use a sparse table instead of a segment tree to handle this kind of dp. Really nice!
•  » » Could you please explain how the sparse tree with updates works? I am confused on this array example: 3, 1, 4, 1, 5, 9, 2, 6 The sparse tree looks like 3, 1, 4, 1, 5, 9, 2, 6 3, 4, 4, 5, 9, 9, 6 4, 5, 9, 9, 9 9 After updating the index 3 to 10 based on the solution's implementation the sparse tree becomes 3, 1, 4, 10, 5, 9, 2, 6 3, 4, 10, 5, 9, 9, 6 10, 5, 9, 9, 9 9 Querying the max of (1,7) will return max(st[1,2],st[4,2])=max(4,9)=9, the answer should be 10. It seems to me that you need to update all ranges in the sparse tree that include index 3, making the sparse tree look like this 3, 1, 4, 10, 5, 9, 2, 6 3, 4, 10, 10, 9, 9, 6 10, 10, 10, 10, 9 10 However, this is O(n) (maybe even O(nlogn)) causing TLE, and not how it is implemented in the solution.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   Never mind, I figured it out. The change function is only used in the construction of the sparse tree, so changes in the middle of the sparse tree will never happen.
 » Can someone explain Div2D or Div1B
 » I think div2 C statement could be more clear.
 » 4 weeks ago, # | ← Rev. 2 →   I think in E1 they meant that you can just go throw all segments after making prefix sums, then, if there at least one index between right and left border of segment, which covered by only two segments, you just iterate throw letf to right border of segment and when there is index i, where prefix[i] == 2, you just fix that on index i you can delete this segment. It probably works in O(4*n) and take not many space
 » Can anyone provide me with the code of div2 D's easy version?
 » 3 weeks ago, # | ← Rev. 3 →   In Problem 1889B Deremy's connecting path, My code is failing for test case 4th and in that, 81st test is failing. i couldn't seem to resolve the problem because I cannot see that 81st test of the test case 4th. I don't think there is a overflow problem because I am using double and my algorithm seems to be correct. i think there is some corner case missing. 1. My algorithm: I will divide the array a by c( to reduce c=1) I will first find the maximum index (1<=i<= n) such that one can make edge (1,i). i will take the sum from 1st to ith index. then i will iterate from i+1 to n, and as soon as I find an index j such that edge (1,j) can be formed with (sum+a[j]) >= 1.j then I will update the sum till jth starting from 1st. Could anyone please help?Just for reference: My Submission https://codeforces.com/contest/1890/submission/232326341
•  » » Take a look at Ticket 17144 from CF Stress for a counter example.
•  » » » Thank you so much!! actually, a=2 and b=4 for c = 2 and i=1,j=3 I wanted to check if (a+b) >= 1*3*2 but I was actually checking (a/c + b/c) >= 1*3 which was giving wrong answer because of decimal thing.
 » Problem E in div1 is great, but the limitations are incredibly strict for completely no reason...
 » 7 days ago, # | ← Rev. 2 →   For problem C1(easy version), can someone elaborate on the proof of the statement "In the "intersection" case, there are at most n useful interval".
 » 7 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; } Div1 Problem C2 could be solved without sparse tables. Instead we observe that when you query an interval, it is the same as getting the minimum dp value from the leftmost element in the interval up until the current position i. These minimums could be store using Arpa trick. Here is a link: https://codeforces.com/blog/entry/48994