### TheScrasse's blog

By TheScrasse, history, 4 months ago,

The official implementations of all the problems are here.

Timeline of the round proposal (may contain spoilers)

1909A - Distinct Buttons

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

1909B - Make Almost Equal With Mod

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909C - Heavy Intervals

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909D - Split Plus K

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909E - Multiple Lamps

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1909G - Pumping Lemma

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

1909H - Parallel Swaps Sort

Author: TheScrasse
Full solution: Endagorion, errorgorn
Preparation: TheScrasse, franv

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Hint 10
Hint 11
Hint 12
Solution

1909I - Short Permutation Problem

Author: TheScrasse
Full solution: errorgorn
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
• +354

 » 4 months ago, # |   +13 Thanks for the fast editorial!
 » 4 months ago, # | ← Rev. 2 →   -81 del
•  » » 4 months ago, # ^ |   +7 Wrong.
•  » » » 4 months ago, # ^ |   0 gcd * 2?
•  » » » » 4 months ago, # ^ |   0 Wrong (I tried it)
•  » » » » » 4 months ago, # ^ |   0 Sort the array and take the GCD of the difference of consecutive elements, then multiply it by 2.AC Submission : 238522780
•  » » » » » » 4 months ago, # ^ |   0 Hi, can you please explain the logic behind the code ? specifically the gcd of differences and multiplying it by 2 part.
•  » » » » » » » 4 months ago, # ^ |   0
•  » » » » » » 4 months ago, # ^ |   0 I think we need not sort the array, directly taking GCD of absolute value of difference of consecutive element , then multiplying by 2, will be sufficient.
•  » » » » » » » 4 months ago, # ^ |   0 Oh, it's ok
•  » » » » » » 3 months ago, # ^ |   0 why the difference?
•  » » » » 4 months ago, # ^ |   0 gcd tried it its wrong
•  » » » » » 4 months ago, # ^ |   0 Hi I also saw a code of gcd*2Can you explain the proof/intuition of gcd*2?
•  » » 4 months ago, # ^ |   +7 Wrong for case :44 8 12 16
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 it is correct the answer will come out to be 8 =(4*2)
•  » » 4 months ago, # ^ |   0 51000 2000 7000 11000 16000
•  » » 4 months ago, # ^ |   +1 You have to check for all the powers of 2, i.e. 2, 4, 8, 16, 32 ... Proof lies in the bitmasking
 » 4 months ago, # |   +1 Thanks for the quick editorial. I will probably become expert in this round. Thanks.
•  » » 4 months ago, # ^ |   0 why do i see ur username in red and gradmaster on ur profile .. is it the problem with everybody else
•  » » » 4 months ago, # ^ |   +1 Because of the Christmas gift.
•  » » » » 4 months ago, # ^ |   -8 oh
 » 4 months ago, # |   0 Can someone explain why this solution receives TLE? I assumed that the time complexity would simply be O(nlogn): 238557809
•  » » 4 months ago, # ^ | ← Rev. 2 →   +53 That's because you've used upper_bound(r.begin(), r.end(), l[i]); instead of r.upper_bound(r[i]); The first one works in $O(n)$ and the second one in $O(log\;n)$ where $n$ is the size of the set. This is due to the fact that the first function is a generic function that works with any container and is guaranteed to work in $O(log\;n)$ only if the container supports random access (std::set doesn't support random access), while the second one is a specific function designed only for sets and is guaranteed to have good complexity. You can refer to the documentation in case you're confused:
•  » » » 4 months ago, # ^ |   0 Ah, unfortunate. Thanks for the insight!
•  » » » 4 months ago, # ^ |   0 I have basically the same code and I did use r.upper_bound, but I still get TLE: 238528720. Did I perhaps get constant factored?
•  » » » » 4 months ago, # ^ |   0 I think I did get constant factored :( Instead of storing the segment in a vector>, I removed this intermediate step and stored the length of the interval in a vector directly and it passed 238595993. I don't understand why this would impact the time factor; I thought this would only cost a bit more memory.
•  » » » » 4 months ago, # ^ |   +7
•  » » 4 months ago, # ^ |   +11 I think to find upper bound on set r, you should use r.upper_bound(x), not upper_bound(r.begin(), r.end(), x)
 » 4 months ago, # |   +3 I Feel so stupid for not getting B in an hour
 » 4 months ago, # |   -7 MathForce. All problems have math tags.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +12 idk why but pinely and codeton rounds are biased towards number theory and maths
 » 4 months ago, # |   0 Great round. Thanks for fast editorial
 » 4 months ago, # |   0 thanks for the fast editorial
 » 4 months ago, # |   0 238549718 why does my soln of B work?
 » 4 months ago, # |   +130 I have a different solution for H so I'll leave it here.Let's assume $N$ is even. Consider $N$ operations $(1,N),(2,N-1),(1,N),\cdots,(2,N-1)$. These operations reverse the whole permutation. For odd $N$, one can do similar operations.During this reversing process, every pair of numbers become adjacent at some moment. Therefore we can "insert" adjacent-swap operations to achieve the arbitrary-swap operation in the final array.The pitfall is that when we try to do multiple arbitrary swaps, they can interfere with each other during the reversing process. However, if the target permutation has a matching structure, there are no worries about interference.Then, remember that we can obtain any permutation by composing two appropriate matching permutations. Therefore by repeating the reverse-and-swap process twice one can sort the input permutation.The time complexity is $O(N)$ and it's better than the intended solution. However, the number of moves is $3N+const$ and it's worse than $2N$. I'm so glad that the author didn't ask me to optimize this constant. (By the way, I'm wondering if it's possible to achieve a better constant factor with my approach.)
 » 4 months ago, # |   +37 I solved B ..By getting gcd of all v[x]-v[x-1] and multiply it by 2
•  » » 4 months ago, # ^ |   +3 can you explain ,thank you
•  » » » 4 months ago, # ^ |   +4 first, every number % gcd would be same.second, if every number % (gcd * 2) would be same, then gcd will not be gcd, it should be at least 2 * gcd.
•  » » » » 4 months ago, # ^ |   0 can u pls explain in detail
•  » » » » » 4 months ago, # ^ |   +2 for example,7 10 16the gcd of the difference is 3So we know that after mod 3, they will be same. i.e. 1 1 1If we look at gcd * 2, i.e. 6. we can see the result would be 1 4 4. There could be only two elements in it. Also, if everything are still the same, then we must be have a wrong gcd in the first step.
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 got that tnx!!But how u got intuition of that solution
•  » » » » » » » 2 months ago, # ^ |   0 can you help me understand, why taking the gcd of difference works ?
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 nice explanation I want to add that this rule will help in understanding this approachif a % k == b % k then (a-b)%k==0
•  » » » » » » » 4 months ago, # ^ | ← Rev. 3 →   +18 Yes,This property is nicely applied in 1826B - Lunatic Never Content question if anyone is interesting in using this property to practice a task
•  » » » » 4 months ago, # ^ |   0 its not correct
•  » » » » » 4 months ago, # ^ |   0 it works when you do the GCD of the Difference Arrays only as mentioned in the main comment
•  » » » » » » 4 months ago, # ^ |   0 Oh I thought I made it clear. The gcd in my comment means the gcd mentioned in mostafaabdelaal_03's comment, which is the gcd of the difference.
•  » » » » » 4 months ago, # ^ |   0 Can you provide a case?
•  » » » » 4 months ago, # ^ |   0 Hello, Sorry if my doubt sounds dumb but I agree that everynumber%(gcd*2) won't be the same but how can you claim that those "not same" %(gcd*2)s will be "same" as there have to be exactly 2 numbers one would be those who are still %(gcd*2)==0 and the other ones who are not zero but how can you claim that the other ones who are not zero will be equal
•  » » » » » 4 months ago, # ^ |   +1 let's say every number mod gcd is x, i.e. a[i] = x + num * gcd for some integer numthen everything mod 2 * gcd would be either x, or x + gcd.This is because when num is even, a[i] % (2 * gcd) would be still x,when num is odd, a[i] % (2 * gcd) would be x + gcd
•  » » » » » » 4 months ago, # ^ |   0 Understood! Thanks for your time
•  » » » » » » 2 months ago, # ^ |   0 thank you for the explanation
•  » » 4 months ago, # ^ |   +1 i was trying a similar approach but got stuck...please explain
•  » » » 4 months ago, # ^ |   0 +1
•  » » » 4 months ago, # ^ |   0 +1
 » 4 months ago, # |   0 In problem D, when we are doing operations on a[i]and want to make it to "tar". You are just doing partitioning. Won't there be cases where we partition a[i] into y, a[i]+k-y, and then recursively do operations on both of them?
•  » » 4 months ago, # ^ |   0 Think about adding operation as ratios, and I can spread the total sum among all of the buckets I produce (from that ai) however I want.
 » 4 months ago, # |   +186 The amount of effort that went into this round is insane, the timeline doesn't really do it justice. Kudos to TheScrasse for never settling on anything less than perfect, and errorgorn for coordinating this extremely demanding set. This turned out to be one of the most quality rounds in my recent memory!
•  » » 4 months ago, # ^ |   +23 Thanks a lot for the solution of problem H! It's my favorite problem in this contest, but I don't deserve the merit because you've solved it :)
•  » » » 4 months ago, # ^ |   +3 That makes two of us for the favourite problem part. =) Coming up with a concept this interesting is surely worth of the problemsetter's merit. I was glad to contribute, and had much fun thinking about this excellent problem some more.
 » 4 months ago, # |   0 Thank you very much for fast Tutorial! I dream of seeing an analysis of the problem D. Thank you for this good round!
 » 4 months ago, # |   0 How to solve F1 with combinatorics?
•  » » 4 months ago, # ^ |   +17 A way to think of this is to maintain the invariant that the difference of p between consecutive elements in front of the ith element is correct and also to satisfy the current consecutive difference. Denote unallocated elements smaller than i as k. If we want to make a consecutive difference of 2, we must assign the current largest element in previous k-1 vacant place, and place any of other k-1 element in current place which is (k-1)*(k-1) ways. Note that placing the current largest element in front of ith element will not break the difference invariant. If we want to make a consecutive difference of 1, we can either put the current largest in the previous k-1 vacancy or place any of current k element in current place. This results in 2k-1 ways. As mentioned before, placing the current largest element in front of ith element will not break the invariant.
 » 4 months ago, # | ← Rev. 3 →   0 while (true) { int div = 0, ndiv = 0; for (int i = 0; i < n; i++) { // st.insert(a[i] % d); if (a[i] % d == 0) div++; else ndiv++; } if (div > 0 && ndiv > 0) { cout << d << '\n'; return; } // if (st.size() == 2) // { // cout << d << '\n'; // return; // } d *= 2; }why is not working when I keep the track of two distinct remainders using two variables instead of a set. the loop is running infinitely for some test case when I use the two variables.
•  » » 4 months ago, # ^ |   0 I had similar approach, got any idea why using set/map to check the size won't work?? i am still stuck with that part.
•  » » » 4 months ago, # ^ |   0 got it
•  » » » » 4 months ago, # ^ |   0 can you explain?
•  » » » » » 4 months ago, # ^ |   0 In your approach, number need not to be perfectly divisible by K.take one testcase where your code is failing. 2 3 1 so here answer is 4, but your code won't output anything. you just have to check if the two reminders are distinct or not. one need not to be equal to zero.
 » 4 months ago, # |   +6
 » 4 months ago, # |   +2 can someone please explain first three lines of solution of problem D ?
•  » » 4 months ago, # ^ |   0 let's forget array and assume that we have to deal with single element.if this element is greater than k say (k+x),now in one operation we have to find 2 number a,b such that a+b=(k)+(k+x), to reduce complexity of question we are doing this trick a+b=(k)+(k+x)=> (a-k)+(b-k)=(0)+(x)we don't care about final number we care about how many operation so we reduce all number by k so our operation changed in select number and break it such in two number such that sum is our x((k+x)-(k)). in short after reducing by k we don't have to deal with k;)
 » 4 months ago, # |   0 All the problems were great and overall the contest was very enjoyable to solve. Thank you for such a good round!
 » 4 months ago, # |   +8 Worst contest for me so far. Didnt solve any. For who wants to see pure pain:
•  » » 4 months ago, # ^ |   0 please explain why mine 238560256 is wrong. I cant get it
•  » » » 4 months ago, # ^ |   0 got it
•  » » 4 months ago, # ^ |   0 a countertest for 238559680?
•  » » » 4 months ago, # ^ |   0 Consider cases where x = 0. If a special point is at x = 0, y = 1, what does your logic do? What is it supposed to do?
 » 4 months ago, # |   0 Story timeline of the round was something new and quite interesting, I enjoyed it.
•  » » 4 months ago, # ^ |   0 You didn't participate
 » 4 months ago, # |   0 In question C I have a test case : 5 1 2 3 6 7 3 4 5 7 8 1 2 3 4 5 in which many got answer 14 and 18. according to me answer is 18 as 14 is not possible please comment on it.
•  » » 4 months ago, # ^ |   0 Will it be added to the system tests and the final standing will differ or will be ignored? TheScrasse
•  » » » 4 months ago, # ^ |   +20 That test case is invalid because the endpoints are not distinct.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Thanks for replying.
 » 4 months ago, # |   0 why my solution gives WA 238595753 in B. Got the logic but got stuck with WA. can anyone explain why this is happening??
•  » » 4 months ago, # ^ |   0 long long :(
•  » » » 4 months ago, # ^ |   0 Got it, actually I defined my map earlier, after that I used Macro for long long to int conversion ;)
 » 4 months ago, # |   0 Last Dance, gud taste m8.
 » 4 months ago, # | ← Rev. 2 →   0 This is my soln to the problem B: bool check(vi arr, ll num){ map m; loopi(0,arr.size()){ m[(arr[i]%num)]++ ; } if(m.size() == 2) return false ; return true ; } void testcase(){ ll n; cin>>n; vi arr(n); loopi(0, n){ ll x; cin>>x; arr[i] = x ; } if(n==2){ cout<<10<
•  » » 4 months ago, # ^ |   0 Your output on line 130 is 10 not 2.As a counter-example consider, a = [10, 20]
•  » » » 4 months ago, # ^ |   0 Thanks, I thought the problem was to do this for size(array) > 2, as an array of size = 2 would already contain distinct elements, but I ignored the fact that the question had mentioned "apply this operation exactly once" in it and not at most once. :(
 » 4 months ago, # |   +13 I was trying to find some cheaters of contest and found this...
 » 4 months ago, # |   +6 In the editorial of problem D(solution section),Shouldn't it be "replace y with x+y" instead of "replace x with y+z"
 » 4 months ago, # | ← Rev. 2 →   0 B in O(n): $\large 2^{ctz((a_1 \land \cdots \land a_n)\oplus(a_1 \lor \cdots \lor a_n))}$238596786
 » 4 months ago, # |   0 Amazing contest! Problems were fantastic. Thanks a lot for the round TheScrasse and all testers.
 » 4 months ago, # |   0 Can anyone explain the concept behind problem D.I didnt understand the editorial
•  » » 4 months ago, # ^ |   0 +1
•  » » 4 months ago, # ^ |   +1 Assume we create a new board $B$, on which for each number $x$ written on our original board (call it $A$), we write the number $x - k$ on $B$. Then, let's try seeing what our operation does. So, since $y + z = x + k \implies (y - k) + (z - k) = (x - k)$ (for the original board), and since we've written $y - k, z - k$ on our modified board instead of $x - k$, this gives the observation that on $B$, our operation just corresponds to replacing $x^{*}$ by two numbers $y^{*}, z^{*}$ such that $x^{*} = y^{*} + z^{*}$. Then, solving this reduced problem is pretty easy (for implementation purposes, just subtract $k$ from each element of $a$, and do the calculations on that itself).
•  » » » 4 months ago, # ^ |   0 Thanks for explaining.
•  » » » 4 months ago, # ^ |   0 Still I didn't understand it
 » 4 months ago, # |   -24 spoilers make the whole text unreadable
 » 4 months ago, # |   -34 writing complexity at the end of an editorial is cringe
 » 4 months ago, # |   0 problem B was really something...
•  » » 4 months ago, # ^ |   0 it was easy
•  » » » 4 months ago, # ^ |   0 can u explain editorial?
•  » » » » 4 months ago, # ^ |   0 well it is kind of obvious intuition you get once u see 2 distinct values modulo some k you think of 2 since only two values are possible however then you remmeber all values might be pair hence there is only one value and then this amazing idea gets to u about the next power of 2 which is 4 well since the numbers were allwith the same parity they have only 2 values possible (pair numbers possible values are 2 or 4 and impairs values are 1 and 3) and then again there is possiblity that they all have same value time to check 8 again only 2 values are possible, you can conlcude that the sol requires checking all powers of 2,genius,see this much easier than what the editorial makes it look like.By the way i just guided you trough how the logical thinking went in my brain
•  » » » » » 4 months ago, # ^ |   0 Thanks for the great explanation
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 How did you know it would work when all the values were odd?edit: nvm. you said that if they're all odd then they'll either be 1 or 3 after you mod by 4.
 » 4 months ago, # |   +13 TheScrasse How does the grader for H work?
•  » » 4 months ago, # ^ |   +20 Link to comment
•  » » » 4 months ago, # ^ | ← Rev. 6 →   +13 (Nvm, this is wrong if you run it on a decreasing array.)By the way, isn't the number of moves for the editorial solution actually bounded above by $3n/2$? Since the number of moves during the second phase is at most the number of Bs after the first phase, which is at most $n/2$ due to there being no two consecutive Bs and the last letter being an A.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 Also curious about these: Were you aware of a solution to H that made $3n$ operations before the contest? Or did the limits just happen to be large enough to allow that to pass? What was the original solution to H with $O(n\log n)$ operations?
•  » » » » 4 months ago, # ^ |   +10 H with $O(n \log n)$ operations sounds like a considerably more boring problem, as I believe you can simply simulate merge sort: suppose the right part starts at $x$, then you can use operations on $[x-1,x]$, $[x-2, x+1]$ etc to create a train of moving elements from right to left, and you remove elements from the train when they reach their final positions.Other than the very annoying implementation, H with $O(n)$ operations is a work of art :)
•  » » » » » 4 months ago, # ^ |   0 Hm, I don't fully understand. By merge sort, do you mean that given two sorted arrays on consecutive ranges, you can merge them into one sorted array? If you do operations on $[x-1,x], [x-2,x+1], [x-3,x+2], \dots$ then this will move some elements right to left over $x$ and others left to right over $x$. But how are you removing elements when they reach their final positions? What if there's some element in the middle of the train that you don't want to keep moving?
•  » » » » » » 4 months ago, # ^ |   0 Here's how I did it: imagine inserting just the rightmost element $a_i$ of the left half with $[x - 1, x]$ operations. $a_{i - 1}$ can trail behind two positions away for free simply by extending the segments to the left (skipping the first one). We stop the trail early if $a_{i - 1}$ doesn't need to go that far, and proceed to $a_{i - 2}$. Final case is if $a_{i - 1}$ needs land next to $a_i$, in which case we add one more swap at the end to achieve that.
•  » » » » » » » 4 months ago, # ^ | ← Rev. 4 →   0 I agree about $a_i$ and $a_{i-1}$, but what if $a_{i-2}$ and $a_i$ need to keep moving to the right but you don't want $a_{i-1}$ to keep moving to the right?It's true that $a_i$ must move at least as far right as $a_{i-1}$, but once you take into account the fact that $a_{i-1}$ must trail two spaces behind $a_i$ to move them rightward at the same speed, this is no longer true.
•  » » » » » » » » 4 months ago, # ^ |   +10 For $a_{i - 2}$ we can forget what $a_i$ does, and focus on operations moving $a_{i - 1}$. Since they don't want to swap, the same logic keeps applying.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +10 I was not aware of any linear solution other than the official one. I didn't put $2n$ as the operation limit to avoid spoilers. The original solution was "put the $n/2$ smallest elements in the left half of the array in $O(n)$ operations, then recurse". Some testers found the "merge sort" solution explained by ffao.
 » 4 months ago, # |   0 hints are very helpful,thanks for editorial
 » 4 months ago, # |   0 Can somebody please explain why my solution of problem C — Heavy Intervals does not work
•  » » 4 months ago, # ^ |   0 In test case l=[1,2,3], r=[10,12,13], c=[1,1,100] it's best to pair (3,10)*100, but in your solution c=100 is multiplied by 10
•  » » » 4 months ago, # ^ |   0 ty
 » 4 months ago, # |   0 Writing timeline of the round is very cool.
 » 4 months ago, # |   0 too much math and number theory
 » 4 months ago, # |   0 Very well written editorial! Excellent hints that actually do help a lot if we don't want to see the full solution. Thank you TheScrasse for the good contest and the great editorial.
 » 4 months ago, # |   0 problem D is very nice!
 » 4 months ago, # |   0 I solved problem B using random numbers.The submission:238551759.
 » 4 months ago, # |   +3 The subtasks of F is helpful for some but also misleading many participants including me :(anyways, good problems and good contest
 » 4 months ago, # |   0 In E, I only understand this phrase in the statement after reading editorial: If you press the button ui, you also have to press the button vi,(at any moment, not necessarily after pressing the button ui) It's my fault to not read it properly, and couldn't think that it is possible to press all buttons
 » 4 months ago, # |   0 Thanks for the editorial :)
 » 4 months ago, # | ← Rev. 2 →   0 Can someone please prove this If ai mod k=x , one of the following holds:ai mod 2k=x ; ai mod 2k=x+k ; problem B
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 This is not a proof but this might help in understanding more intuitively. consider this array A=[42,10,26]. let's write these numbers in the bit representation.(i will use term 'bit position k' which means kth bit from right). 42 = 101010 10 = 001010 26 = 011010let's take k=4 can you tell what will be A[i]%k for all i ,(where k=4) just by looking at bit representation?as 4 = 000100 A[i]%4 (for all i) is the number represented by all bits which lies on right side of set bit position.In our case we will take last two bits from every number and that will be the reminder. so we got '10' as last two bits from every number in array, hence A[i]%4 is 2 for every element. (NOTE: this is true only if we are taking k as some power of 2).using k=4, we got only one distinct element i.e. 2 let's do same thing for k=2*k. follow the same steps that we did for k=4 for k=8, we will get only one distinct element i.e. 2 for k=16, we will get only one distinct element i.e. 10now when k=32, the set bit position is 6. The bits for each number in A which lies on right side position of set bit are reminders. 42%32 is 01010 10%32 is 01010 26%32 is 11010for k=16 we got 42%16 = 1010 10%16 = 1010 26%16 = 1010see the transition in results from k=16 to k=32. Upto bit position 4 the reminder is same(which is 10) but when we did the mod operation for k=2*16 we got 5 bits. The new bit that we got will be either 0 or 1. If it is 1 we will add previous k(16 in our case) to the previous reminder, and if it is 0 we will get the previous reminder as it is. So we finally got 2 distinct values which are (previous reminder+previous k) and previous reminder as it is.
 » 4 months ago, # |   0 B was such a good question. Was stuck on the gcd approach for a while before realizing the pattern in the bits.
•  » » 4 months ago, # ^ |   0 Check my submission,i had different implementation you might find what you are looking for
•  » » 4 months ago, # ^ |   0 even I got stuck at the gcd approach , the answer would be 2*(gcd of differences of successive terms)
 » 4 months ago, # |   -10 Lot of mathematics, I feel they should also try not giving just mathematics. B was too hard for me,i never would have thought it that way.
 » 4 months ago, # |   0 In Problem D why the answer is -1 when we have both negative and positive in our array after applying the operation (a[i] = a[i] — k) ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 First, notice how the number of operations required to make the "shifted" array (as it is called in the editorial) have equal values is the exact same as in the case of the original array.Now, with that out of the way, let's establish some notations. We'll denote the first element in the shifted array with a1', the second element in the shifted array with a2' and so on. The final value will be val (after all the operations, the shifted array will have all its elements equal to val). The number of operation required to change the first element of the shifted array to val (which is the same as the number of operations required to change the first element of the initial array to val) will be written as nop1. For the second element it will be nop2 and so on.We will consider a shifted array with only 2 value, but the proof can be generalized.Notice that a1' is equal to (nop1 + 1) * val and a2' is equal to (nop2 + 1) * val. This means that we can write val with respect to a1' and a2':val = a1' / (nop1 + 1)val = a2' / (nop2 + 1)This means that:a1' / (nop1 + 1) = a2' / (nop2 + 1)At first glance it seems that this equality always holds true. However, notice how a1' and a2' can have any integral value but nop1 and nop2 can be only non-negative numbers (it doesn't make sense to have a negative number of operations). This means that this equality is valid as long as a1' and a2' have the same sign. The moment they have different signs, this equality doesn't hold anymore and val can not exist.On a side note, following the same rationale you can determine that val doesn't exist in the case where there are 0 and non 0 numbers in the shifted array.
 » 4 months ago, # |   +8 Alternative solution for E:Let's call a subset $S$ of pressed buttons good if at the end at most $\left \lfloor \frac{n}{5} \right \rfloor$ lamps turned on. For $n \leq 19$, the amount of such subsets is $\leq 1159$. We can find them for each $n \in [1, 19]$ in $O\left(\sum\limits_{n=1}^{19} 2^{n} \cdot n \log n\right)$, and then check only them for each $n \leq 19$ testcase in $O(nm + 1159n)$.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +33 Actually, you can prove that the number of such subset for $n = 19$ is exactly $\binom{19}{3} + \binom{19}{2} + \binom{19}{1} = 1159$ since we can think of each switch $i$ associated with a vector $v_i \in \mathbb{Z}_2^{19}$ and all the vectors are independent, so $v_1$, $\dots$, $v_{19}$ is the basis, and we only care when $\oplus_{j = 1}^k v_{i_j}$ has less than or equal to $3$ bits on (excluding the case it is equal to zero), so we get the above result.
 » 4 months ago, # | ← Rev. 2 →   0 In problem D could we have solved for the smallest x in x*k+ Sum of Ai which is divisible by x+n
•  » » 4 months ago, # ^ |   0 Consider the case $A = [1, 2, 3].$ In this case $x = 0$ is the best choice, which is incorrect.For only positive $x$ values, consider $A = [10, 10, 20]$ and $k = 10$. In this case smallest $x$ is $2$ that satisfies the condition, but you can't really make all numbers equal.
 » 4 months ago, # | ← Rev. 2 →   0 Can anyone help me with a simple test case for which my submission is wrong for C? It's the same logic as the above solutionhttps://mirror.codeforces.com/contest/1909/submission/238575783
 » 4 months ago, # |   0 I love long and clear explanations in math and number theory problems. thanks to errorgorn TheScrasse franv Endagorion and everyone who contributed.
 » 4 months ago, # | ← Rev. 2 →   0 In problem C, making small intervals is not the same as sorting the sequences of left and right endpoints and pairing the corresponding indices. Let, $u = L_1,L_2,...,L_n$ si obtained after sorting $l_1,l_2,...,l_n$ and $v = R_1,R_2,...,R_n$ is obtained after sorting $r_1,r_2,...,r_n$. Then the new intervals will be $[L_1,R_1], [L_2,R_2],...,[L_n,R_n]$.
•  » » 4 months ago, # ^ |   0 what are you trying to say ? can you explain a little more ?
•  » » » 4 months ago, # ^ |   0 What is the difference between the approach explained in the editorial and my approach?
•  » » » » 4 months ago, # ^ |   0 Your approach fails for $l = [1, 2]$, $r = [3, 4]$, $c = [1, 2]$. You claim that it's optimal to keep everything as it is, while the editorial makes $l = [1, 2]$, $r = [4, 3]$, $c = [1, 2]$ ($3$ is matched with the closest $l_i$, which is $2$). The picture "explains" why the second solution is better than the first.
•  » » » » » 4 months ago, # ^ |   0 Hi, I didn't understand the picture can you explain it once? what is the 3 and 5 and what the different colors represent
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 The red subinterval is the only one whose cost changes (from $5$ to $3$). In general, you want intervals with big cost to be as small as possible, so you let intervals with small cost "steal" subintervals from intervals with larger cost.
•  » » » » » » » 4 months ago, # ^ |   0 Thank you! Got it now.Also the symmetry case with Ci>Cj means we would just assign Cj to the first interval(instead of Ci in explanation) to have same condition where total cost does not increase(as interval with Ci cost is decreased and interval with Cj cost is increased)?
 » 4 months ago, # |   0 Hello, would be great if someone explained why the following idea for B does not workhttps://mirror.codeforces.com/contest/1909/submission/238648704I was thinking of the following test casesIt should seem to always be possible for k to be a single digit value unless all numbers are multiples of 10.If there are 2 distinct numbers for each last digit, k=10 is always a solution.If there are more than 2 distinct numbers for each last digit, we can iterate k=2-9 to find a value for which it works
 » 4 months ago, # |   0 learned a property of divion and remainder in binary form.Thank you
 » 4 months ago, # |   0 In problem E, What the following line does inside the check(int s) function of Jiangly's code 238527503 if (s >> u[i] & ~s >> v[i] & 1)
•  » » 4 months ago, # ^ |   0 If button $i$ is pressed, then s>>i will be $1$. This line is to check whether $m$ pairs are satisfied.
 » 4 months ago, # |   0 Thanks for interesting tasks. Little comments for authors. problems $B, D, F$ are really cool, because they can be solved without any algorithms with only a brilliant idea. Problem $C$. Maybe it was better to make more samples, because there were a lot of WA's and a lot of greedy solutions can pass example tests(but of course incorrect).
 » 4 months ago, # |   0 Problem E is kind of funny.I tried to use complicated graph algorithms but failed.And the official solution is cool!I love it!
 » 4 months ago, # |   0 Thanks for the fast editorial!
 » 4 months ago, # |   +10 I have another solution for problem G. It is easier than the intended one in my opinion, at least idea-wise. SolutionLet $d = m - n$. Fix any valid $x$, $y$ and $z$. Let's see what is going on closely. If $i = |x|$ then the substring $t[i, i + d)$ is $y^{k-1}$. In particular, it has period $|y|$ and for at least $|y|$ indices $j$, starting from $i$, the equality $t_j = t_{j+d}$ holds (because another occurrence of $y$ follows $t[i, i + d)$). Obviously, the opposite works: if, for some $i$ and $l$, the substring $t[i, i+d)$ is $t[i, i + l)$ repeated several times, and for all $j$ such that $i\leq j < i + l$ we have $t_j = t_{j+d}$, then this pair $(i, l)$ corresponds to a unique valid triple $x = t[0, i) = s[0, i)$, $y = t[i, i + l) = s[i, i + l)$, $z = s[i + l, n)$. We are going to find the number of valid $l$ for each $0\leq i\leq n$. The plan is the following. First, we find for how many first indices $j$ from $[i, i + d)$ the equality $t_j = t_{j+d}$ holds. This can be done for all $i$ in one iteration over string $d$ from right to left. Denote this number by $c$ (stands for common).After we established this, we will find the smallest $p$ (stands for period) such that $t[i, i + d)$ is $t[i, i + p)$ repeated $d/p$ times. Then the number of good $l$ for this $i$ will equal the number of $g$ such that $p\mid g\mid d$ and $g\leq c$, or, equivalently, the number of $g\leq c/p$ for which $g\mid d/p$.To find the period $p$, we will try to find it under the assumption that $p\leq d/2$, and if we fail, then $p = d$.Let's solve a subtask: given string $u$ of length $d$, find its period if it's at most $d/2$. Let $i$ and $j$ be any pair of integers that $0\leq i$, $j\leq d$ and $j - i = \lfloor d / 2 \rfloor$. Then the period is $\min(d, \mathrm{lcm}(\mathrm{tailperiod}(u[0, j)), \mathrm{tailperiod}(u[i, d))))$, where $\mathrm{tailperiod}(v)$ is the smallest $p$ such that $v$ is a prefix of the infinite concatenation of $v[0, p)$ with itself (it is like a period, except there may be some leftover, although also consistent with the periodicity). The proof is left as an exercise for the reader.To always have such pair of indices, let's find such periods for all $t[i, j)$ where $i$ is divisible by $\lfloor d/2 \rfloor$ and $j-i \leq d$. We can find them by running z-function for each substring starting at such $i$ of length $d$ (or till the end of $t$, whichever is shorter). Similarly, we can run z-function on similar substrings of $t$ reversed, which concludes this part of the solution.What remains is to be able to tell how many divisors of $g\mid p$ don't exceed some $c$, where $p\mid d$. I just generated all divisors for each $p\mid d$ beforehand, and solved this subtask using lower_bound. I suspect that it can be shown that $p$ in these queries first only decreases, then only increases, in which case we can re-generate the divisors every time it changes, which will be better than $\log$ per query.
 » 4 months ago, # |   0 In D, "Now, the operation becomes "replace x with y+z such that x+y=z+k⟹(x′+k)+(y′+k)=(z′+k)+k⟹x′+y′=z′ ". Therefore, in the shifted problem, k′=0" .I think it should be y+z = x+k instead of x+y = z+k.
•  » » 4 months ago, # ^ |   0 Fixed, thanks.
 » 4 months ago, # |   0 B, O(n * log(57)): https://mirror.codeforces.com/contest/1909/submission/238756149
 » 4 months ago, # |   +10 I can understand the solution of G now,but I've got no idea about how the vital observation "$(a,b)$ is valid then $(a+1,b+1)$ is valid if and only if $s_{b+1}=t_{b+1}$" was found.What inspired you think about that?Can someone help me?
•  » » 4 months ago, # ^ |   0 Actually, I only found it while preparing the problem (with constraints $n, m \leq 2 \cdot 10^5$). I was trying to build strong tests (where the valid $y$ of fixed length are not consecutive), but I ended up proving it's not possible.I'm curious about how actual contestants figured it out.
 » 4 months ago, # |   0 I see lots of people have doubts about why '2' in B,and I have difficulty in it too.Actually it's difficult to find 2 when in competiton for man who didn't cotact number theory.
•  » » 4 months ago, # ^ |   0 I can tell you how it worked for me. It is easy to get that if the array has even one even and odd number k can be taken as 2. Now the arrays left will have either all even or all odd numbers. For arrays with all even numbers, upon taking k as '2' the only value we get will be zero, but these might not all be divisible by '4' which forces us to think to take k as 4, which can yield two distinct values as zero and two, and again if this doesn't work we can keep on taking k as 8, 16, 32... For arrays with all odd numbers if we take k as 2, the only value we'll get is one, or the other way round if we remove 1 from all numbers again they all are divisible by 2, which again forces us to think that these all numbers(after one being removed from them) might not be divisible by 4, hence taking k as four can yield values as one if the number is divisible by 4 or yield as three if it's not divisible by 4, and again we can take 8, 16, 32...similarly until we get two distinct values.
 » 4 months ago, # |   0 can someone please explain with a proof how does subtracting k from every a[i] in problem D, effectively convert it into a shifted problem with k = 0? for all problems with k = 0, our job is to divide the sum of the numbers in the array into pieces which are all equal right? so i assume, we subtract k from the numbers in the original problem in order to reduce the sum. but since every time we do an operation we increase the sum of the numbers in the array by k, how does it guarantee that subtracting k from all the numbers lets us forgo this requirement, i.e. we subtract n*k from the original sum but it is not true that we have to do exactly n operations every time and hence subtract n*k from the original sum.i'm sure there is some misconception in my assumptions, if someone would be nice enough to point it out to me, it would be very cool. thanks for reading.
 » 4 months ago, # |   0 Can someone explain the intution behind problem C?
•  » » 4 months ago, # ^ |   0
•  » » » 4 months ago, # ^ |   0 Can you explain how the rearrangement inequality is related?
•  » » » » 4 months ago, # ^ |   0 I guess I actually do see how it is used in the problem (in sorting the cost array in descending order with the lengths), but that wasn't the hard part for me. The part that was hard was how to pick the elements l and r. I guess an intuitive explanation would be that you want to maximize the lengths so that you can pair a higher length with a a lower cost. To do that, for the smallest Rs, you want to pick and L that is the closest to them because you want to save the smaller Ls for the Rs that are larger, because that results in a larger lengths. I can elaborate more on this if anyone wants me to.
 » 4 months ago, # | ← Rev. 3 →   0 in problem c I'm trying to follow the editorial in the proof section he is saying at the third line If you swap ri and rj, the cost does not increase. I did that on the example n=2 provided and the cost increased from 6 to 7 first step he said match them any other order so: [2,4] [1,3] then he said You have also assigned some cost ci to [li,ri] and cj to [lj,rj] . [2,4] ci=2 [1,3] ci=1 now cost is 6 then ** If you swap ri and rj, the cost does not increase. ** swapping here will make the cost 7 so I don't get it can you please explain what is wrong here
•  » » 4 months ago, # ^ |   0 In the editorial, $c_i \leq c_j$. If $c_i > c_j$, you have to swap $l_i$ and $l_j$.
 » 4 months ago, # |   0 Can someone help me to explain the complexity of problem E plz?
•  » » 4 months ago, # ^ |   0 For each test case, you have to iterate over $O(n^{k-2}) = O(k^{2k-4})$ masks (in the worst case), and for each of them you can check if it works in $O(m)$.
•  » » » 4 months ago, # ^ |   0 I know how to prove $O(n)=O(k^2)$, but I don't know how $O(n^{k-2})$ comes out (especially $k-2$ power). Sorry for bad English expression.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +8 tl;dr replace $5$ with $k$ and $3$ with $k-2$ in the editorial.The largest solution to $\lfloor n/k \rfloor < \lfloor \sqrt n \rfloor$ is $n = k(k-1)-1$. In that case, you already have a solution which turns $\lfloor \sqrt{k(k-1)-1} \rfloor \leq k-1$ lamps on, so you can iterate over masks which contain $k-2$ lamps.
•  » » » » » 4 months ago, # ^ |   0 Thank you so much!
•  » » » » » 4 months ago, # ^ |   0 But here seems to be a little mistake? I suppose it should be "The largest solution to $\lfloor n/k\rfloor<\lfloor \sqrt{n}\rfloor$".
•  » » » » » » 4 months ago, # ^ |   +8 Yes, fixed.
 » 4 months ago, # | ← Rev. 2 →   0 Can anyone provide more proof on editorial of C? Why does the algorithm mentioned on the editorial works? More mathematical proof?
 » 4 months ago, # |   +3 For D, the shifting part is still unclear to me(ik what is being done ,but how is it correct and how to think of it) thnx in advance if someone can spare their time or share related resources
•  » » 4 months ago, # ^ |   0 I was really struggling for a while to come to grips with this solution and I think I am now (mostly) convinced of why it works, so I'll try to explain my way of thinking about it.Imagine a number line with numbers x, y and z marked such that y + z = x + k.Now think about the operation you can do: y + z = x + k. Going back to the number line, what this operation means is you would have to pick x and move it k unities to the right, then pick two numbers x and y such that their sum "lands" in (x + k) and not x. For each of those three numbers now, mark in the number line its value shifted k unities to the left, and call these new guys x', y' and z'. Clearly you can represent x by (x' + k), y by (y' + k) and z by (z' + k). So, looking again at our operation, we have (y' + k) + (z' + k) = (x' + k) + k -> y' + z' = x'. What that tells us is that if we had a magical way of taking every number on our line and shifting it k unities to the left, when we would execute the operation on an original number x, instead of doing that complicated process (moving it k unities to the right and only then finding numbers which add to it), we could map x to its representation in the shifted "world" and find two other numbers, also in the shifted world, such that their sum is equal to the representation of x. Our magical way of doing this shift is simply to take every number given in the input and subtract it by k. Now, for every operation we do in those numbers (including gcd), we are working with numbers from our shifted world; so we can now solve the problem as if k didn't even exist. Hope this is helpful in some way :)
 » 4 months ago, # |   0 clear proof for CDisjoint intervals are okay.But choosing between overlapping and intersecting intervals, it turns out that overlapping intervals give a smaller ans.Checkout the writeup.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 that was very helpful
•  » » 4 months ago, # ^ |   0 Now I finally understand the proof. Thanks!
 » 4 months ago, # |   0 can someone give the intuition behind the idea of "shifted problem" for D ? is it a trick or just random manipulation for this specific problem
 » 4 months ago, # |   0 Can someone tell the error in this code for Problem C: https://mirror.codeforces.com/contest/1909/submission/239092120
 » 4 months ago, # |   0 In D you can also do the reverse problem: Start at the final state which is a bunch of identical elements then apply "combine and subtract $k$" operations and arrive at a similar solution with algebra.
 » 4 months ago, # | ← Rev. 2 →   0 Just posting the snippet I took from my notes here, maybe it will be of help. The following attempts to explain why a possible solution to Problem B is outputting 2 multiplied by the gcd of the elements in the difference array.Another method is presented in the comments. It states that, if performing mod (2 * g') on the input array (where g' is the greatest common divisor of the absolute value of the difference between two consecutive elements) there will be exactly 2 distinct values. Why is that?We can write g' as gcd(a[i] - a[i-1]) assuming that a[i] is greater than a[i-1] (this can be easily accomplished by sorting the array or taking the absolute value).Another useful notation is the following: let f(k) be the number of distinct values resulted after performing mod (k) on each element of the input array.Another useful observation is that if a ≡ r (mod k), than there are 2 possibilities: either a ≡ r (mod 2k) or a ≡ r + k (mod 2k) Now with that out of the way, we shall prove that f(2g') = 2.Notice that f(g') = 1. Why? Because a[i] - a[i-1] ≡ 0 (mod g'), which means that a[i] ≡ a[i-1] (mod g'), that is, all elements have the same value after performing mod (g') on them.How about f(2g') = 2? Well, based on the previous information, we can state that f(2g') should be either 2 or 1. So why it is not 1? Because f(2g') = 1 would mean that a[i] ≡ a[i-1] (mod 2g'), so a[i] - a[i-1] ≡ 0 (mod 2g'), so 2g' would be a divisor of a[i] - a[i-1]. However, do not forget that g' is the greatest common divisor, so there is no divisor greater than it, this means there is no way f(2g') = 1 as that would imply that 2g' is a divisor greater than the greatest divisor.After all of this, if f(2g') can not be 1, it goes without saying it should always be 2 ⇒ f(2g') = 2 ⇒ 2g' is a valid solution.
 » 4 months ago, # |   0 Folks, can someone please help me with why my solution to D is failing for the 6th test case given in the question? My solution#include using namespace std; #define ll long long int ll mod = 1e9 + 7; ll findGcd(ll a, ll b){ if(b == 0) return a; return gcd(b, a % b); } int main() { int t; cin>>t; while(t--){ ll n,k; cin>>n>>k; vector arr(n); for(int i=0; i>arr[i]; sort(arr.begin(), arr.end()); if(arr[0] >= k){ ll gcd = arr[0] - k; for(int i=1; i 0){ ll count = 0; for(ll x: arr){ count += (ll)((x - k) / gcd) - (ll)1; } cout< 0){ ll count = 0; for(int x: arr){ count += ((k - x) / gcd) - (ll)1; } cout<
 » 3 months ago, # |   0 in first probelm you said that i can visit it in any order so i can go to the point (1,0) after that to (-1,0) after that to (-1 ,-1 ) so i use just r l d so the answer in test two YES !!!!
 » 3 months ago, # |   0 problem D is amazing i have different approach for. suppose mn and mx are the max and min elements if mx == mn ans is 0. if mn <= k && k <= mx we can neve the values of array to a single value. if k < mn || k > mx ans will exist. assume at the end all the elements are equal to x so the last element we remove = 2 * x — k. second last element we would remove will be either 2 * x — k or 3 * x — k and so on. it shows that all the elements in the initial array is of the form .. pi * x — (pi — 1) * k, after rearranging pi(x — k) + k. now ans would be just summation of all pi.
 » 5 weeks ago, # |   0 ai mod 2k = x;  ai mod 2k = x + 2k; There must be x + 2k instead of x + k.For example, let ai = 5 and k = 2:5 % (2*2) = 1;Hence, x is 1.If we go with ai % (2k) = x + k, then:1 + 2 != 5But:1 + 2*2 == 5;TheScrasse