Codeforces Round #932 (Div. 2) Editorial

1935A - Entertainment in MAC

Idea: i_love_penguins
Preparation: i_love_penguins
Editorial: i_love_penguins

1935B - Informatics in MAC

Idea: AndreyPavlov
Preparation: AndreyPavlov, i_love_penguins
Editorial: AndreyPavlov

1935C - Messenger in MAC

Idea: i_love_penguins
Preparation: i_love_penguins
Editorial: i_love_penguins

1935D - Exam in MAC

Idea: IzhtskiyTimofey
Preparation: IzhtskiyTimofey
Editorial: IzhtskiyTimofey

1935E - Distance Learning Courses in MAC

Idea: IzhtskiyTimofey
Preparation: AndreyPavlov
Editorial: AndreyPavlov

1935F - Andrey's Tree

Idea: AndreyPavlov
Preparation: IzhtskiyTimofey
Editorial: IzhtskiyTimofey

We hope you liked our problems!

• 3 days ago, # ^ | D was alot harder for me but that may be just cause I'm bad at math.

• 3 days ago, # ^ | ← Rev. 2 →   0 Man you are Pro!!

• 2 days ago, # ^ | True, my stupid ass got stuck on C but D took me like 10 mins.

• 2 days ago, # ^ | Me too, I only used 10 mins actually lol

• 33 hours ago, # ^ |

• 24 hours ago, # ^ | ← Rev. 2 →   +3 I have a doubt in the editorial of problem C. When I fix L and R i.e the border values, then why checking only summation of all a_i such that it does not exceed l-(b[r]-b[l]) is sufficient? Shouldn't we also ensure that we have taken a[l] and a[r] in that summation?

  • 22 hours ago, # ^ | ← Rev. 2 →   0 Technically speaking, you are right, but it doesn't matter here whether you take it or not, Say a[L] and a[R] are not in the cur(from editorial's implementation), say the a[L+d] and a[R-e] (R-e >= L+d) are the leftmost and right most a's included in the cur, then when the loops are at i = L+d and j = R-e this case is going to counted or maybe even bigger subset of a's (since difference of b's is smaller here, than when i = L and j = R, since b's are sorted), hence the multiset s doesn't exactly contain the a's which are considered in the current loop but the answer comes right (a clever implementation !!) PS : My submission in contest also works exactly on your line of thinking, you can check that out here 249816460, Although the code is very messy :(

• 3 days ago, # ^ | can you share the solution using segment tree

• 30 hours ago, # ^ | I solve C,in contest time using a o(n^3) algorithmn.But someone hack me.However,the second day,I solve the problem in a o(n^3) algorithmn again.Using 2.1s to solve the 3s limited problem

• 3 days ago, # ^ | My code with such an asymptotic received a TLE.

• 3 days ago, # ^ | Can you explain how?

• • 3 days ago, # ^ | Binary search — the size of the subset and check if there is a subarray of length with cost no larger than . The rest is the same with the editorial.

    • 3 days ago, # ^ | ← Rev. 2 →   +16 why to check only subarray when we can choose subsequence also ???

      • 3 days ago, # ^ | I did think in binary search approach but then couldn't prove why subarray selection can be considered optimal instead of subsequence selection. Like, if I am starting at as first element and want to select elements, the optimal selection may be by chosing instead of . This can happen because can be insanely high while may be only a bit higher than .

        • 3 days ago, # ^ | i also couldn't figure out why selecting only the subarray works, why not the subsequence??

      • 10 hours ago, # ^ | we are not checking whole subarray here we are checking some elements in the subarray.Here we can use priority_queue or multiset in order to get the maximum number of elements whose sum is less than l-(dif) where dif is the difference between bi value of first and last element of subarray :)

    • 3 days ago, # ^ | It seems that your own submission is not using binary search. Can you show us your code?

• 3 days ago, # ^ | it also can be solved in O(n^2) 249837146

• 2 days ago, # ^ | ← Rev. 4 →   0 Binary Search can be applied: 249807781 Disclaimer Main Idea: If we can select a subsequence of size k, so can we select a subsequence of size k' < k. (monotonicity is obvious.) Now remains to check if a subsequence of length k exists that doesnt exceed the limit. Let's assume we fixed the left and right borders. As pointed out, only the sum of the remaining a-values matters because the b-values are only important if they are on the borders. So we need to compute for all subarrays the sum of the smallest k-2 a-values not included in the borders. To achieve this, let's iterate over R from 2 to n, set L = R-1 and maintain a multiset that stores the smallest k-2 values currently included in our window. To expand our window, we just need to update the multiset with the a-value of index L. Total asymptotics is O(n^2logn). If you have any further questions please don't refrain from asking.

• 3 days ago, # ^ | Nice! Same here...for the second one though, I just maintained a prefix array of mexes going from n-1 -> 0. Then, I compute the mex for each from and compare if leftmex == suffixmex[i+1], which is mostly the same as what you're saying, I think! I think the second observation that you only need 2 subarrays was the most useful for me.

• 3 days ago, # ^ | bro really called python pseudocode damn

  • 3 days ago, # ^ | Lol. There's subtle differences which make it more valid to call this pseudo-code. If it were python, 1. It would be def solve and not function solve. 2. set = {} would just create a dictionary object making set.insert(i) invalid. 3. I am assuming set = {} is a set that only stores distinct integers, which help me in calculating if I have seen all numbers from 0 to mx-1. 4. getMex is assumed to be well understood and implemented by the user.

• 3 days ago, # ^ | Thank You for breaking this down! I was having a hard time understanding the editorial but this makes so much sense.

• 3 days ago, # ^ | Bro if 0 is more that two in the array,then 1 is also same but 2 is just 1 then answer should be no?

  • 3 days ago, # ^ | Yeah, but that approach is not scalable or simplify-able to write code IMO. It has lots of corner cases too, I also started with thinking if there's any non-negative number which occurs only once, then answer will be no.

    • 3 days ago, # ^ | "the mex of every subarray will actually be the mex of entire array if answer exists.", If mex is k and k-1 is just one time in the whole array,then answer must be no ?

      • 3 days ago, # ^ | Yes, that is correct, but it's not useful. Even if is the mex and appears twice, or even if all values in appear twice, there might still be no solution, for example .

        • 2 days ago, # ^ | Yeah,after that I will just build my two segment 0 to k-1 first then again 0 to k-1 for the second time.If I can build answer is yes otherwise no.I have already get ac in that way.But thank you for your analysis.

• 3 days ago, # ^ | I did it exactly like this and thought authors really messed up with it. Turns out there's a much simpler solution.

• 3 days ago, # ^ | why does 0 1 1 return -1?

  • 2 days ago, # ^ | ← Rev. 2 →   0 The mex of the array is 2 You can't divide it into 2 segments [0,1] = 2, [1] = 0 Not okay. So -1.

• 3 days ago, # ^ | Wow u back to cp?

• 2 days ago, # ^ | ← Rev. 3 →   0 A typo? set.insert(i) should be set.insert(arr[i])

• 23 hours ago, # ^ | thanks

void solve(){
    long n;
    string s;
    cin>>n>>s;
    string result;
    if(s[s.size()-1]<s[0]){
        result = s;
        reverse(result.begin(),result.end());
        
        cout<<result<<s<<"\n";
    }else{
        cout<<s<<"\n";
    }
    
    
}

• 3 days ago, # ^ | You are only checking for the first character of the string. You should check the whole string. Your code will fail on this string "adba"

  • 3 days ago, # ^ | Thanx

• 3 days ago, # ^ | ← Rev. 2 →   0 You are comparing the first and the last character of the string instead of comparing the complete string with its reverse. Consider the string "acba". Take n to be any even number. Now, your code will output "acba", even though "abcaacba" is lexicographically smaller. To correct this, check for reverseStr<str instead.

  • 3 days ago, # ^ | Yeah , the problem was if the last and first are equal I have to keep checking for the condition (s[s.size()-i-1]<s[i]) Thank you for answering!

• 3 days ago, # ^ | thats the same solution as mine

• 2 days ago, # ^ | You can try the example acba

• 2 days ago, # ^ | not offending you but what do you expect you are contributing with these comments...most of the people don't understand the code because you know what logic you wrote...it doesn't have comments either. Some understand wrong solutions and concepts get unclear...please if u comment then atleast give a small explanation of ur code

• 2 days ago, # ^ | please explain your solution clearly by writing the states then the transitions so that it helps us...these types of comments create in us confusion related to the topics...please answer

  • 2 days ago, # ^ | ← Rev. 3 →   +13 I think I explained it good, maybe some pseudo-code will help you. Ask if it is not We must choose maximum lenght subsequence such sum of is minimum (we want to choose minimum sum, because we want this sum be not greater than , if minimum sum is greater than it means every sum will be greater than ). So, let's iteratate in non-decreasing order of values , for we store base (because is minimal value, that is, . And in formula we get , so current value will be and we must substract it). Now transition is simple: choose previous length and try to add new value in it, increasing lenght by sort pairs by b[i] value d[len] = INF d[1] = a[1] - b[1] for(int i = 2; i <= n; i++) { for(int len = 1; len <= n; len++ ){ check if (len + 1) will be answer after we add a[i] b[i] pair in it } for(int len = n; len >= 2; len-- ){ d[len] = min(d[len], d[len - 1] + a[i]) } d[1] = min(d[1], a[i] - b[i]) } print ans Upd: my submission during the contest [here]

    • 47 hours ago, # ^ | Thanks...I got it !! sorry if my comment sounded rude

      • 13 hours ago, # ^ | Bro doesn't even try to understand. You just want fast food.

• 3 days ago, # ^ | maybe you can try to use scanf to read and printf to print answer. I think your code is correct in time complicity.

• 3 days ago, # ^ | Yes, my passed with the help of pragmas.

• 3 days ago, # ^ | 249812906 is , it passes in 1300ms without any extra optimizations. Feel free to hack if you think you can make it TLE (I might try hacking it myself later)

• 3 days ago, # ^ | My n^2log^2 solution passed, but it most likely would not have passed, had I used multiset or some other heavy O(logn) data structure, instead of priority queue.

  • 3 days ago, # ^ | Yeah I used a PST so it's kinda my fault, but I think the TLE case should have been in pretests atleast.

    • 3 days ago, # ^ | feels bad :I

  • 21 hour(s) ago, # ^ | I used a multiset for solving in time and it passed, I think the constant of the time complexity would make a huge difference in this case.

• 3 days ago, # ^ | Maybe you should try to sort pairs by because if you select some pairs and the optimal way to arrange them is sort them with

• 3 days ago, # ^ | ngl idgaf fr

• 3 days ago, # ^ | Meh, I had an solution but decided not to implement because I thought it would TLE.

• 2 days ago, # ^ | same as mine. We are goofs, the O(n^2) solution was so much easier :skull:

  • 2 days ago, # ^ | Agreed. We got lucky with the constraints of . I wasn't able to come up with the O(n^2) solution :'(

• 3 days ago, # ^ | Because if you select 0 and 1 1, the mex for first segment is 1, and for the second segment is 0, or if you select 0 1 and 1, the mex on the first segment is 2 and in the second is 0, so again mexs are different.

  • 3 days ago, # ^ | thank you,i didnt get that part at first

• 3 days ago, # ^ | Exactly my doubt..pls someone clear.. even if we delete some ai in l to r why are we still considering V[r] — V[l] ?

• 3 days ago, # ^ | ← Rev. 2 →   +4 In the solution, for the [l,r] interval, we are not maintaining number of smaller a's with sum <= L - (a[l] + a[r] + (b[r] - b[l])). Rather, for every interval [l, r], our priority_queue / multiset maintains the list of a's which lie in [l, r], with sum <= L - (b[r] - b[l]). only (which means we do not fix a[l] and a[r] to always be included in the sum). Now, 4 cases arise for interval [l, r]: Both a[l] and a[r] are included in the set of the smallest sum. a[l] is included but a[r] is not included a[r] is included but a[l] is not included both a[l] and a[r] are not included. For case 1, we know that this is the best set of a's maintained for [l, r], so we can do mx = max(mx, count) here. For every other case, we have some other interval [l_inner, r_inner] where l_inner and r_inner are indices of the leftmost and the rightmost included a's. For every [l, r] interval where case 1 is not applicable, we say that the current count is less than or equal to the count of [l_inner, r_inner] (This is because b[r_inner] - b[l_inner] <= b[r] - b[l] increasing the possible number of items we can pick for the sum within limit). So, for any [l, r] where cases 2, 3 and 4 exist, the answer will always be <= answer of [l_inner, r_inner]. Also, we can see that for the interval [l_inner, r_inner], elements at l_inner and r_inner will be always be chosen in the sum. Since we are looping through all the possible values of l and r, it is ensured that we will calculate [l_inner, r_inner]. So, this is why we do not need to calculate the exact sum for [l, r], but rather b[r] - b[l] + (sum of a's) <= L. Hope this helps and is not too confusing.

  • 3 days ago, # ^ | ← Rev. 3 →   +2 In other words where . Since we are iterating all possible we are also going over all

    • 3 days ago, # ^ | Yes, correct

  • 3 days ago, # ^ | Great explanation.

  • 2 days ago, # ^ | Great Explanation!!! So our first priority is to maintain all possible gaps/distance [l,r], and for that particular distance we are calculating maximum possible count. (Make Sense). I was thinking greddily and why we we not updating [l,r] in the case if we are removing first and last element of subset we are choosing.(We don't required it, we can simply calculate max soln for all possible distance).

• 3 days ago, # ^ | Same issue, unsure what 591st tc in 2nd test case is? 249827779

• 3 days ago, # ^ | Same Solution

• 3 days ago, # ^ | Can you explain what you did?

  • 3 days ago, # ^ | ← Rev. 4 →   +1 first of all we will store values in a vector<pair<int,int>> v and sort according to bi. (if you don't know why, ask) now, my dp[i][j] has following arguments i and j. i: chosen subset will end at i. j: chosen subset will have j values and dp[i][j] is the minimum cost of choosing optimal subset such that it ends at i and have j values in it. answer will be maximum value of all js such that dp[i][j]<=l. now transition: well I lied above dp[i][j] is not the minimum cost of choosing the optimal subset but rather it is dp[i][j] = minimum cost — v[x].second. where x is the index of the first value in the subset. and it's not only ending at i its minimum cost for all indexes <=i with values count j — transition works as follows dp[i][j] = dp[i-1][j-1] + v[i].first + v[i].second. a lot of things happened here dp[i-1][j-1] = minimum cost — v[x].second(explained above) is the amongst all the ending indexes < i, such that we get minimum cost — v[x].second so dp[i][j] = minimum cost + v[i].first + (v[i].first-v[x]) now since the b values are sorted only contribution we will get from b is (v[i].second-v[x].second) now we will do dp[i][j]= min(dp[i-1][j], dp[i][j]-v[i].second) (because we want to make it (minimum cost — v[x].second)).

    • 2 days ago, # ^ | ← Rev. 3 →   0 what made you choose to sort in accordance with bi got it :<)

    • 47 hours ago, # ^ | Wow...your solution was great. I mean thinking of such states and transitions are great. please share some more prblms like this if you have where the state definition is not trivial and transitions require critical thinking...i Specially liked the part where you are using ur dp array to check if it is <= l...and at the next step making it such that it helps in recalculation of next dp states. please share more problems like this

      • 44 hours ago, # ^ | this is a common technique where we have to separate f(i) and f(j) if we are dealing with pairs. (here essentially we are dealing with every thing before index j and j) let me give you a trivial example. suppose we have been given a array "arr" with some values and we have to calculate no of pairs such that arr[i]*arr[j] = 1 (mod 1e9+7) we can just loop in the array store 1/arr[i] (mod 1e9+7) in a hashmap and add and+=mp[arr[i]]; code: map<int,int> mp; int ans = 0; int inverseMod(int val) for(int i=0;i<n;i++){ ans+=mp[arr[i]]; mp[inverseMod(arr[i])]++; } the main idea being used in that dp solution is that only.

  • 3 days ago, # ^ | well i did not explain it very clearly if you have any doubt just ask me.

    • 2 days ago, # ^ | now we will do dp[i][j]= min(dp[i-1][j], dp[i][j]-v[i].second) (because we want to make it (minimum cost — v[x].second)). i don't get it when are you choosing to have v[x].second in dp[i][j] because if choosing ith as optimal then only we should add v[i].second to dp[i][j] so then if it's no optimal it shouldn't be added and shouldn't be subtracted in future

      • 2 days ago, # ^ | i don't clearly understand your question.

      • 2 days ago, # ^ | ← Rev. 3 →   0 dp[i][j] before this code "dp[i][j]= min(dp[i-1][j], dp[i][j]-v[i].second)" is taking the following form -> sum of all ai's in the subset + (v[i].second-v[x].second) now i am making it dp[i][j] = min(dp[i-1][j], sum of all ai's in the subset-v[x].second)

• 3 days ago, # ^ | if you think deeply it still covers all the cases. If we're removing a value of the element and still considering it's b value, this case has already been covered earlier at index with smaller b value which will be optimal than the current one.

• 2 days ago, # ^ | I agree. Posted the same query here.

• 2 days ago, # ^ | If messages or are removed from the set, we're now calculating the cost incorrectly: the cost we calculate is larger that the true cost, and this might mean that our answer is too small. But that is actually never a problem. If or gets removed when considering the range , the range is definitely not optimal ( or , depending on which element got removed, would be at least as good as ). Since we comsider all ranges, including and , we won't miss the optimal solution.

  • 2 days ago, # ^ | Yes, but it doesn't seem satisfying IMO, I have posted similar doubt comment above. Also if element l gets removed, note that though l+1 may have less value in a but it definitely also has bigger b value which helps when its the smallest b. Now the answer to that is, but we will include l+1 in our for loop iteration, so that case gets covered. The point here is, this seems to be working only because of many other reasons behind the scenes which are skipped in editorial. Would like a cleaner general approach to handle such situations with more clarity without worrying over the behind-the-scenes forces making this work.

    • 2 days ago, # ^ | Just to avoid all this I didn't include lth element and rth element in the multiset. Instead, I added them explicitly. And guess what I got WA this way. And I ended up not being able to solve the problem in the contest. Here is my code : Submission It would be very helpful if you could point out where this code is failing.

      • 2 days ago, # ^ | I tried the same way and my submission fails at the same test case. This needs rectification.

        • 2 days ago, # ^ | I was not able to do anything today just to figure out why it is going wrong.

        • 2 days ago, # ^ | Take a look at Ticket 17407 from CF Stress for a counter example.

          • 2 days ago, # ^ | Thanks buddy

        • 2 days ago, # ^ | I just printed that test case that it was failing for. The thing is that when we are fixing lth and rth element we might remove a smaller element that might be useful afterwards just to keep rth element.

          • 47 hours ago, # ^ | Thanks for the clarification

• • 2 days ago, # ^ | When the sequence of B is odered, why the formula always get minimum ? I want to the reason.Please teach me ，i am willing to know!

    • 2 days ago, # ^ | I think you misunderstood this. Let's observe formula: Sum of values does not require any order, we can just sum them. What about sum of differences of , of course, we want to minimize this sum (so that sum is not greater than ) Now, we can forget about values (their sum does not depend on order we choose values). But if we got values , it's always optimal to sort them. For example, gives sum , but gives sum . Why? You can see abs function as distance beetween two points on straight line. It's easy to see, that sorting gets the minimum sum. Now, we can sort values by and choose sum values to our answer. Let's closer look at , it's equal to , there are pairs etc for all from to , and now this sum equal to

      • 2 days ago, # ^ | i am appreciate your reply! The words resolve my question! For example, b=[1,6,1,5] gives sum 6−1+6−1+5−1=14 , but b=[1,1,5,6] gives sum 1−1+5−1+6−5=5 . Why? You can see abs function |x−y| as distance beetween two points x,y on straight line. It's easy to see, that sorting gets the minimum sum. Also , you assist me to deepen insigth about the problem. Thank you !

        • 2 days ago, # ^ | NP! (Not like NP-problems by these authors, but "No problem")

          • 2 days ago, # ^ | "NP" means "No problem" ? if my guess is right , it is fun and straightforward！

      • 24 hours ago, # ^ | I have one more doubt. While we are selecting the l and r and checking whether the sum of elements in between them is less than l-(b[r]-b[l]), we are taking the sum of some a[i]'s, but the problem is that as soon as we fix l and r, shouldn't we also make sure that a[l] and a[r] are always there in our sum? But proceeding greedily without taking care of them is getting accepted. How is this correct? Please help me with reason why we don't need to make sure that the sum always includes a[l] and a[r]. Thank You

        • 23 hours ago, # ^ | I must say, I don't know why greedy works. My solution is DP

• 2 days ago, # ^ | You have to use in your proof, author's C++ solution don't use

• 2 days ago, # ^ | If there is answer in such segments we can always reduce it into segments. So, it is not possible to find answer in segments, we won't find it in any bigger segments (if there is answer in bigger number of segments, we would reduce it into segments and found it there).

• 2 days ago, # ^ | Let us assume for array , we have a valid partition into subsegments each having . If we consider merging subsegments and (), the of the new subsegment would also be (as it too would contain all elements from to but would not feature ). Continuing this process will lead us to partition array into any number of subsegments less than . We can conclude that if there is a valid partition of into subsegments, a valid partition into subsegments must exist. As a corollary, if cannot be partitioned into segments, it cannot be partitioned into segments. This would prove your argument for .

• 44 hours ago, # ^ | Consider the test case: This might help.

• 39 hours ago, # ^ | i found my mistake, sorry everybody

• 31 hour(s) ago, # ^ | ← Rev. 3 →   0 I think if the multiset is not empty, there must be v[l+a].second() and v[r-b].second() in the multiset, so

• 24 hours ago, # ^ | this is my code ,the only difference is i am not adding the boundary element to multiset,i dont know why am i getting wa, can someone help me? for(i=0;i<n;i++) { ll sum=0; ans=max(ans,(ll)1); multiset<ll>nums; for(j=i+1;j<n;j++) { if(v[i].second+v[j].second+v[j].first-v[i].first>x) { continue; } while(nums.size()!=0 && sum+v[i].second+v[j].second+v[j].first-v[i].first>x) { sum=sum-*nums.rbegin(); auto it=nums.end(); it--; nums.erase(it); } sum=sum+po[j].second; nums.insert(po[j].second); ans=max(ans,(ll)(pq.size()+1)); } }

  • 23 hours ago, # ^ | found what's wrong , i assumed taking the current right element is always best , but its not the case, some times we have to skip the current right element, ac code for(i=0;i<n;i++) { ll sum=po[i].second; ans=max(ans,(ll)1); multiset<ll>nums; for(j=i+1;j<n;j++) { while(nums.size()!=0 && sum+po[j].first-po[i].first>x) { sum=sum-*nums.rbegin(); auto it=nums.end(); it--; nums.erase(it); } sum=sum+po[j].second; nums.insert(po[j].second); if(sum+po[j].first-po[i].first<=x) { ans=max(ans,(ll)(nums.size())+1); } } }

• 24 hours ago, # ^ | Same doubt I also have.

• 24 hours ago, # ^ | error in comp funtion try this bool comp(vector&u,vector&v){ return u[1]<v[1]; }

• 22 hours ago, # ^ | My Dp uses only 1 state

  • 22 hours ago, # ^ | yeah its possible to reduce one dimension. Actually i have done this in my solution. I have use this extra dimension for simplification.

• 41 minute(s) ago, # ^ | "Suppose we are iterating over bit , then if such a bit occurs times in numbers there are several cases:" This means the number of times that a bit occur in , not in . In your example, when you have and , when we are looking for the highest bit = , then , so you put the bit in the answer. After that, the next bit is , that appears once in , so you put the bit in res, then, bit doesn't appears in any of them, and bit appears both in and , so, the answer is .