Codeforces Round #771 Editorial

I hope you enjoyed the problems! You can give feedback on each problem and also choose your favourite below. This could help me and other problemsetters understand what type of problems you want to see on Codeforces.

1638A - Разворот

1638B - Сортировка нечётными обменами

1638C - Граф инверсий

1638D - Большая кисть

1638E - Красочные запросы

1638F - Два плаката

Now you can choose your favourite problem from the ones you solved during the contest or upsolved after it.

• Problem A

  42

• Problem B

  144

• Problem C

  525

• Problem D

  172

• Problem E

  141

• Problem F

  40

UPD: Don't forget to check out ak2006's video tutorials on his channel.

• 6 weeks ago, # ^ |

  A little question about avoiding accidents:

  In this round I finished coding my solution to problem E in the last four minutes, but when I try to submit the code, I found I cannot do that. In some pages I can't click the bottom 'submit', and in somes others, I was told 'Put you source into the textarea or choose the file' although I have already choosen the file', it even return 403 error in one attempt.

  I think there is something wrong with my network, so I want to ask that have you ever encountered such a situation? How to avoid such a desperate situation?

  Forgive my poor English.

  • 6 weeks ago, # ^ |

    You are not alone comment, I also get 403 and white pages that don't reload... I started noticing this one year ago, more o less.

  • 6 weeks ago, # ^ |

    I also can't click on submit sometimes and during hacking, each submission takes around 30 seconds to load which is annoying.

• 6 weeks ago, # ^ |

  couldn’t solve = bad ig. I liked it, felt it was interesting

• 6 weeks ago, # ^ |

  ← Rev. 2 →  

  -19

  Was there in the last contest too...

• 6 weeks ago, # ^ |

  Don't use "memset(rk,0,sizeof(rk));" for each testcase,if you do so,the time complexity of your code will be O(T*sizeof(rk)).

  But if you use "for(int i=1;i<=n;i++)rk[i]=0",the time complexity will be O(sum(n)),which can get pretsets past as well.

  (sorry for my poor English)

  • 6 weeks ago, # ^ |

    got it,thanks!

• 5 weeks ago, # ^ |

  Can you tell me how did you make the edges in merge sort algo

• 6 weeks ago, # ^ |

  ← Rev. 2 →  

  +1

  For b Push all odds into one array and all evens into another array if both arrays are not sorted print no else print yes the observation is if you start from sorted array and perform this swap operations and consider all possible arrays from these swap operations then you will see all even numbers are sorted in those arrays and also all odd numbers are sorted in those arrays

• 6 weeks ago, # ^ |

  Actually, N=104N=104 means to me that "only" O(N2)O(N2) pass.

• 5 weeks ago, # ^ |

  The strange limit for nn is for failing some heuristic that works like this: Find a wrong solution which finds an answer in O(n)O(n) for a given starting position. Also have a brute force solution that finds the correct answer in O(n2)O(n2) for a given starting position. Then, run the wrong solution on all positions and the correct solution only for the 3030 most promissing positions.

  Unfortunately, I could not find a pattern that would fail this, so we changed the limit for nn. My solution runs in 748ms/2000ms.

• 6 weeks ago, # ^ |

  same solution as editorial, just didn't use FastIO library. unfortunate

• 6 weeks ago, # ^ |

  The text is the editorial. It explains the solution of the problem.

• 6 weeks ago, # ^ |

  For some contest, we don't get codes.. It depends on the author. In case you still need codes you can go and read submissions of others. To be precise you can follow SSRS_. He participates in almost all the contests and also his submissions are much similar to the editorial ones....

• 6 weeks ago, # ^ |

  double check problem D

  • 6 weeks ago, # ^ |

    Ah it's C... my bad. Thank you man.

• 6 weeks ago, # ^ |

  You mean problem C

  • 6 weeks ago, # ^ |

    Yes, I made the edit.

• 6 weeks ago, # ^ |

  That does work.

• • 6 weeks ago, # ^ |

    Let us take an example of 3 2 1 6 5 4 , Here till the third index permutation of 3 is present so we could surely say that it will be a separate component which would not share any edge with 6 , 5 or 4 . But if we take an example :- 3 1 5 2 4 , Here till the third index we don't have the permutation of 3 this implies that there exists a number after third index which will share an edge with 3 and 5 both. Likewise we could calculate the number of connected components.

    • 5 weeks ago, # ^ |

      brilliant!

• 6 weeks ago, # ^ |

  scanner?

  • 6 weeks ago, # ^ |

    For problems B and C as well, I use the same way to get the input using scanner. In those 2 problems, the value of n is a lot bigger than this.

    • 6 weeks ago, # ^ |

      There are 500 tests and 500 n in problem A. It is 250000 elements. In problem B, for example, special limit on the amount of n: 50000. Scanner is slowly.

      • 6 weeks ago, # ^ |

        Oh. Didn't notice that.

        Just noticed this below statement in problems B and C, after reading your comment. It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

        So, in problem A, it is max 250000 In problems B and C, it will be max 200000.

        I see the difference now. Thanks for replying.

        Any suggestions on how to get input, when the input is large ?

        • 6 weeks ago, # ^ |

          When I changed from Scanner to BufferedReader, it passed. Submission — 146445635

          Thank you vdxz for your reply.

• 6 weeks ago, # ^ |

  Your merge function has a bug.

  if(parent[_x] != parent[_y])

  shoulde be

  if(find(_x) != find(_y))

  Though even after the fix the code will probably TLE.

• 6 weeks ago, # ^ |

  After competition, we go 0 with DSU. Sed lyf

• 6 weeks ago, # ^ |

  My DSU solution passes, you can check it here 146394231

  • 6 weeks ago, # ^ |

    Thank you for sharing the submission. But, I didn't get what you did! It would be great if you could explain what was the approach and how that differs from my solution.

    • 6 weeks ago, # ^ |

      See my explanation here. DSU is modified so that we maintain the maximum element of the set in the array 'm', similarly to the size of the set in the array 'sz'.

• 6 weeks ago, # ^ |

  solve() have difficult O(n ^ 2)

  • 6 weeks ago, # ^ |

    Nah it amortizes a lot. I think it's O(n∗logn)O(n∗logn) because when there's a bunch of maximums bigger than currently added value, they all get reduced to one component

    • 6 weeks ago, # ^ |

      Can this be proven somehow? Even I passed it using this but still have no idea why it works.

      • 6 weeks ago, # ^ |

        Yeah, of course. I will refer to my solution 146394231. DSU technically isn't O(1) but for these constraints let's say it is.

        So let's consider the inner while loop. How many times the operations inside, which btw take constant time, will get executed (not in one iteration of for loop but for the duration of the whole solve())? For this let's consider the value of comp_maxes.size(). We see that for each iteration of for loop it increases at most by 1. So it cannot be greater than nn, its size is linear. And in while loop it can't decrease by more than its size. Said differently, number of deletions (which is equivalent to number of executions of while loop) cannot be greater than number of insertions, which is linear. So body of while loop will get executed at most nn times overall. So the cost of solve() is nn times the cost of set::lower_bound() which is O(logn)O(logn).

• 6 weeks ago, # ^ |

  ← Rev. 2 →  

  0

  Your implementation for dsu has an infinite loop. If s1 = s2 in the unite function, then value of dsu[s2] becomes positive and if you try to use find_set on any member of this component, it will never find an answer.

• 6 weeks ago, # ^ |

  I used DSU and merge_sorting.Here is my AC code 146425315,which is O(nlogn).Hope it will help you.

  • 5 weeks ago, # ^ |

    Thanks, it helps me a lot.

• 6 weeks ago, # ^ |

  You are getting TLE not because of DSU, but because of nested for loops.

• 6 weeks ago, # ^ |

  I'm not sure you can do it as a topsort directly, because there may be multiple different operations that "unblock" a position. However, you only need one operation to unblock a position, but the topsort will enforce that you do all such operations. Maybe there's a different way to frame it as a topsort, but I could not come up with one.

  • 5 weeks ago, # ^ |

    Here is a similar problem that everyone (basically) use topo sort. Strange Printer II

    Mainly 3 different points compared to this problem: 1. no 2x2 restriction 2. only use colour once. 3. Output result if valid.

    I believe the third one won't be hard, since we just record the result when the in-degree is 0. I am getting stuck when I try to resolve the 1 & 2.

• 6 weeks ago, # ^ |

  To me it's more like SpeedForces...

• 6 weeks ago, # ^ |

  I think, when you change color you should utilize lazy array and add its value on a given interval which you consider.

• 6 weeks ago, # ^ |

  ← Rev. 2 →  

  +3

  If n == 1, you dont read in the only element in the array, which then causes it to become the n on the next pass. Try cin >> n; inside the if block.

  • 6 weeks ago, # ^ |

    Yeah, that's got to be it. Thank you.

• 6 weeks ago, # ^ |

  You will need this observation: if a1,...,aia1,...,ai is a permutation of 1,...,i1,...,i then there is no edge from vertices from 1,...,i1,...,i to the rest. Then, call i0i0 the first index satisying our condition. It is clear that a1,...,aia1,...,ai form a connected component. Then consider i1i1 the next number. We have a[1..i0]a[1..i0] is not connected to a[i0+1..i1]a[i0+1..i1] and a[1..i1]a[1..i1] is also not connected to the rest. So we can conclude a[i0+1..i1]a[i0+1..i1] is also a connected component.

  So now we need to count number of ijij. Your implementation is correct because sum of kk distinct positive integers is k⋅(k+1)/2k⋅(k+1)/2 if and only if they are a permuation of 1,...,k1,...,k.

• 6 weeks ago, # ^ |

  No, You're not a dumb. You are just a beginner.

  • 6 weeks ago, # ^ |

    No I'm stupid af. I feel frustrated and hate myself all the time while doing codeforces. I can't even solve ad-hoc (Div2 A/B) problems on my own without reading editorials, let alone more difficult ones that require DSA. The solutions are always tricky and appear out of nowhere. How can I improve? Pls help this dumbass.

    • 6 weeks ago, # ^ |

      practice is the only true mantra

• 6 weeks ago, # ^ |

  this works like magic but my brain could never think an implementation like this :)

• 6 weeks ago, # ^ |

  can you give me any logic behind this implementation??

  • 6 weeks ago, # ^ |

    ← Rev. 2 →  

    0

    For me personally, looking at the diagrams given in the problem's test case helped.

    Problem statement

    Example - to get familiarised with this problem:

    Important example that helped me get this idea:

    So,

    Additional examples to try, to make sure this works:

    • 5 weeks ago, # ^ |

      Great approach.

• 6 weeks ago, # ^ |

  Creating sparse table is actually not required. Since, you are always calculating minimums for a suffix, you can precompute all suffix minimums.

• 6 weeks ago, # ^ |

  it passed all the test cases if acc to you it will fail on any case then do let me know.

  • 6 weeks ago, # ^ |

    Only if connected components is 1 and n = 10^5. Use long instead of int.

• 5 weeks ago, # ^ |

  Each interval has a color id. Let's keep two arrays:

  • pendingColor[c], the updates pending for each color group,
  • pending[sid], the updates delta pending for a particular segment id

  When updating a color, do it in O(1): pendingColor[c]+=x.

  When creating a new segment with a given color, I create it with an offset pending[sid]=-pendingColor[c].

  That way, the updates pending for a given segment ispendingColor[c]+pending[sid].

• 6 weeks ago, # ^ |

  for(int i = 0; i < vpe.size() — 1; i++){

  vpe.size() is unsigned int64. if size == 0, then it will not be i < -1, but i < max(unsigned int64).

  PS: I looked your code and can not find the error so I tried for myself and my IDE gave me the tips.

  • 6 weeks ago, # ^ |

    Thanks for the tips! It would be great if you can share the name of your IDE :)

    • 5 weeks ago, # ^ |

      Qt Creator. But I think any modern IDE will have similar functionality.

• 6 weeks ago, # ^ |

  Get your maths right.

• 6 weeks ago, # ^ |

  Obviously bro!!!! 10^5 is 100000 which is way greater than 86227.

• 6 weeks ago, # ^ |

  It doesn't seem like that's the case, what happens in a case like the following?

  • 5 weeks ago, # ^ |

    Is the test idea that a BFS would traverse this in a zig-zaggy fashion with O(N^2) iterations in total? I guess that reduces my fun fact to "I was fooled to think my straightforward solution is O(N^3), and tests were weak" xD

• 6 weeks ago, # ^ |

  Each component is a segment of the array because consider a inversion with indices i, j then if a[k] < a[i] where i < k < j then it will have edge with index i else if a[k] >= a[i] then it will have edge with index j which means every element between index i,j will belong to the component of i,j.

  Consider two adjacent segments seg1,seg2 which are forming different connected components which means there is no edge from any element of seg1 to any element of seg2 which means that max element of seg1 is less than min element of seg2.

  If you consider a prefix till index i (one based indexing) and if it is containing all the numbers from 1 to i then max element of 1 to i is i and min element of remaining array is i + 1. So the sub segment till index i will increase num-of-connected-components by one which exactly your code is doing .

  • 6 weeks ago, # ^ |

    I understood first two paragraphs easily but I am having difficulty in understanding 3rd paragraph. Can you please elaborate on it.

    Thank you for your time :)

    • 6 weeks ago, # ^ |

      Its like we are starting with all the indices in one component and then we are forming new component when prefix till i is disconnecting with suffix[i+1 .. n](which again may get split in future). And that happens when max(prefix till i ) = i, that is prefix till index i has elements from 1 to i.

      • 6 weeks ago, # ^ |

        Okay understood. Thanks

• 6 weeks ago, # ^ |

  instead of endl use "\n", TLE is due to slow output, my solution was also getting TLE due to same issue.

  • 6 weeks ago, # ^ |

    Thank you bro it is submitted

    • 5 weeks ago, # ^ |

      yeah, no problem!

• 5 weeks ago, # ^ |

  ← Rev. 2 →  

  0

  I did the same thing but I am getting TLE. Solution with sorting working but still getting TLE My Solution: 146510364 If anyone have any idea why and how to fix this please help

• 5 weeks ago, # ^ |

  This is super helpful! Thank you.

• 5 weeks ago, # ^ |

  In regard to my implementation, BIT is almost 4-times faster than Segment Tree. So it is recommended to use BIT when both are options because it is faster and shorter.

  Another reason that leads to TLE is the excess time on IO. (n=10^6) You can use fread to get faster IO like 146629883. In my experiments, it save ~1600ms in this problem.

• 5 weeks ago, # ^ |

  ← Rev. 2 →  

  0

  For Input n-1, n-2, n-3,... 1 it should fail, since it becomes O(n^2)

  I did nearly the same implementation, but deleted the unused elements from the set, then it is O(nlogn)

  see https://codeforces.com/contest/1638/submission/146446755

• 5 weeks ago, # ^ |

  ← Rev. 2 →  

  0

  I'm also thinking this thing while upsolving D. I had a blurred picture not super clear that if there might be a dead end it'll be reached in m*n steps and when we have a choice to form new special cells, we can go with any choice as long long it's creating at least 1 new special cell because choosing set A cells rather than B do not hinder our answer as set B can always be chosen later. I mean choosing one set of cells over another doesn't force us with restricted choice. Idk whether what I'm thinking is right or wrong.

• 5 weeks ago, # ^ |

  Instead of using fast i/o you've mentioned, there is ultra light weight version (but slower a bit): 146387910

• 5 weeks ago, # ^ |

  Div2 D

• 5 weeks ago, # ^ |

  Cool solutions, but, to my mind, they are definitely harder than editorial one (:

• 5 weeks ago, # ^ |

  Additional optimization