### doreshnikov's blog

By doreshnikov, history, 20 months ago, 1579A - Casimir's String Solitaire

Idea: MikeMirzayanov

Tutorial
Solution

1579B - Shifting Sort

Idea: doreshnikov

Tutorial
Solution

1579C - Ticks

Idea: MikeMirzayanov

Tutorial
Solution

1579D - Productive Meeting

Idea: doreshnikov

Tutorial
Solution

1579E1 - Permutation Minimization by Deque

Idea: MikeMirzayanov

Tutorial
Solution

1579E2 - Array Optimization by Deque

Idea: doreshnikov

Tutorial
Solution

1579F - Array Stabilization (AND version)

Idea: doreshnikov

Tutorial
Solution

1579G - Minimal Coverage

Tutorial
Solution Tutorial of Codeforces Round 744 (Div. 3) Comments (58)
| Write comment?
 » Please fix the code for problem G.
 » 20 months ago, # | ← Rev. 3 →   Similar stuff in video format :video solutions
 » Really sorry the editorial took longer than usual. I'll try to post it sooner next time!
•  » » Still, this is one of the highest-quality editorials I've seen, great job!
•  » » » true that !
•  » » problem B : solution -> actions.push_back({l,min_pos}); "l" is not defined here.
•  » » » Yep, sorry, fixed
 » Regarding E2:- I have faced similar kind of concept in many problems "finding elements smaller or larger than current element occurring before it"... someone please tell me a source to learn __gnu_pbds::tree (or) balanced binary search tree (or) any best way to solve this.
•  » » https://codeforces.com/blog/entry/11080 This blog by Adamant is perfectly describing how to use ordered_set.
 » in problem A how can it handle "BABA" case its answer should NO but according to above solution its give YES
•  » » the string is of length 4, and there are 2 B's which is half the size so it would print yes.
•  » » » But I guess, it clearly mentioned that we can't pick two adjacent character
•  » » » » They don't have to be adjacent, but they can be.
 » 20 months ago, # | ← Rev. 2 →   There is a nice way to implement G with bitset. Let's do a binary search on answer. DP for checking if we can stay inside the segment of fixed length $m$ looks like this: bitset<3000> d; forn(i,0,m+1) d.set(i); auto cut = d; for(auto x : a) d = ((d>>x)|(d<=m$, otherwise it's$
•  » » I solved it like this too. Very elegant.
•  » » » Can you please explain what we are doing in this line for(auto x : a) d = ((d>>x)|(d<
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   After i loops, j'th bit of b represents whether it is possible to reach position j after considering i segments, or in other words, j'th bit represents whether it is possible for the "end" of i'th segment to be at position j. Now, say we are in the i'th loop. j'th bit of b currently represents whether it is possible to reach position j after considering i-1 segments. So, if we consider the i'th segment now, position j is reachable if and only if either position j-x is reachable after i-1 segments or position j+x is reachable after i-1 segments. This transition is equivalent to new_b[j]=b[j+x]|b[j-x]; which is equivalent to new_b = (b>>x)|(b<m, which is a way of saying that it is not possible for any segment to end at j>m. A simple way to do this for any bitset b is b = b&cut; where cut has j'th bit=1 for j<=m, and 0 for j>m.After n iterations, j'th bit of b represents whether it is possible to reach position j if we start from any of the positions p for 0<=p<=m. If this is true for any j, where 0<=j<=m, then we return true, else we return false.Hope you understood that. Sorry I'm not good with markdown.
•  » » » » » Got it, thanks!
•  » » I had the same idea but messed something up
•  » » Why do you use &cut?
•  » » » You actually need a bitset of size $m+1$ but you can't do that in runtime. It's basically emulating that.
 » 20 months ago, # | ← Rev. 2 →   https://codeforces.com/contest/1579/submission/130289614 pls tell me why this soln for D gets WA if u have time. PS : ignore it, i got it why im getting it rong..
 » I reflected a LOT on problem G and i observed the dp solution, but didnt come up with the idea that answer never exceeds 2.lmax :( beautiful problem over all.
 » Can you tell me how mysolution is getting a wrong answer even though I did it exactly how the editorial says . https://codeforces.com/contest/1579/submission/130186425
•  » » You are inserting into the beginning of the vector, which takes O(n), because it shifts everything for one step. Better solution would be use data structures that allows you to add elements in O(1). It can be deque, list (which is based on linked list). Another solution is using vector with two pointers in the middle (and shift them while you are adding elements to the left or to the right). Thus you dont need to shift all elements each time when you need to put smth in the beginning. Your solution fails on tests like (200000, 199999, 199998...), because time complexity becomes O(n^2), which it too slow for this task.
 » 20 months ago, # | ← Rev. 2 →   Alternative solution for 1579D - Продуктивная встреча. Think of following question: what arrays $a$ you can turn into 0? Suppose sum of $\sum\limits_{i=1}^n a_i = S$ (same as in editorial). If $S$ is odd — obviously we can't. Also, by simplest pigeonhole principle we know if there is $a_i > S/2$, then we can't reduce all $a_i$ to zero. But, if there is $a_i > S/2$ it's easy to see that it's maximum of array, and it's unique.So idea to decrease corresponding $a_i$ in a way to make it possible to turn them into zero. To do that, calculate $S$. Find $a_i > S/2$ if it exists. And, decrease it by one while $a_i > S/2$ still holds (decrease $S$ correspondingly). Because this maximum was unique, no need to search anything else. Now $S$ can be odd, but we'll handle it later. Now, we'll make list of all participants with their repetition. So, in case $a$ = [1,2,3] we will get $p$ = [1,2,2,3,3,3]. Its length is $S$, and if it's odd, remove last one element. Now, I claim answer is pairs of $(p_i, p_{i + len(p)/2})$. The only thing to prove that is left is: $p_i \neq p_{i + len(p)/2}$, but this follows from $a_i \leq S/2$. Time complexity is $O(S)$. 130295963
 » When up-solving, I tried to solve Question E2. I have been getting TLE on test case 3. My logicFor each element, I counted the number of smaller and greater elements before it. The final result is the sum over each element the minimum of the number of smaller and the greater numbers before it. To find the number of the smaller and greater numbers before any element in the array, I used the method 3 given on this website : Code Used. The Time complexity for the same is O(nlogn).Any help regarding where I went wrong would be greatly appreciated. My submission.
•  » » The BST code you've used does not maintain any balancing, and as a result, might work in O(n) per insert. Try to insert consecutive integers and you'll notice, the height of the tree is linear to the size. There are efficient BST variants, like Red-Black Tree, AVL Tree or Splay Tree, which are a bit more complicated, but maintain O(log(n)) time per query (amortized or not). For this problem though, you could use ordered_set from pbds. Refer to this blog by Adamant for more info https://codeforces.com/blog/entry/11080.
•  » » » Thank You!! The explanation helped a lot. And yeah, I tried using ordered_set from pbds and my solution got accepted.
•  » » » Can you help me ? Why it is giving TLE : E2 Codeand it is accepted : E2 CodeThanks in advance. map is used just to store frequency
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   Perhaps there is an anti-hash test there. Because of it, unordered_map can run in $O(n)$.
•  » » » » No need to use map if you use ordered_set. both structures may yield high working times resulting in your TLE.
 » I was going to answer a comment with a different proof of D (always take the two largest elements) that I came up with, but it got so long that I figured it would look better here with spoilers and math mode. This is mostly a result of bashing out a ton of different cases that could happen. Feel free to point out any mistakes (which can include forgetting to format somewhere).There are two cases (as the editorial mentions): 1. The largest element is greater than the sum of all of the other elements.In this case, it's optimal to use the largest element in every operation (an upper bound on the answer is the sum of the non-largest elements, and doing an operation without the largest will give us 1 operation but decrease the upper bound by 2), and doing the two largest every time will accomplish this. 2. The opposite: largest element is less than or equal to the sum of all other elements.Let's do our operations in such a way that this (invariant) is always true: the largest minus the smallest element is at most 1. Why? Because the final state will be a bunch of 0's, and maybe a single 1 if the whole sum is odd. Having this invariant implies we'll reach an optimal state.If the largest minus the smallest is at most 1, and we have a 0, then the largest element must be at most 1. If we only have 0's and 1's, then we can pair the 1's until we can't anymore, and we either get all 0's (even sum) or all 0's and one 1 (odd sum). In both cases, this is optimal — there's no way you could have done more than $\lfloor \frac{sum}{2} \rfloor$ operations, and having that end state means that you did exactly that many operations (each operation subtracts 2, so the number of operations is $\frac{initial \, sum - final \, sum}{2}$, you can do out the cases if you want).So if we can make sure that the largest minus the smallest element is at most 1, we're guaranteed to reach this final optimal state. If this condition is initially true, then taking the two largest every time will keep it true.If $(largest - smallest) = 1$, then we wouldn't decrease smallest without also decreasing largest, since we prefer to take larger elements [do casework on whether you have 1, 2, or more than 2 duplicates of the largest element]. If $(largest - smallest) = 0$, it doesn't matter what we do in this operation, $(largest - smallest)$ can become 1 at worst. So if this condition is true, then it will stay true, and our final state will be optimal.So the last part is if this condition isn't initially true, then we need to make it true. Say we have x copies of the maximum element.If $x \geq 2$, then we'll decrease pairs of these maximum elements until we have $x \mod 2$ copies remaining. Note that because we assume $(largest - smallest) \geq 2$ [the condition isn't initially met], it's always valid to decrease these maximum elements, because they must be at least 2. If x was even, then the largest element decreases by 1, and we're closer to our goal of $(largest - smallest) \leq 1$. If x was odd, we get...$x = 1$. With our algorithm of selecting the two largest, every operation will decrease the largest by 1, because we only have 1 copy of the largest. Sometimes we'll decrease the smallest, sometimes we won't, but no operation can increase $(largest - smallest)$.At the beginning, we asserted that the largest element $\leq$ sum of all other elements. Our operations will preserve this fact.We'll always take one away from the largest element, so the largest element will decrease every time the sum of the rest decreases. If something else becomes the largest element since it wasn't part of the operation, and it's at least $2$, then you have at least two elements that are at least $(2 - 1)$ that were part of the operation. The only time where the sum of all other elements can become smaller is in the final state, if the sum of all elements is odd, but that state is optimal anyway.Why am I bringing this up? Because if we assume that to be true (which it is), then in the $x = 1$ case, there's no way that the single maximum element can remain the unique maximum forever. As long as $(largest - smallest) \geq 2$, then the largest element $\geq 2$, so the remaining sum $\geq 2$, and we have at least 2 elements, so we can continue doing operations. These operations will continue until either that element is no longer the unique maximum (so $x > 1$), $(largest - smallest)$ becomes $\leq 1$ naturally, or that element becomes less than 2, in which case $(largest - smallest) \leq 1$ anyway. In all cases, we will end up closer to our goal of $(largest - smallest) \leq 1$.The fear may be that we can run out of operations while $(largest - smallest) \geq 2$. But in the casework on x above, it's shown that if $(largest - smallest) \geq 2$, we will always still have operations that we can do. So while $(largest - smallest) \geq 2$, we will have operations to do, and these operations can never increase $(largest - smallest)$. We can't do infinite operations, so eventually, $(largest - smallest)$ has to decrease to $\leq 1$, and the algorithm will succeed.
•  » » Yeah this was how I implemented a previous problem that asked the same thing. Solution here : 111076508
 » 20 months ago, # | ← Rev. 2 →   In problem G, Can someone explain why we are taking 0 as the leftmost boundary and never crossing that? I am stuck with this idea for two days.
•  » » In problem G ,we are maintaining the relative position of the start with respect to the left and right boundaries, not the actual position of start. So, if in any case we are going to cross the leftmost boundary of our segment, we would be assuming that leftmost point(<0) as the new leftmost boundary and start also.That's why we are always maintaining 0 as the leftmost boundary and never crossing that. You can watch galen_colin's stream to get a better understanding. Link:- https://www.youtube.com/watch?v=JRuAgCCwi0M
•  » » » Thank you so much. I finally get it.
 » Hey guys, in problem E2, I use discretion and Binary Indexed Tree to count numbers and it lead to TLE, but this solution complexity should be $O(nlogn)$, I do not know why this solution cannot ac, this is my code link
•  » » You memcpy the whole array while you need only n elements. Use vectors to avoid such mistakes.
•  » » I use the map insted of unordered map. It got AC 193683141
 » Any similar problems like problem G? I really liked the idea.
 » Hey guys, I've got TLE in E2, but I used multiset with lower/upper_bound which works with $\ O(logN)$ complexity. So, I guess that my submission should work with $\ O(NlogN)$ time. Here my submission 130358299, can you tell where I'm wrong.
•  » » https://codeforces.com/contest/1579/submission/130371833We are in the same situation I guess
 » If it does not bother you, can someone please tell me why this submission : https://codeforces.com/contest/1579/submission/130371833 gets TLE, I thought its complexity was O(n log n) as expected by the correct answer.
•  » » 20 months ago, # ^ | ← Rev. 4 →   I believe here the distance function takes O(n) time. It is much better to use a structure like __gnu_pbds::tree. You can read about it here. SpoilerYou can read more about the Time complexity of distance function here.
•  » » » Oh, yeah, huge thanks, I always assumed it was O(1).
 » For Problem D, will choosing the min and max element at each turn, work similar ?
•  » » nope, i tried that, does not work + wasted a good 4 hours :)
•  » » » It works. but I couldn't prove it.
•  » » It worked for me.My submission
 » Problem $F$ can be solved using $Binary\ Lifting$ although it is not optimal. Idea We make a $sparse\ table$ containing where to go at $2^i$ th jump. We make another $sparse\ table$ containing the $range\ AND$ value that we will get at $2^i$ th jump. Now for each index, we find the maximum steps so that the range $AND$ remains $1$. Let us denote the steps as $len$. If it remains $1$ forever then the answer is $-1$. Otherwise we do it for all indices and take the $MAX_{1\le i\le n}\ len_i+1$, as $AND$ value shows a $monotonic$ property [the property of binary search]. That will be our desired answer. Time Complexity: $O(n\log{n})$ Sample Code130189104
 » About the problem E2, I see someone write the solution like this: #include using namespace std; const int N=2e5+5; int t,n,a[N],b[N]; long long c[N]; long long ans=0; int lowbit(int x){return x&-x;} void add(int x){ while(x<=n){ c[x]++;x+=lowbit(x); } } long long query(int x){ long long ans=0; while(x){ ans+=c[x];x-=lowbit(x); } return ans; } int main(){ cin>>t; while(t--){ cin>>n;ans=0; for(int i=1;i<=n;i++) cin>>a[i],c[i]=0,b[i]=a[i]; sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b; for(int i=1;i<=n;i++){ long long cur=min(query(a[i]-1),query(n)-query(a[i])); ans+=cur; add(a[i]); } cout<
•  » » It's binary indexed tree (or Fenwick Tree)
 » 20 months ago, # | ← Rev. 3 →   Can anyone help me find why my code for D is failing? Any edge cases I need to check for? It always fails on tc 69.Anyone knows what that tc is :( ? https://codeforces.com/problemset/submission/1579/130623552 I did as said in editorial. Used a pq for choosing two persons with max sociability.
•  » » Consider the test case "2 2 2", correct answer is 3 conversations.
 » 20 months ago, # | ← Rev. 3 →   for D, will the following algorithm work? : " Choosing two people i and j such that ith person has maximum remaining sociability and j can be any other person with non zero sociability and stop this process when less than 2 people are left with non zero sociability "
 » if ai≥S−ai, the answer cannot be more than (S−ai)+∑j≠iaj=2⋅(S−ai). In first point of Problem-D editorial, How is this true?
 » 8 months ago, # | ← Rev. 2 →   d