### induk_v_tsiane's blog

By induk_v_tsiane, history, 4 months ago, translation,

We hope you liked the problems.

Task A was invented and prepared by induk_v_tsiane.

Task B was invented by induk_v_tsiane, and prepared by i_love_penguins.

Task C was invented and prepared by induk_v_tsiane.

Task D was invented by i_love_penguins and efimovpaul, and prepared by i_love_penguins.

Task E was invented by induk_v_tsiane and kristevalex, and prepared by induk_v_tsiane.

Task F was invented by induk_v_tsiane and Artyom123, and prepared by induk_v_tsiane.

1859A - United We Stand

Hints
Tutorial
Author's code

1859B - Olya and Game with Arrays

Hints
Tutorial
Author's code

1859C - Another Permutation Problem

Hints
Tutorial
Author's code

1859D - Andrey and Escape from Capygrad

Hints
Tutorial
Author's code

1859E - Maximum Monogonosity

Hints
Tutorial
Author's code

1859F - Teleportation in Byteland

Hints
Tutorial
Author's code

Some notes/challenges:

• We know about the $O(N^2)$ solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions).

• You can solve $D$ without the constraint that the segments are contained, but that is harder. It is solvable in $(ONlogN)$.

• Thank you all for participating! If you have any complaints/suggestions/advice for future rounds, feel free to share in the comments!

• +272

 » 4 months ago, # |   0 Auto comment: topic has been updated by induk_v_tsiane (previous revision, new revision, compare).
 » 4 months ago, # |   +3 Thanks for fast editorial!
•  » » 3 months ago, # ^ |   0 what does multiset extract do exactly? can I just use erase?
 » 4 months ago, # |   0 Thanks for your texts!
 » 4 months ago, # | ← Rev. 2 →   +24 Problem C can be solved in O(n^2).
•  » » 4 months ago, # ^ |   +47 Yeah, I solved it in O(n^2) by кукарек, I don't know, why my solution works correctly.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +6 maybe can be solved in O(n) too, but I don't know how to prove it
•  » » » 4 months ago, # ^ |   0 What is the O(N) idea?
•  » » » » 4 months ago, # ^ |   0 I think that the recalculation of the tail from step to step could be done in O(1) — you always know where is the maximal term and the delta to sum: -sum of all values + delta for border elements
•  » » » » » 4 months ago, # ^ |   0 Got you.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +4 First I got all the answers for n<=13 by brute force, then subtracted this answer from the sum of the squares of all the natural numbers less than or equal to n to get a series:1 3 7 13 20 29 40 52 66 82 100 120 141Then I subtracted each neighboring number in this series to get a second series: 2 4 6 7 9 11 12 14 16 18 20 21Then I realized that the second series is very much like an equal-variance series, but at the no.2*3,2*5,2*7... number this difference changes to 1.Through this strange pattern, it is possible to construct a second series (n<=250) by preprocessing, which inverts the first series to get the answer. For each example, we only need to find the sum of the squares of all the natural numbers less than or equal to n.This is my submission:218557375
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 You could have solved each test case in O(1) if you would have used (n*(n+1)*(2*n+1))/6 to calculate the sum of squares of first n natural no.s instead of using that O(n) loop ;)
•  » » » » » » 4 months ago, # ^ |   0 absolutely right!!
•  » » » » 4 months ago, # ^ | ← Rev. 4 →   +3 First of all, observe that the maximum cost permutation is like this: $1$, $2$, $3$, $4$, ... , $p$, $n$, $n-1$, $n-2$, ... , $p+1$ ;Secondly, it's provable that p=n-sqrt(2*n). And without precalculations or other things, we can solve this problem with a kinda brute force solution in O(n).My submission: 218725357 .
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 How you reach at this p = n-sqrt(2*n)
•  » » » » » 3 months ago, # ^ |   0 can you explain more why the maximum cost permutation is like that
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +6 found that reversing the last k elements where k is the minimum value such that n <= k + floor(k^2/2) (which is oeis sequence) is optimal so its o(n)don't know why it works
•  » » » » 4 months ago, # ^ |   0 I initially guessed that the largest number was n*i and that i should have some regularity, but I didn't realize that the inverse of the series i~n was the answer array.But I eventually found a very strange pattern about $\sum_{1}^{n}i^2-ans$ and solved the problem.
•  » » » » » 4 months ago, # ^ |   0 On similar terms, I was guessing the maximum term to be like max_number*i but I was unable to find the reversal pattern of latter units. My initial guess was reversing the floor(n/2) terms but couldn't extrapolate for larger numbers.
•  » » » » » » 4 months ago, # ^ |   0 Same here My initial observations was reversing last (n+1)/2 numbers. But this didn’t work correctly for larger numbers So brute force was an easy answer
•  » » » 4 months ago, # ^ |   +5 is it possible to calculate all the answers locally then make a script to create many if else statements to achieve a O(1) solution? just a random thought :)
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 but I wait the answer when n==13 for at least 7 mins,O(n!) is too terrible!:(
•  » » » » » 4 months ago, # ^ |   0 i found this: 218549633
•  » » » » » » 4 months ago, # ^ |   0 lmao he must be very patient.
•  » » » » » » » 4 months ago, # ^ |   0 true, but at least he did show some effort into writing a solution i guess
•  » » » » » 4 months ago, # ^ |   0 lol I used to do that during contest
•  » » » » » » 4 months ago, # ^ |   0 cool
•  » » » » 4 months ago, # ^ |   +5 very interesting! I think we can. However calculating for all the permutations might take a lot of time. I might try this some time afterwards
•  » » » » » 4 months ago, # ^ |   +5 218549633 bro did it lmao
•  » » » » » » 4 months ago, # ^ |   0 You can check out my code here: https://codeforces.com/contest/1859/submission/218544590 I got a $O(n^4)$ solution but it didn't pass so I just pre-computed it :)
•  » » » » » » » 4 months ago, # ^ |   0 very cool
•  » » 4 months ago, # ^ |   0 What is the O(N^2) idea?
•  » » » 4 months ago, # ^ |   +3 For task C the optimal answer is a permutation that is the identity permutation with some suffix reversed. For example, for n = 4 you have 1 2 4 3, so you can get an O(N^2) solution.
•  » » 3 months ago, # ^ |   0 Any idea how to solve C using dp?
 » 4 months ago, # | ← Rev. 2 →   +47 For task C the optimal answer is a permutation that is the identity permutation with some suffix reversed. For example, for n = 4 you have 1 2 4 3, so you can get an O(N^2) solution. https://codeforces.com/contest/1859/submission/218520660
•  » » 4 months ago, # ^ |   +86 Hardest part is to prove that
•  » » » 4 months ago, # ^ |   +53 there exists an easy proof strategy called "proof by ac"
•  » » » » 4 months ago, # ^ |   +74 "It's easy to show that..."
•  » » » » » 4 months ago, # ^ |   +43 "... this solution is correct because it passed pretests"
•  » » » » 4 months ago, # ^ |   +5 That is called "verification"
•  » » » » » 4 months ago, # ^ |   +42 stolen meme
•  » » » 4 months ago, # ^ |   +12 I lost 30 minutes proving it
•  » » » » 4 months ago, # ^ |   0 Could you tell it to us, please?
•  » » » » 4 months ago, # ^ |   0 Can you please share your idea how did you prove it.
•  » » » 4 months ago, # ^ |   0 can we prove why reversing only last two elements will not work ?
•  » » » » 7 weeks ago, # ^ |   0 Use case n=10. Does not work. $\square$
•  » » » 4 months ago, # ^ |   +31
•  » » 4 months ago, # ^ |   0 I wrote a solution in O(N * logN) I don't know why it works, but it worked https://codeforces.com/contest/1859/submission/218544583
 » 4 months ago, # |   0 Damn, I've figured out how to solve problem B, but still didn't get it right. My solution have no difference between the one in the tutorial, but for some reason it failed on pretest 4.
•  » » 4 months ago, # ^ |   +9 Read about int and long long datatype in c++
•  » » » 4 months ago, # ^ |   0 Thanks for noticing. I didn't consider the sum being greater than 10^9. Spent last 30 minutes debugging the solution when the answer was out there.
•  » » » » 4 months ago, # ^ |   0 same
•  » » 4 months ago, # ^ |   0 I think, use long long, the sum can excess int
•  » » 4 months ago, # ^ |   0 In my opinion,I always use #define int long long so I don't need to care that I use int or long long.
•  » » » 4 months ago, # ^ |   +1 i think it's not a good practice
 » 4 months ago, # |   0 Where is precalc in author’s solution of the problem C???
•  » » 4 months ago, # ^ |   +9 Do you really need a precalc when you have an $O(n^3)$ (or even $O(n^2)$ for most of participants) solution???
•  » » 4 months ago, # ^ |   0 $\sum n\le500$,so $O(n^3)$ can solve it.As the result,you needn't use precalc.
 » 4 months ago, # |   +5 Very entertaining round keep it up :)
 » 4 months ago, # | ← Rev. 4 →   +19 I found C through pattern:The solution is always in form: 1, 2, 3, ... k, n-1, n-2, ..., k+1 I didn't prove this, does somebody have an idea why this happens? Sol is trivial O(N^2)
•  » » 4 months ago, # ^ |   +7 the stream is proving the statement uwu
•  » » » 4 months ago, # ^ |   0 yes, in the alternate sol
•  » » 4 months ago, # ^ |   +1 This pattern was so not obvious. Almost gave up on C but then decided to loop through every permutation(next_permutation) for n=10 to see what permutation gave 303 and the pattern was there clear as hell.
•  » » » 4 months ago, # ^ |   0 same, the bruteforce was so obvious i just tried it to look for patterns (also i couldn't find the solution for 10)
•  » » » » 4 months ago, # ^ |   0 I actually wrote a program to see for n=10. Was so demotivated by C that couldn't even brute force myself for n=3, 4. 10!=3628800 permutations=3e7, so I could go through all permutations in order of 1e7 operations and find the one which has it's answer 303.
•  » » 4 months ago, # ^ |   +1 initial permutation :- 1 2 3 4 ... nk = 1 to n let say you want to change positions only in last n-k (may be not all also). so permutation will be 1 2 3 ... k — — and now we need to find for what position of other numbers (k+1 to n) will we get max ans ; if we minimize the max value then remaining sum of values ( k+1 to n positions ) become larger and ans will be max .let say n is at position a and n-1 is at position b . if a > b ==> abs(n*a — (n-1)*b) > abs(n*b — (n-1)*a) . As we want all numbers(k+1*val at k+1 to n*val at n) to be closer to each other we give b position n and a to n-1.By considering all possible pairs 1 2 3 4 -- k n n+1 — k+1 gives the max ans when only we want to make changes in last n-k positions iterate this for k = 1 to n.
 » 4 months ago, # |   0 Thanks for fast editorial!The nice round really activated my dull brain!Although I did not solve the problem D and E, the quality of the problems is really high.
 » 4 months ago, # |   0 How can problem C be solved with dp???
•  » » 3 months ago, # ^ |   0 same question :D i'm struggling to find out the solution :)
 » 4 months ago, # |   +48 Just calculate everything, put all in a list and print and print
•  » » 4 months ago, # ^ |   +33 Bruteforcing all permutations of 250 elements goes brrrr
•  » » » 4 months ago, # ^ |   +3 No it's impossible as 12! is already 479001600, which is very large, we need to realize this. Then brute force for a permutation takes O(n^2) time.
•  » » » » 4 months ago, # ^ |   +33 Bruh why do we need the table then?
•  » » » » » 4 months ago, # ^ |   0 because I had been generating 10 first permutations and realize the pattern, so I pre-calculate all and submit then pray for luck, luckily it's Accepted lol
•  » » » » » » 4 months ago, # ^ |   +23 Couldn't you submit the program that calculates answers instead of the table?
•  » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 you can visit my profile and look at my submission for C, it still have the precalc part
•  » » » » » 4 months ago, # ^ |   +27 Bro had to calculate answers by hand.
•  » » » » » » 4 months ago, # ^ |   -8 yes, to be honest I don't like this way, it makes me have feeling of cheating. But I couldn't think of proper way, so I had to do like this, isn't it a wise choice :)
•  » » » » 4 months ago, # ^ |   0 Yes but $t\leq{30}$
•  » » » » » 4 months ago, # ^ |   0 I'm telling that generate all permutation is impossible, not O(n^2) is not good enough
•  » » » 4 months ago, # ^ |   0 It is not possible as 250!=3.2328562609E492
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 How i understand he write O(n ^ 4), but not the O(n!)
•  » » 4 months ago, # ^ |   +13 What if we use 100% of our brain:D
•  » » 4 months ago, # ^ |   +14
•  » » » 4 months ago, # ^ |   0 you could become a Grandmaster ;)
 » 4 months ago, # |   +1 Task D: "We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum. ... We notice that to solve this problem, we can use the std::multiset} container, which automatically sorts elements in ascending order."Which other structures can be used to solve this? (preferably easy to implement)Golang doesn't have a built-in multiset. I tried to use a priority queue, but couldn't find a version that supports removing some element by index.
•  » » 4 months ago, # ^ |   0 In problem D, I only use vector. You could consider to see my solution submission
•  » » » 4 months ago, # ^ |   0 Never thought it could be solved so easily. Thanks man.
•  » » » 3 months ago, # ^ |   0 that's helpful, thanks!
•  » » 4 months ago, # ^ |   0 I used stack for problem D
•  » » » 4 months ago, # ^ |   0 Can you elaborate?
•  » » » » 4 months ago, # ^ |   0 So if I have an array of segments and we want to merge the intersecting segments together, I can sort the array of segments according to it’s first element, then I push each segment into a stack, either it intersects with the top of the stack, then I merge them together, or it doesn’t and then I just push it as another segment into the stack. Though I think using a vector would be better for this problem.
•  » » » » » 4 months ago, # ^ |   0 Yeah I used vector to merge intervals it worked quite well, Thankyou.
•  » » 4 months ago, # ^ |   0 You can simply use vector of pairs, and then a map.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 even no map is required only vector you can see my submission 218580178
•  » » » » 4 months ago, # ^ |   0 Okk
•  » » » » » 4 months ago, # ^ |   0 sorry bro
•  » » 4 months ago, # ^ |   +1 Solution using only vectors (slices in Go) in a couple of words: 1. From l, r, a, b we build segment l, b and add such pairs to slice as a segment 2. Sort the segments by start coordinate 3. Use scanline to get union of segments as a new set of segments (which is already sorted as well) 4. For each query use binary search (sort.Search is very convenient in Go) on this new set and if the point is inside a segment, then the answer is the end coord of this segmentHere is the solution in C++, which is easily convertable to Go: https://codeforces.com/contest/1859/submission/218541082
•  » » » 4 months ago, # ^ |   0 could you please explain what "scanline" is in brief? I'm finding it difficult to understand why we're processing l, r, b in a particular order (not necessarily in that order). Thanks in advance
•  » » » » 3 months ago, # ^ |   0 scanline is an popular algorithm, you can do bit research about it.. as far as this solution for d problem is concerned, it is the first thing that came to my mind.. you just need to see how we can move from a (b) point of 1 segment to any of the (b) point that lie on right of it.. l,b for each segment is the only required thing.. based on that you can decide from this (b) point which (b) point on right you can go.. so you can also think of it as DSU as if you can go a->b and b->c, it means you could directly go a->c.. so we club all segment to get rightmost reachable point..
•  » » 4 months ago, # ^ |   +1 You don't need any fancy data structures to solve D. You just need to be able to sort the portals with respect to b 218826757, and thats about it.
•  » » » 2 months ago, # ^ |   0 Could you explain the reasoning? Or maybe someone else?
 » 4 months ago, # | ← Rev. 3 →   0 problem C can be solved in N2 approach, but it takes N(logN)^2 for average case.check out my submission.
 » 4 months ago, # |   0 Problem C can be done in linear time as well. Notice the ans is always of the Patten 1,2,3...k, n, n-1, n-2...n-k type. For example, for n=10, it is 1 2 3 4 5 10 9 8 7 6. So just try all such for given n and return maximum. I wonder why constraints where so low. With above approach, we can easily solve for higer N also.****
•  » » 4 months ago, # ^ |   +17 Is there a proof for it?
•  » » 3 months ago, # ^ |   0 how linear time? How do you find k without iterating N times?
 » 4 months ago, # |   0 Minus delta :(. Btw fast editorial.
 » 4 months ago, # |   0 thanks for editorial!
 » 4 months ago, # | ← Rev. 2 →   0 what is correct ans for this test case for problem b ? 8 1 1 2 2 3 1 4 2 5 6 1 7 2 8 9 1 10 2 11 12
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Do you mean 1 8 1 1 2 2 3 1 4 2 5 6 1 7 2 8 9 1 10 2 11 12 or just 8 1 1 2 2 3 1 4 2 5 6 1 7 2 8 9 1 10 2 11 12?for first, the condition says that m>=2 and is an incorrect test case. Secondly, not enough numbers.I think the problem with your code int answer
•  » » » 4 months ago, # ^ |   0 yes is find out that my made test case is wrong.
 » 4 months ago, # |   0 Problem C can be solved in O(n^2). The idea is to reverse some suffix of the sorted permutation and finding which gives maximum power. 218547871
•  » » 4 months ago, # ^ |   0 Try to prove that)
 » 4 months ago, # |   +26 pattern recognition forces
•  » » 4 months ago, # ^ |   0 Nah only C was pattern (and it was also unintended, the actual solution looks very legit)
•  » » » 4 months ago, # ^ |   0 Yeah, I agree it was a good problem
 » 4 months ago, # |   0 lately i am not doing good against problem B, but thanku for c.
 » 4 months ago, # |   0 Problem C can be solved in O(n^2+t*n).We can preprocess an array first and calculate it easily. My English is a little poor. You can see https://codeforces.com/contest/1859/submission/218569933 .
•  » » 4 months ago, # ^ |   0 So not only n can be larger, but t can also be larger.
•  » » 4 months ago, # ^ |   0 Can you prove it is correct?
 » 4 months ago, # | ← Rev. 5 →   +21 My solution to the problem D (it can be easier to understand for someone).First of all, we can use only $l_{i}$ and $b_{i}$ ('cause it is always beneficial to teleport to point $b_{i}$, and we do not really need to teleport to the point $b_{i}$ from the right)So let's say we have got $n$ segments $l_{i}, b_{i}$. If two segment intersect each other we can squeeze them (we can do it by using simple stack)After we squeeze all of the segment for each $x$ we just have to find the segment with the biggest $l$, which is not bigger than $x$ (we can do it by using binary search). After finding the segment the answer for $x$ will be max (x, $r_{i}$).It takes $O((q+n)log(n))$ time.btw, thanks for the fast tutorial!
•  » » 4 months ago, # ^ |   +1 I do the same .I think this is the best soln that can be possible After reliazing that [l1..b1] range is sufficient , its rating is like div2B :))
•  » » 4 months ago, # ^ |   0 yup , I did this same way submission
•  » » 4 months ago, # ^ |   0 What if a,b is not inside l,r
 » 4 months ago, # |   0 still waiting on someone to prove why th does 1 2 3 k n-1 n-2 k+1 solution for C works i just noticed it while using next permutation and find the biggest possible answer
 » 4 months ago, # |   0 Can anyone tell me some better approach for C? My Submission — https://codeforces.com/contest/1859/submission/218546334
 » 4 months ago, # |   0 I love this Round. Because I can learn a lot from it. Thank you!
 » 4 months ago, # |   +5 Are questions like c really relevant . Meaning which ability of ours is it testing.
 » 4 months ago, # |   +6 The time limit was very strict for Problem D it seems.. Another nlog n solution with lazy segment tree got TLE... https://codeforces.com/contest/1859/submission/218564665 :-(
•  » » 4 months ago, # ^ |   0 I solved it with segment tree as well and I get TLE on test case 9 though without lazy. If I added lazy I would also have the same result as you. I agree with you this was very strict. Maybe the author didn't even notice that there is a solution with segment tree. What would have been most optimal would be to split this task into 2 parts one getting 1500 points and the other 250 points and just say that the time limit is the only difference. Put 3 seconds on the easy version and 2 seconds on the hard version. If I have done all the correlation steps to achieve O( NlogN + QlogN ) complexity why should I get a big fat 0?
•  » » » 4 months ago, # ^ |   0 yea correct.. seems the author and tester didnt notice the segmentree solution.. the code passes in g++20 actually.. :-(
•  » » » » 4 months ago, # ^ |   0 Like if they put the limit to be 3 seconds I don't see how a quadratic solution would pass anyways... It's a bit ridiculous if you ask me how they came up with 2 seconds as the time limit. I guess they just timed their solution and that was it.What's even more pitiful is that it doesn't really take much skill to switch from a segment tree solution to a PQ solution for this problem. It's the same observations that you need to make essentially and simply apply them using the respective container.But in any case: This can be a lesson for both you and me to always1) Check first if a segment tree solution can be easily changed to a PQ or iterative seg tree one. 2) Always submit as g++20 since we have already seen in many cases where the same code passes in g++20 and not in previous compiler versions.
•  » » 4 months ago, # ^ |   +12 Hi! Sorry that this happened, we did not want to cut off such solutions. One of our testers passed two segment trees, one with lazy operations and one without, so we thought that the TL was OK.I will try to be more lenient with TL's from now on.
•  » » » 4 months ago, # ^ |   +3 i got tle with segment tree beats at first too, then changed to set but still got tle because for convenience i substituted an array for std::map??? complexity's still right but i got stuck for a long time...
 » 4 months ago, # |   0 Just wonder if it is code obfuscation 218587647
 » 4 months ago, # | ← Rev. 2 →   0 I found a StackExchange post (https://math.stackexchange.com/questions/4751863/maximise-sump-ii-maxp-ii-with-p-permutation-of-size-n) for the Problem C in O(n^2) time. There is no answer yet but it's worth looking at in a few days if no proof has been posted here.
 » 4 months ago, # | ← Rev. 2 →   0 can anyone has recursive dp solution of D?? ~~~~~ int g=-1; vector,pair>>v; const int N1=1e6+5; int dp[N1];//maximum distance for element at position N1; int ans(int n){ // int p=-2; if(g!=-1){ if(g==n){ return n; } } // base condition if(dp[n]!=-1){ return dp[n]; } for(int i=0;i,pair>p1=v[i]; pairp2=p1.first; pairp3=p1.second; if(n>=p2.first && n<=p2.second){ int x1=p3.second; if(dp[n]<=x1){ debug(x1); g=n; debug(g); dp[n]=max(dp[n],ans(x1)); } } } return dp[n]; } void solve(){ memset(dp,-1,sizeof dp); int n; cin>>n; for(int i=0;i>a>>b>>c>>d; pairp1,p2; p1={a,b}; p2={c,d}; v.push_back({p1,p2}); } int q; cin>>q; int i=0; while(q--){ memset(dp,-1,sizeof dp); int m; cin>>m; cout<
 » 4 months ago, # |   0 since the intended solution was O(N^3) for C, why didn't you just let O(N^3logN) pass, this is much more better than guessing stupid patterns.
 » 4 months ago, # | ← Rev. 3 →   0 Amazing contest! Problems were high-quality and fun to solve. Thanks to kristevalex, i_love_penguins, efimovpaul, induk_v_tsiane and all the other testers!
 » 4 months ago, # |   0 Can anyone help me with my solution of Task D I am getting TLE on test case 9 although my time complexity is qlog(n)??
 » 4 months ago, # |   +4 Thanks for the great round and nice hint based editorial !Here is my advice about the problems I solved: APerfect problem A! There is an idea, it is not an A + B problem. The statement is short. BPerfect problem B!! I think that creating a good B is extremely hard because it has to be easy to implement, there should be some idea that is not completely obvious but still a bit obvious... The problem is interesting and fun to solve! CThe problem by itself is cool but I think that the time limit is a bit too extreme. I came up with an $O(N^3 log(n))$ solution directly which got TLE so I spent 30mn optimising it to $O(N^3)$. I think it could have been better to clearly draw the line and ask for an $O(N^2)$ algorithm. I also think that it is an issue to have a problem with an ""easy"" pattern to guess. The solve count is very high and it is most likely because people guessed the pattern without proving it. The problem is still great but I think that such factors (is the problem guessable) should be considered, especially when setting a problem that everyone will read (if it was a "guessable" div2F, it would be fine because not that much people will actually try to guess it). I'm interested in the advice of other people about this problem. Maybe it is actually fine to have ""guessable"" problems, I don't know. DI find it very funny that this problem has a large variety of solutions ! I think that it is a bit standard but the problem is still enjoyable to solve and educative. I think that every round can have at most one or two such "educative" problems. What are your thoughts about this? EAgain, nice trick about handling |a — b|. It helps in a lot of other problems such as 1622E - Math Test so it's a problem that actually teach some "general" ideas which is great.
 » 4 months ago, # |   +94 Thanks for the contest! Feedback on the problems:A: Good easy problem.B: Fine easy problem.C: Decent problem; not terrible but not my favorite. I think the problem would have been better with a higher time limit--I don't think there's much risk of a brute force solution passing and I think it would have been better to clearly accept $O(N^3 \log N)$ rather than making its result implementation-dependent (my straightforward implementation gets AC in 2800ms without the optimization mentioned in the editorial). I could imagine using either ~5s or 1s, with 1s intended to clearly cut all solutions that don't optimize out the log factor. Especially because the slower solution requires some optimization to get AC, I don't love that there is also an $O(N^2)$ solution that seems pretty difficult to prove, since this pretty heavily rewards proofs by AC.D: Good problem, probably my favorite of the round. The observation that the containment constraint is helpful is pretty nice and the implementation is fairly straightforward from there. (The bonus task is also nice, and I thought about it in-contest when I didn't read the containment constraint--I could imagine including it as a harder subtask with a score distribution along the lines of 1500 + 2500, but I think excluding it is fine too.)E: Good problem; the absolute value maximization trick is a nice one for people who haven't seen it yet.I don't understand why my solution gets AC: see here for my in-contest solution and here for the solution I think is correct. The difference occurs in case 4; I think my current solution maximizes |A[l] — A[r]| + |B[l] — B[r]| instead of |A[l] — B[r]| + |A[r] — B[l]| when the interval we choose has length greater than one. I have no idea why this passes, but at the same time I don't immediately see a countercase (it's a bit harder because I correctly handle the case where the length of an interval is 1).My current theory is that the only two cases we need to actually consider are A[l] + B[l] — A[r] — B[r] and A[r] + B[r] — A[l] — B[l]; for the other two cases we could do better by splitting into smaller intervals. Indeed, this submission only considers these two cases and gets AC. If anyone has a proof of this, I'd be happy to see it; I'll also try to show that this holds myself later on.F: Fairly good problem. The implementation was a bit annoying, but that's hard to avoid unless you want to exclude this type of heavy-duty tree problem entirely.My one criticism of the statements is that I think "cost" should be replaced with "value" in C and E. Typically, we try to minimize a cost, so when I skimmed the problems and read the word "cost", I tried to minimize the answers rather than maximizing them for my first few minutes. I think it makes more sense to use cost for minimization problems and value (or e.g. score or similar) for maximization problems.Overall, though, I enjoyed the contest--thanks very much to the authors!
•  » » 4 months ago, # ^ |   +36 Geothermal Your intuition on E is correct! In fact, for the other two cases, you can do better by simply considering the singleton intervals at the endpoints. ClaimThe only two cases we need to actually consider (for intervals of size at least two) are $A[l]+B[l]—A[r]—B[r]$ and $A[r]+B[r]—A[l]—B[l]$. ProofWe can rephrase the claim as the only cases we need to consider are the "dually monotonic" ones: both $A[l]$ and $B[l]$ are bigger than (or equal to) both $A[r]$ and $B[r]$ both $A[l]$ and $B[l]$ are smaller than both $A[r]$ and $B[r]$ Suppose for a contradiction that there exists some optimal interval where the above doesn't hold and there is an "inversion". We will show that considering only the two singleton intervals at the endpoints gives equal or better value ($=2*|B[r]-A[r]|+2*|B[l]-A[l]|$). WLOG, $A[l]$ is the smallest element. Then there are 4 cases to consider: $A[l]<=A[r]<=B[l]<=B[r]$. In this case, the value is $(B[r]-A[l])+(B[l]-A[r])=(B[r]-A[r])+(B[l]-A[l])<= singleton$ $A[l]<=A[r]<=B[r]<=B[l]$. Analogous. $A[l]<=B[r]<=B[l]<=A[r]$. In this case, the value is $(B[r]-A[l])+(A[r]-B[l]) \leq (B[r]-A[r])+(B[l]-A[l])+3*(B[r]-B[l])+(A[r]-A[l]) = 2*(A[r]-B[r])+2*(B[l]-A[l]) = singleton$ $A[l]<=B[r]<=A[r]<=B[l]$. Analogous. CorollaryFor the only two cases that we now (provably) care about, both $|A[l] — A[r]| + |B[l] — B[r]|$ and $|A[l] — B[r]| + |A[r] — B[l]|$ are equivalent! So maximizing either gives AC :)
•  » » » 4 months ago, # ^ |   +9 Wow, that's cool. We did not notice this during testing, thank you very much for your insight!
•  » » 4 months ago, # ^ |   +15 Regarding E: We can show that if A[l] — B[r] >= 0 and A[r] — B[l] >= 0 (one of the mixed case from above), it is always better to use two singletons instead of using a single interval of length > 1. Label the four numbers A[l], A[r], B[l], B[r] as x1, x2, x3 and x4 according to their order, i.e. x1 <= x2 <= x3 <= x4. There are six ways to arrange them such that the inequalities hold. I will discuss 2 of them:  l r l r A: x2 x4 | x3 x4 | B: x3 x1 | x2 x1 | For the first case we have (cost of the interval on the left, cost of the singletons on the right):x2 - x1 + x4 - x3 <= 2x3 - 2x2 + 2x4 - 2x1because after simplification we have:0 <= x4 + 3x3 - 3x2 - x1For the second case we have:x3 - x1 + x4 - x2 <= 2x3 - 2x2 + 2x4 - 2x10 <= x4 + x3 - x2 - x1We can verify the inequality holds for all other cases in a similar way.
•  » » 4 months ago, # ^ |   +5 Thanks for the proofs, y'all! I forgot that the objective function is nonnegative in $k$, so I was trying to do something more complicated involving breaking the sequence into two parts whose union is the entire sequence. Using the singletons makes this very clean; nicely done!
 » 4 months ago, # |   0 What is the intended solution for problem $D$ without the constraint that the segments are contained?
 » 4 months ago, # |   +4 I solved problem C in O(n2) by 1, 2, 3, ..... n, n-1, ....., x. But idk how to prove it >:(, just wasted 1 hr.
 » 4 months ago, # |   +1 Thanks for the great contest, really enjoyed it. Hope I will turn green today :)
 » 4 months ago, # |   0 very nice round
 » 4 months ago, # | ← Rev. 4 →   +1 to Cdefine $k=n-\lfloor \sqrt{2n+1} \rfloor$for 1~k, $p_i=i$for k+1~n, $p_i=n+k+1-i$so C can be solved in $O(n)$
•  » » 4 months ago, # ^ |   +1 any proof you have for that?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +6 I just find the pattern by running my $O(n^2)$ program.
•  » » 4 months ago, # ^ |   +1 It seems to be correct,but i can't prove it.
 » 4 months ago, # | ← Rev. 2 →   0 Please help me find out why I get the wrong answer in B pretest 4 please don't downvote, I'm trying for hours but couldn't find why I get WA. Ok, so here is my code
•  » » 4 months ago, # ^ |   0 Note that due to the bounds given in the task, the maximum sum is about $25000 \cdot 10^9 \approx 2 \cdot 10^{13}$, which is outside the usual valid range for int (up to ~$10^9$).
•  » » » 4 months ago, # ^ |   +6 OMG, thank you so much. I'm new to C++, I used Python before and didn't have to worry about using ints or longs lol.
 » 4 months ago, # |   0 Can someone please explain how to do D using Disjoint set union?? Thanks!
 » 4 months ago, # |   0 Why my solution gives TLE on problem E.
•  » » 4 months ago, # ^ |   +1 Looks like you’re unnecessarily memset-ing the entire dp table every time instead of only up to N, which could be slow.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 I removed memset and did the same manually Accepted solution, why it works now? Can you please explain. Thanks btw. :)
•  » » » » 4 months ago, # ^ |   +10 Before you were filling the entire MAXN (3000) dp table everytime which is too slow, instead of filling only up to n for that test case
 » 4 months ago, # |   +8 Problem C can be solved in O(NlogN) too. If you look carefully at the given test cases, all the solutions are obtained through reversing a suffix of the sequence 1 2 3 4 ... n. So it was deducible that the best possible answer will have a certain suffix reversed, but which suffix ? For that I calculated value of (∑ni=1pi⋅i)−(maxnj=1pj⋅j) for all possible suffix reversed sequences. Here is a simulation for n = 11: For the array : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 :: 1015 For the array : 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 :: 1029 For the array : 1 2 3 4 5 6 7 8 9 10 11 12 15 14 13 :: 1040 For the array : 1 2 3 4 5 6 7 8 9 10 11 15 14 13 12 :: 1048 For the array : 1 2 3 4 5 6 7 8 9 10 15 14 13 12 11 :: 1051 For the array : 1 2 3 4 5 6 7 8 9 15 14 13 12 11 10 :: 1049 For the array : 1 2 3 4 5 6 7 8 15 14 13 12 11 10 9 :: 1040 For the array : 1 2 3 4 5 6 7 15 14 13 12 11 10 9 8 :: 1024 For the array : 1 2 3 4 5 6 15 14 13 12 11 10 9 8 7 :: 999 For the array : 1 2 3 4 5 15 14 13 12 11 10 9 8 7 6 :: 965 For the array : 1 2 3 4 15 14 13 12 11 10 9 8 7 6 5 :: 920 For the array : 1 2 3 15 14 13 12 11 10 9 8 7 6 5 4 :: 864 For the array : 1 2 15 14 13 12 11 10 9 8 7 6 5 4 3 :: 795 For the array : 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 :: 713 For the array : 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 :: 616 Notice that plotting the values (∑ni=1pi⋅i)−(maxnj=1pj⋅j) against the starting number(position) of the suffix reversed we get a Bitonic function!Thus all we needed to find was the beginning of the suffix for the largest answer, or more simply the bitonic point, which can be done in log N time using binary search.Here's my solution(218593697) for problem C.(I didn't even look at the time limit given and assumed it to be <= 1 second based on the constraints. Thus, spend unnecessary time on this optimized solution).
 » 4 months ago, # |   0 I was trying to solve problem D with dsu, but I was missing an important part of the algorithm. Can someone tell me if it's possible to determine does point X belongs to some of N segments in O(log N) or O(1). Thank you in advance
•  » » 4 months ago, # ^ |   +1 1) Yes, it can be done. Let's sort all segments $(l;r)$ with condition $l_{i} \le l_{j}$ for $i \le j$. Ok, now we can do this by binary search:Let's find position $i$ with maximum $l_i$ with condition $l_{i} \le x$. For all $1 \le j \le i$ now condition $l_j \le x$ is correct. Let's just find maximum value $r_j$ on prefix $[1;i]$, and if $r_j \ge x$ result is YES.2) In this problem, we have offline queries, we can create event-type algorithm to calculate answer for all values $x$ in $\mathcal{O}(n\log{n})$.
 » 4 months ago, # |   0 for problem D, I tried representing each portal as a vertex and then found all connected components in the resulting graph, which consists of edges between vertices with overlapping ranges. I couldn't get AC. Did anyone try using this approach and how did you do it? Thanks!
•  » » 4 months ago, # ^ |   0 I actually thought of this too and I also failed lol
•  » » 4 months ago, # ^ |   +19 Isn't graph will be too large? With $n$ vertex number of edges will be up to $\frac{n(n-1)}{2}$
•  » » 4 months ago, # ^ |   0 Since it can be observed that $r_i$ and $a_i$ are useless for each segment. I use $l_i$ to sort all segments($l_i; b_i$) and then use some kind of greedy to merge all intersecting segments. Then I only need to use binary search for each $x_i$ to find which segment is covering it.Although my approach isn't the same as yours, I hope it'll be useful for you. Here's my code:218556118.
 » 4 months ago, # |   0 C question can be solved in O(n) runtime. I noticed from the test cases that first, say k, elements of the permutation would be same as the index and the remaining n-k elements will be in reverse order of the remaining indices. i.e., the array will be 1,2,3,...,k-1,k,n,n-1,....,k+1. So we can just run a loop to see for what value of k the cost is maximized. As simple as that!
•  » » 4 months ago, # ^ |   0 Nice observation ,can anybody prove it?
•  » » 4 months ago, # ^ |   0 that's what almost all people did it is a O(n^2), because u have to check sum for every k which is O(n)
•  » » » 4 months ago, # ^ |   0 No it's O(n) only. For any k, you can write a mathematical expression for the sum of last n-k elements instead of looping through it. Also to find the max element, it will be the middle element of last n-k elements, which can be done in constant time. Check out my solution at https://codeforces.com/contest/1859/submission/218596825.
•  » » » » 4 months ago, # ^ |   0 is it possible for you to post a proper Mathematical proof for this series sum which then can be done in O(1) for every k.
•  » » » » 4 months ago, # ^ |   0 my bad, I didn't think about formula
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 yup I have solved it in O(n^2)
 » 4 months ago, # |   0 IN problem B shouldn't the minimums be moved to array with smallest difference between second smallest and its minimum element rather than to smallest second smallest element????????????????????????
•  » » 4 months ago, # ^ |   0 No. Consider the case with two arrays $[1, 3]$ and $[3, 4]$. Your solution would suggest moving minimums to the second array leading to arrays $[3]$ and $[1, 3, 4]$ with $\mathrm{score} = 3 + 1 = 4$.The correct solution would suggest moving minimums to the first array leading to arrays $[1, 1, 3]$ and $[4]$ with $\mathrm{score} = 1 + 4 = 5$ which is larger.
•  » » » 4 months ago, # ^ |   0 Yeah bro in your case the minimum is changing hmm yes don't know how they say it is the second smallest element but by seeing test cases even if someone moves to array with minimum element they are considered correct still any ideas to help it's second smallest element because I can see a set of cases
 » 4 months ago, # | ← Rev. 2 →   0 done
 » 4 months ago, # |   +5 For problem E, the editorial says "Now we can look at out dp states as a table, and notice that we recalc over the diagonal". Does this mean one must look for patterns, or is there a way to notice this recalculation mathematically? Thanks in advance!
•  » » 4 months ago, # ^ |   0 Basically, from dp(i,j) you are making a move to dp(i-1, j-1). Which is considered a diagonal move.
 » 4 months ago, # | ← Rev. 2 →   +16 We can use Centroid Decomposition to solve problem F in $O(n\log n\log w)$.Code: 218616904It works faster than the common solution(with LCA).
•  » » 4 months ago, # ^ |   +10 That is cool.It probably is due to the fact that the average centroid tree height is small, so you really do less operations constant-wise. Thank you very much for this cool submission!
 » 4 months ago, # |   +8 C can be done in O(1). It is a straightforward formula, that can be derived with a bit of paperwork. We can prove by induction that for every n, the max cost can be found by reversing the last 'k' digits while writing 1 to n in ascending order. Eg- 1 2 3 4 5 6 10 9 8 7{max cost case of n=10}. So if we consider the general case, cost = (1^2+2^2+...(n-k)^2)+{(n)(n+1-k)+(n-1)(n+2-k)....(n-k+1)(n)}-max((i from 1 to k)(n+1-i)(n-k+i)). max(i.e. the third term in above formula) can be calculated by AM>=GM. so the final expression of cost is cubic in terms of k, which is to be maximized by d(cost)/dk=0. thus we get a O(1) solution. you can check my submission to see the final formula{I don't know how to add the link}.
 » 4 months ago, # |   0 For problem D, there seems exists a $O(n)$ solution using dsu. Considering combining the interval $[l_i, b_i]$, and setting the ancestor of these elements to $b_i$. Consider 218626575.
•  » » 4 months ago, # ^ |   +8 Sorry for forgotting the time consumption of sorting, which costs $O(n\log n)$.
•  » » 4 months ago, # ^ |   0 Two intervals are combined in a single set if they overlap. Can you explain how to construct dsu(specifically union)? Since there are n intervals, I'm performing O(n^2) comparisons to check whether two intervals overlap and perform union.
•  » » » 4 months ago, # ^ |   0 Sure. The fact is that cheking for overlapping of intervals may be unnecessary. We can just combine these overlapped intervals in a single set, which means that all beginners in the set can reach to the right-hand side endpoint of the interval.
 » 4 months ago, # |   0 It was an awesome round !
 » 4 months ago, # | ← Rev. 2 →   0 Hey, here is my code for the problem E. The time complexity should be O(N*N), according to me. However, even if it is not the case, how can the program pass 21 tests and give a TLE on the 22nd test case? The passed cases already involve worst-case values (N=3000, K=3000).Please let me know where I am going wrong.
•  » » 4 months ago, # ^ |   +3 Your solution is O(N^3). In general you have N^2 states and the transition from one state to another is done in O(N) in your memo function. If N = K there are only O(N) visited states since i = k for each. That's why it works on other test cases.
•  » » » 4 months ago, # ^ |   0 Thanks
 » 4 months ago, # | ← Rev. 22 →   0 I am weak in mathematical notation. I have solved problem D but do not understand tutorial. I don't understand the mathematical notation of this line "Let ansi be the maximum coordinate we can reach while being on segment i, and let pj be the answer to the j-th query. Then we notice that the answer to query pj=max(xj,maxni=1ansi|li≤xj≤ri)". Can you please explain this part "pj=max(xj,maxni=1ansi|li≤xj≤ri)". Thanks in advance.
 » 4 months ago, # |   0 Why does this code take 1500 ms?
 » 4 months ago, # | ← Rev. 2 →   0 Can someone explain why i am getting run time error in problem D. 218670993
 » 4 months ago, # | ← Rev. 5 →   0 for problem A I'm getting this error wrong answer Integer parameter [name=l_b] equals to 100, violates the range [-1, 99] (test case 3) the code is in java 218508753 on test 3 I don't know how to tackle this typos situation and if anyone faces the similar or another type of problem in during the contest kindly share it along with the solution as you get corrected it, all the suggestions are welcomed kindly help me to solve this and similar type of problem so that I can't face anything related to this in future. SecondThread Kindly help me as you are long time Java userUPD — got the solution it's happening because I was using for each loop while traversing the list
 » 4 months ago, # |   0 How 2 prove my C's solution? QAQ Just enumerate every i from 1 to n, flip the last k numbers of an ascending sequence of 1 to n, compute each answer and arrive at the maximum value, the final answer.I don't understand why it's correct even I Accepted D:
 » 4 months ago, # |   +6 Here is a sketch of why the faster solution to C works:First, consider permutations $1$, $2$, $\ldots$, $y-1$, $n$, $n-1$, $\ldots$, $y$. In this case, the answer is basically $1/12 (2 n^3 + 6 n^2 y - 3 n^2 - 6 n y^2 + 6 n y - 2 n + 2 y^3 - 9 y^2 + 4 y)$, the maximum occurs at around $y=n+1.5+\sqrt{2n+1}$, or $y=n+1-\lfloor\sqrt{2n+1}\rfloor$.Let $x$ be the maximum of $jp_j$. Then, $ip_i\leq x$, $i\leq n$, and $p_i\leq n$ implies $i+p_i\leq n+\frac xn$. Let $C=n+\left\lfloor\frac xn\right\rfloor$. Consider the largest possible value of $\sum_{i=1}^n ip_i-x$ over all permutations satisfying $i+p_i\leq C$. By the observation in the editorial (local swapping arguments), the maximum occurs when $p_1=1$, $p_2=2$, $\ldots$, $p_{C-n-1}=C-n$, $p_{C-n}=n$, $\ldots$, $p_n=C-n$. In this case, we compute $\sum_{i=1}^nip_i-x\leq\frac16 (n^3 + 3 n^2 y - 3 n y^2 + 6 n y - n + y^3 - 3 y^2 + 2 y)-ny$ where $y=C-n=\left\lfloor\frac xn\right\rfloor$ since $ny\leq x$. This is less than the construction given above when $y\leq n-2\sqrt n$. When $y>n-2\sqrt n$, the optimal permutations are very easy to characterize: since the part of the hyperbola $ip_i\leq x$ where $1\leq i\leq n$ and $1\leq p_i\leq n$ is very close to a line with slope -1, you must have $p_1=1$, $p_2=2$, $p_a=a$, $p_{a+1}=b$, $p_{a+2}=n$, $p_{a+3}=n-1$, $\ldots$, $p_{a+1+n-b}=b+1$, $p_{a+2+n-b}=b-1$, $p_{a+3+n-b}=b-2$, $\ldots$, $p_{b-1}=a+n-b+2$, $p_b=a+1$, $p_{b+1}=a+n-b+1$, $\ldots$, $p_n=a+2$, which is easily verified to be optimal in the equality case above.The details are left to the interested GM.
•  » » 4 months ago, # ^ |   0
 » 4 months ago, # | ← Rev. 2 →   +5 Hii, guys I am new to codeforces, can anyone please guide me why my sol failed on 4th pretest even though i used same aporach as author?Link to sol — Your text to link here...int main() { int n; cin>>n; for(int i=0;i>n_arr; vector v; for(int j=0;j>sz; for(int k=0;k>tp; temp.push_back(tp); } sort(temp.begin(), temp.end()); v.push_back(temp); } vector abc; int mn = v[0][0]; for(int j=0;j
•  » » 4 months ago, # ^ |   0 Corrected You need to take the final sum as long long
 » 4 months ago, # | ← Rev. 2 →   +3 O(log n) solution of C log factor is due to sqrt218710354
 » 4 months ago, # |   0 How my $O(n^4)$ solution passed in C?
 » 4 months ago, # |   0 can anyone explain the statement of problem B?
 » 4 months ago, # |   0 For Problem E, had the problem ask for the minimum instead of maximum, is it still possible to solve it given the constraints? Maybe I'm missing something obvious.
 » 4 months ago, # |   0 in question d, there's a hint use scanline, I'm hearing this term for the first time, can anyone explain what it is?
 » 4 months ago, # | ← Rev. 5 →   0 I'm attempting a proof for the C solution using pattern: $1,2,3,4, ... , x−1,n, n−1,n−2, ... , x$.Please feel free to comment/add/correct/improve.1.If $n$ is paired with $x$, then $x$ is paired with $n$. ProofSuppose $n\rightleftharpoons x$ and $n\rightleftharpoons y$ pairs exist, and $x$>$y$. The answer can be improved by swapping $n\rightleftharpoons y$ pair with $x\rightleftharpoons ?$ pair to give $n\rightleftharpoons x$ and $y\rightleftharpoons ?$.Applies to the largest mixed-paired number, so not just $n$. This cuts out a lot of permutations.2.Pairings do not cross. ProofIf $a \rightleftharpoons b$ and $c\rightleftharpoons d$ pairings exist, then the range $(a,b)$ does not overlap with $(c,d)$.Proof by comparing possible combinations. Can always better the crossed pairings. A bit messy.3.If $n$ is paired with $x$, then $n-1$ has to be paired with $x+1$ (if $n-1>x+1$). ProofGiven 1&2 above, $n-1$ has to be paired with a number larger than $x$. Suppose $n-1$ is paired with $y>x+1$, then the numbers in range $(x,y)$ will be paired to themselves as any pairing amongst them will lower answer; furthermore, answer could be improved by pairing $n$ to $y-1$ instead of $x$.This can be extended to $n-2$ etc, if necessary. Of course, if $x$ is large, there might not be any need to pair $n-1$.To summarise, if the optimal solution contain pairing $n \rightleftharpoons x$, then the given pattern would be the best.
 » 4 months ago, # | ← Rev. 5 →   +7 jiangly's solution to problem C using DSU was also O(n^3) if not better. (I don't really understand amortised analysis at all). After fixing $M$ and noticing that the greedy strategy of giving the highest available position to the numbers $n,n-1,...,1$ (in that order) is optimal, he used DSU to build the permutation in linear time.For every n, the highest/rightmost position that satisfies that $p_i\cdot i$ will be $min(n,M/i)$.If this highest position is available, then the value of its parent(as in DSU convention) is going to be itself and we can simply put $p \in P$ to this position. After doing so, we update its parent as the preceding position (via the merge/union operation). Doing this has the effect that, for all future elements that could have theoretically taken this position, are nudged to take the preceding position instead until they do find an empty position.Overall, the idea was that we maintain the highest available position as the parent of the currently "formed" part of the permutation. So, whenever a theoretical rightmost position is pre-occupied, then the highest available position can be used up.Implementation details: Omit union-by-rank/size heuristic because we want a very specific type of union such that we make the preceding position (even if it had a rank/size = 1 only) as the parent of a position we just filled up.jiangly's submission 218527131my submission (if useful to anybody) 218844879UPD:: Afterthoughts, this is pretty much the same thing as the use of stack in the editorial. Complexity should be same/similar.
 » 4 months ago, # |   0 Why is this code giving TLE for Problem D. I used a different approach from the one given in the tutorial, but Time Complexity wise, it is still the same. I could optimise it as much as I could. Any thoughts?
 » 4 months ago, # | ← Rev. 3 →   0 O(N^2) solution for problem C. Link : SUBMISSION LINKIdea : We will go for the following pattern - n=6 6 5 4 3 2 1 1 6 5 4 3 2 1 2 3 6 5 4 1 2 3 4 6 5 1 2 3 4 5 6 We will calculate answer for each and take maximum.
 » 4 months ago, # |   0 why is the O(N^3) method in the tutorial of problem C iterate i from 1 to N? I'm literally confused ...
 » 4 months ago, # |   0 Can anyone explain the O(n^3) solution of problem C for me, I can't understand what the stack does there and can't figure out how it makes the time complexity to O(n) in the loop
•  » » 4 months ago, # ^ |   0 Hi!First we notice the solution which uses $std::set$, where we greedily pick the maximum available while iterating from $N$ to $1$.Now let's do the following — we say that we can pair each number $k$ from $1$ to $N$ with the following prefix: $[1; \lfloor\frac{mx}{k}\rfloor]$, where $mx$ is the current maximum which we are iterating over. We can notice that we always pair the number with the highest available — so, for each index $i$ we create a vector of numbers which "become available" for all indexes $k \leq i$. Then we just use stack to maintain all available elements in descending order.
•  » » » 4 months ago, # ^ |   0 thanks a lot
 » 4 months ago, # |   0 By any chance can we use binary search in C?
 » 4 months ago, # |   0 Can someone help me understand the optimisation in Que E?
•  » » 4 months ago, # ^ |   0 Hi!The idea is that $|x| = max(-x, x)|$, and we can use this to simply consider different cases of modulos instead of always doing it correctly.After that we use a simple vector to store the maximum sum.
 » 3 months ago, # | ← Rev. 3 →   0 hello ! my code for the 1st question "United we Stand passes the first test case" but for the second test case , it says "wrong answer Integer parameter [name=l_b] equals to 2, violates the range [-1, 1] (test case 2)" code is attached below : please help me out , I think my idea is correct but somewhere in the implementation , I seem to go wrong . ~~~~~import java.util.*;public class A_United_We_Stand { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while (t-- > 0) { int n = sc.nextInt(); int arr[] = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = sc.nextInt(); } Set set = new HashSet<>(); for (int num : arr) { set.add(num); } if (set.size() == 1) System.out.println(-1); else if (set.size() > 1) { Arrays.sort(arr); List list1 = new ArrayList<>(2); List list2 = new ArrayList<>(); for (int i = 0; i < 2; i++) { list1.add(arr[i]); } for (int i = 2; i < arr.length; i++) { list2.add(arr[i]); } System.out.print(list1.size() + " " + list2.size()); System.out.println(); for (int i = 0; i < list1.size(); i++) { System.out.print(list1.get(i) + " "); } System.out.println(); for (int i = 0; i < list2.size(); i++) { System.out.print(list2.get(i) + " "); } System.out.println(); } } }`} ~~~~~
 » 3 months ago, # |   0 Guys I want some friends with whom I can do cp, So, if any one who loves problem solving we could somehow connect.
 » 3 months ago, # |   +8 in D I did binary search + dfs (also it's kinda dp)
 » 3 months ago, # |   0 It's obvious that we can soolve this problem by O(1) ，with no local calculate in my code. Here's my submission: this..By the way, how I can use LaTeX when writing comment in cf?
 » 3 months ago, # | ← Rev. 2 →   0 Can anyone prove why reversing the preixes and checking the max works in Problem C