Stepavly's blog

By Stepavly, 3 years ago, translation,

1506A - Strange Table

Problem author: sodafago

Editorial
Solution

1506B - Partial Replacement

Problem author: MikeMirzayanov

Editorial
Solution

1506C - Double-ended Strings

Problem author: MikeMirzayanov

Editorial
Solution

1506D - Epic Transformation

Problem author: MikeMirzayanov

Editorial
Solution

1506E - Restoring the Permutation

Problem author: MikeMirzayanov

Editorial
Solution

1506F - Triangular Paths

Problem author: MikeMirzayanov, Stepavly, Supermagzzz

Editorial
Solution

1506G - Maximize the Remaining String

Problem author: MikeMirzayanov

Editorial
Solution
• +65

| Write comment?
 » 3 years ago, # |   +22 Problem C was a direct Longest Common Substring question
•  » » 3 years ago, # ^ |   +276 Thanks for sharing such a valuable insight with us.
•  » » » 3 years ago, # ^ |   +11 Your sarcasm is very RATIST
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +4 You have high EQ
•  » » » 3 years ago, # ^ |   +5 Your EQ is really high.
•  » » 3 years ago, # ^ |   +1 Thanks man!!
 » 3 years ago, # |   +4 Nice problems. Thanks for such a wonderful contest.
 » 3 years ago, # |   +3 very interesting tasks!
 » 3 years ago, # |   +12 Spoilers are broken for me.
•  » » 3 years ago, # ^ |   0 It is very annoying. Please MikeMirzayanov fix.
 » 3 years ago, # |   0 tutorial d is not clear
•  » » 3 years ago, # ^ |   +5 Consider the frequency of the most frequently occurring element. Let it be $mx$.Now, we will try to pair these $mx$ elements with rest of the elements, i.e, $(n-mx)$.$if(mx\,<=\,n-mx)\,ans = 0 \newline else\,ans\,=mx\,-\,(n-mx)$Also note that if $n$ is odd then minimum possible answer is $1$$if(n\,\,is\,\,odd)\,ans=max(ans, 1)$
•  » » » 3 years ago, # ^ |   0 I used the same approach but I got TLE on test case 7. What is the problem? Can someone help me?
•  » » » » 3 years ago, # ^ |   0 Same problem here , I am not able understand why I got TLE on testcase 7 , please anybody can explain it...
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 unordered_map m; m.reserve(1<<10); m.max_load_factor(0.25); By adding these two lines at after declaring unordered_map, you can get rid of TLE. For explanation checkout this blog.
•  » » » » 3 years ago, # ^ |   +20 Your logic is correct. The reason that you are getting a TLE verdict is because you have used an "unordered_map". By using an unorederd_map , you are expecting an average of O(1) time complexity. However,as you might know, unordered_map works on the concept of "hashing". So,for that particular test case(T.C-7,where your code gives a TLE verdict), there must be collision between hash values in the map,giving you an actual time complexity of O(n^2) as opposed to your expected O(1) time complexity. Judging by the constraints,you may easily see that O(n^2) is not sufficient to pass the tests. You may use "map" instead,which will give you a time complexity of O(log n).It will easily pass the tests. You may refer the given link below for more understanding on the above topic: https://mirror.codeforces.com/blog/entry/62393 Also,here is a link to my solution in case you may face any problems: https://mirror.codeforces.com/contest/1506/submission/111029797
•  » » » » » 3 years ago, # ^ |   +1 thanks a lot bro i also did the same mistake and i had no clue why my solution was wrong
•  » » » » » 3 years ago, # ^ |   +1 Yeah! Thank you for your valuable reply...
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   +1 Thnak you so much :) ....even editorial is containg unordered map
•  » » » 3 years ago, # ^ |   0 why is ans 0 if mx <= n — mx. This basically means the max frequency is lesser than rest so it will be paired easily but after fixing these mx elements, how do i know the left elements will be distinct and i will be able to eliminate all? or 1 will be left in case of odd. can someone explain?
 » 3 years ago, # |   0 Please put the code in spoiler tag.
•  » » 3 years ago, # ^ |   +1 Seems like spoilers are broken now
 » 3 years ago, # | ← Rev. 2 →   -6 Hey, MikeMirzayanov Just wanted to bring before you plagrism of two users Both of these Users don't know whether same persons or different has submitted solution of Problem A and B with minor Changes. Please Do look at their submission. Even their template is same. Since Even submitting Solutions from alternate account is clear voilation of policy please Review their submission. Maybe they would be same person just submitting solution from one account to confirm its correctness and escape penalty, which is voilation of Rule and needed to be punished if really found guilty. Their Submissions: Problem A: 110996666 and 111008607Problem B: 111007814 and 111006918
•  » » 3 years ago, # ^ | ← Rev. 4 →   -40 MikeMirzayanov plag_report Yeah my bad, but I have an explanation for that which I think might be justified. Since the past 3 contests I've been facing issues with the CodeForces server being down, as might be evident from the bad results of my past 2 contests as well as the fact that I could not give the Division 2 immediately preceding today's contest. Thus, to prevent a negative effect on my rating I started today's contest with my alternate account but switched back to my original one after facing no issues for about half an hour.I had no idea that submitting from 2 accounts is also a violation of Rule, and I thought that since I could easily prove the 2 accounts to be mine, I would be able to show that the code is completely original in case someone said otherwise.I can assure you that it wasn't a case of trying to avoid a penalty because I did get penalties in my D and E as well. If I had been trying to avoid penalties by testing solutions with my alt account, then I obviously wouldn't have stopped that for the harder problemsMoreover, I submitted the solution for A from my main account 15 minutes later, which covers up the 1 penalty advantage that I would've received in problem B
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +10 Do you even read the rules of participation before clicking on that "Register" button while registering for participation in a contest ? It's clearly written there that you can't use multiple accounts
•  » » » 3 years ago, # ^ |   +2 You can use second and third websites for contests. [Second website(https://m2.codeforces.com/) Third Website]
 » 3 years ago, # | ← Rev. 3 →   +5 my solution for D sorry for my englishlet MAX be the maximum number of times a number occurs. if MAX>n-MAX, then the answer is MAX — (n-MAX) because we can delete this number with all the others, but we can't delete it with ourselves. otherwise, the answer is n%2, because we can delete the remaining numbers up to the number of our number, and then delete them with our number. well, if n%2 == 0, then we can delete everything, otherwise it is clear that we will not be able to delete one element because we delete 2 elements each
•  » » 3 years ago, # ^ |   +2 how can we prove if n%2 == 0 and MAX<=n-MAX then every number will get paired up
•  » » » 3 years ago, # ^ |   -7 you can easily prove this by induction.
•  » » » » 3 years ago, # ^ |   0 How would you prove it? Please provide a proof.
•  » » » » » 3 years ago, # ^ |   0
•  » » » » 3 years ago, # ^ |   0 can u pls tell the proof??
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 For base case: Let's say we have two groups ($a$ & $b$) of elements initially. $freq[a]=size/2$ $freq[b]=size/2$ So we can pair them up easily. Now we assume that we can pair $k$ groups of elements.Now for the $k+1$ th group, No of elements in this group $\leq$ $totalSize/2$. So we can always break a pair and make two new pairs with the elements of $k+1$ th group. Although I assumed that size of $k$ groups is even, but you can see that if it was odd then we could pair one element of $k+1$ th group with that left element. You can extend this proof to $size$ being $odd$ where you could make a argument that we will be left with one element after pairings are done. And in fact this proof is for both $odd$ and $even$ size combined.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +41 Sort the array and pair up $a_i$ with $a_{i+n/2}$. Since every number appears no more than $n/2$ times, these two numbers are always different.
•  » » » » 3 years ago, # ^ |   0 Easy to understand!
•  » » » 3 years ago, # ^ |   0 Prove by contradiction-> Let there be some numbers left. Without loss of generality, we can assume that there are x 1's left. Let's assume initially there were y 1's present in the array. So, we can safely say that (y-x) 1's were paired with some numbers. So, there are $n-y-(y-x)$ elements left which are neither 1's nor paired to any 1. So, there were $\frac{n-y-(y-x)}{2}$ pairs involving no 1. So, we will try to break $\frac{x}{2}$ of those pairs and pair each number with the remaining $x$ 1's. Now, we just have to prove that $\frac{x}{2}\leq\frac{n-y-(y-x)}{2}$. $x\leq n-y-(y-x)$ $2*y \leq n$Now, as the most frequent elements occur less than $\frac{n}{2}$ times, so this condition is satisfied. Hence proved! Voila!
•  » » » 3 years ago, # ^ |   0 Since now MAX <= n-MAX, you could pair numbers in n-MAX. Whenever you delete a pair, n-MAX => n-MAX-2. Continue this process until MAX == n-MAX-2*pair_nums.[Noticed that there must a pair_nums which fits the equation. If not, then there is a number which appears (n-MAX-2*pair_nums) times and MAX < (n-MAX-2*pair_nums), however MAX is the max appear times.]Then we could delete each number in MAX with others.
 » 3 years ago, # |   -8 Learnt something new today — s.lower_bound(x) is MUCH MUCH faster in set than lower_bound(s.begin(),s.end(),x). Wasted an hour and will cost me my rating but definitely wont make this mistake ever again. Thanks :)
•  » » 3 years ago, # ^ |   0 Blog about it! Luckyli I faced this while practicing. And today that experience helped me!
»
3 years ago, # |
-41

HAPPY CODING

•  » » 3 years ago, # ^ | ← Rev. 2 →   +50 Just a friendly advice, you should try and improve your coding skills and try streaming later when you are better at coding.
•  » » » 3 years ago, # ^ |   -56 just a friendly advice too : Don't judge a Book by its cover and Oil your own machine ..
•  » » » » 3 years ago, # ^ |   +50 Easy dude, just tried to help you not argue with you. Fine, I lose, you are one of the best coders and are really great at coding. Okay?
 » 3 years ago, # |   +10 I guess problems were easier than the editorial :)
 » 3 years ago, # |   0 Can anyone please explain the problem 1506G — Maximize the Remaining String in simpler way?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 Here's my pretty basic approach:For the first letter, can we make it Z? We can if we have a Z, and every other unused letter appears after the first instance of Z. If not, try Y, X, W, etc.Then repeat this for the second letter, third letter, fourth letter, discounting the letters we have already used, and strictly considering positions after our last used letter. We finish when there are no more unused letters.Here's my submission (python). It's reasonably easy to follow.
•  » » » 3 years ago, # ^ |   +5 Thanks a lot for this approach! Was a good bitmask exercise for me in c++.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Made a video on this, you can give it a watch. https://youtu.be/NMSiu-VNfYU
•  » » » 3 years ago, # ^ |   0 Thanks a lot! Really helped!
 » 3 years ago, # |   0 Stepavly for problem E, i think u forgot to mention approach for lexicographically maximal string. I cant find it "If we want to build a minimal lexicographic permutation, we need to build it from left to right by adding the smallest possible element. If q[i]=q[i−1], so the new number must not be greater than all the previous ones, and if q[i]>q[i−1], then necessarily a[i]=q[i]. q[i]q[i−1], then a[i]=q[i], otherwise we put the minimum character that has not yet occurred in the permutation."
•  » » 3 years ago, # ^ |   0 To get the maximum you can do something very similar.If q[i] > q[i-1], again we have q[i] = a[i]. When this happens, add all integers between q[i-1] and q[i] to a maximum priority queue. For elements where q[i] = q[i-1], a[i] is the element at the top of the maximum priority queue.
 » 3 years ago, # |   +3 If c1=c2, then if (r1+c1) is even, then the cost is r2−r1, otherwise the cost is 0;Shouldn't that be $r1 - c1 = r2 - c2$ instead of $c1 = c2$?
 » 3 years ago, # |   +9 Can someone plz give a more beginner friendly explanation to problem G. I cant understand the one given in the editorial.
•  » » 3 years ago, # ^ |   +6 Hope this helps
•  » » 3 years ago, # ^ |   +9 Maybe 111074804 this can help.
 » 3 years ago, # |   0 boooooooooooooooooring round
 » 3 years ago, # | ← Rev. 2 →   +2 what will be the time complexity of editorial of problem d? since the value of ai can go up to 1e9;update: sorry I just forget, we are dealing with frequency. :( How can I be so dumb!
•  » » 3 years ago, # ^ |   +1 We are not dealing with ai. We are dealing with the frequency array of a. Since total number of elements <=2e5,the sum of elements of freq array doesn't exceed 2e5.
 » 3 years ago, # |   +46 When Problemsetters don't want the police to bother them! Credits — Problem G(For those who don't know, "AEZAKMI" is a cheat code in GTA San Andreas to escape from the police permanently)
 » 3 years ago, # |   +4 Problem G is the same as https://leetcode.com/problems/remove-duplicate-letters/
 » 3 years ago, # |   0 I had the exact idea for D. But I didn't code it since I thought it would give TLE. Can someone explain why the solution for D won't TLE?
•  » » 3 years ago, # ^ |   0 I thought of the same thing during the contest. But the sum of n over all test cases wont exceed 2e5. So it passes.
•  » » 3 years ago, # ^ |   0 i coded it and got TLE, XD. Here in editorial they used 2 elements for priority_queue but i used only one. Though priority_queue does not work on hashing still i don't know why it gave me TLE //This is my code. int n; cin>>n; vector a(n); unordered_map cnt; for(int i=0;i>a[i],cnt[a[i]]++; priority_queue pq; for(auto u:cnt) pq.push(u.second); while(pq.size()>1) { int hi=pq.top(); pq.pop(); int lo=pq.top(); pq.pop(); if(hi>1) pq.push(hi-1); if(lo>1) pq.push(lo-1); } int ans=0; while(pq.size()) { ans+=pq.top(); pq.pop(); } cout<> q; //changes are here only int n; cin >> n; map v; for (int i = 0; i < n; i++) { int x; cin >> x; v[x]++; } for (auto u: v) { q.push({u.second, u.first}); } while (q.size() >1) { auto hi = q.top(); q.pop(); auto lo = q.top(); q.pop(); hi[0]--; lo[0]--; if (hi[0]) { q.push(hi); } if (lo[0]) { q.push(lo); } } int ans = 0; while(q.size()) { ans+=q.top()[0]; q.pop(); } cout << ans << "\n"; 
•  » » » 3 years ago, # ^ |   0 it was the same in my case. when i used unordered_map, it gave me TLE. changing it to map gave AC. idk why it happens. is the inbuilt hashing function that bad?
 » 3 years ago, # |   +1 Weak pretests for problem E. Well, it was ultimately my mistake as I ignored the time complexity of my code
•  » » 3 years ago, # ^ |   0 Yeah, felt so bad to get TLE 12 hours after it was initially accepted. I didn't expect my solution to pass but it still hurt.
•  » » 3 years ago, # ^ |   0 Me too I though the complexity of my code was o(n) but on closer examination on some cases its o(n^2). Many people had submitted such a solution and had their solution hacked.
 » 3 years ago, # |   0 For question D,why can map pass this questionAccepted but use unorderd_map will TLE
•  » » 3 years ago, # ^ |   0 Have a read. Blog !
•  » » » 3 years ago, # ^ |   0 Thanks
•  » » 3 years ago, # ^ |   0 Ordered map aka usual "map" is sorted as a default so any operation performed on it is O(log(n)) whereas unorderedmap will cost O(n) for each operation
 » 3 years ago, # |   0 Can anyone help me with E. Why my code got TLE? Code
 » 3 years ago, # |   +1 Can someone explain the solution of G?
 » 3 years ago, # | ← Rev. 2 →   0 Why did my code for E gave TLE. As far as I know insert, lower_bound and upper_bound all are O(log n), so the overall complexity should be O(nlogn) right ??
•  » » 3 years ago, # ^ |   0 Hopefully this will clear your doubts — https://mirror.codeforces.com/blog/entry/76206?#comment-606743
•  » » » 3 years ago, # ^ |   0 Thanks, got it. Also could you tell which part of the code is taking time in this vector implementation.
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   0 Erasing an element from a vector takes O(n) time complexity. So, the overall time complexity of your function is O($n^2$). I would suggest you clear your fundamentals especially related to the STL library and its function's time and space complexity so that you don't make further conceptual errors in implementation at least. Please refer to this — https://stackoverflow.com/questions/28266382/time-complexity-of-removing-items-in-vectors-and-deque#:~:text=Erasing%20an%20element%20in%20a,complexity%20is%20O(n).
 » 3 years ago, # |   +13 B, C solutions with regexes instead of usual loops. Perl: B — 111112920, C — 111113262
 » 3 years ago, # |   0 Why this solution (in Python) for question E gives TLE, but this (in CPP) does not. Can anybody explain?
 » 3 years ago, # |   0 Hey does anybody knows the scoring criteria for hacking someone's solution? I made around 15 successful hacks but my rank does not seem to have improved much.
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone show why my E problem code got RTE? https://mirror.codeforces.com/contest/1506/submission/111127527Thanks alot
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Your code uses erased iterator. auto it = s.lower_bound(a[i]); if (it == s.begin()) { cout << *it << " "; continue; } -- it; if (it != s.end()) s.erase(it); res[i] = *it; // uses a deleted iterator Just modify slightly will AC(111132839). if (it != s.end()) res[i] = *it, s.erase(it); 
•  » » » 3 years ago, # ^ |   0 Got it, thanks alot
 » 3 years ago, # |   0 Can someone tell me why using unordered_map instead of map in problem D gives TLE on test case 8.TLE when using unordered_map: https://mirror.codeforces.com/contest/1506/submission/111132652Accepted when used map instead: https://mirror.codeforces.com/contest/1506/submission/111132742
 » 3 years ago, # |   0 can someone explain G again ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Just keeping adding the highest character to your string such that following conditions are met: (Suppose the index of your highest character is i in the orignal string(s). answer string is t) then i >index of last character in t also take lowest such i 3.check if s[i+1....s.size()] contains all remaining characters which are not added to your answer string t.if any of these conditions are not met move to the next lower character. continue this process till you have added all unique characters to string t
 » 3 years ago, # |   0 I did problem D with a very simple 2 pointer solution. Initialse left pointer,lft=0 & right pointer, rgt= ceil(n/2). Now, till you the rgt is not at the end of array, if arr[lft]==arr[rgt]: pair_count++,lft++,rgt++; else rgt++; final answer would be n-pair_count.
 » 3 years ago, # |   0 **** Problem E ******I wrote O(nlogn) solution for problem E using sets but it is giving TLE in 3rd test case. Here is my solution: here.Please anyone help me to find the problem in it. I am not able to figure it our.
•  » » 3 years ago, # ^ |   0 You wrote erase and find for a set in the loop so it's more than $O(n\ log\ n)$ .
•  » » » 3 years ago, # ^ |   +1 I have used only erase at first and it gave TLE so, I tried by using find and erase and again it is giving TLE.Later I have found it is giving TLE bcoz of using a normal lowerbound function, I replaced it with set lower_bound then it got accepted.
•  » » » » 3 years ago, # ^ |   0 Oh I see.
 » 3 years ago, # |   0 Please can someone explain statement of problem F ? Actually, I don't really understand how it is possible to pass through all N points as the edges are directed Thanks by advance for your help!
•  » » 3 years ago, # ^ |   0 It is guaranteed by the input of the problem, so they will always give n points which you can pass by them after sorting them by layer
 » 3 years ago, # |   0 [Problem E] I invented a very clean implementation of the solution to problem E. Both for max and min, maintain a pool of unused numbers; If V[i] == V[i-1], pick the most relevant element from the pool and add to solution; If V[i] != V[i-1], update the pool by all numbers in range [V[i-1] + 1, V[i] - 1], and extend both solutions by V[i]. The key point here is that the pools can be created using queue for min (we will always pick smallest non-used this way) and for max by using stack (now we will always pick the largest not used number)! This way we implement the solution in O(n) and in around 25 lines of code, max-part of it being an almost direct copy of the min-part. My solution: submission 111566779 (mal and ros are respective pools, and omal and oros` are vectors for the solution to the problems).
 » 9 months ago, # |   0 Hi, I dont know whats wrong with CD judge. I am submitting solution for D and its giving wrong verdict on the very first test case. On other machines its running pretty fine. Here is my solution link https://mirror.codeforces.com/contest/1506/submission/214315136Thanks in advance if someone could help.
 » 7 weeks ago, # |   0 can anyone share the 65th entry of Testcase 2 of D as I am getting out of bounds in it