Stepavly's blog

By Stepavly, 6 months ago, translation, In English

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
 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Problem C was a direct Longest Common Substring question

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Nice problems. Thanks for such a wonderful contest.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

very interesting tasks!

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Spoilers are broken for me.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tutorial d is not clear

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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) $$$

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the same approach but I got TLE on test case 7. What is the problem? Can someone help me?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same problem here , I am not able understand why I got TLE on testcase 7 , please anybody can explain it...

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it
          unordered_map<int, int> 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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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://codeforces.com/blog/entry/62393 Also,here is a link to my solution in case you may face any problems: https://codeforces.com/contest/1506/submission/111029797

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          thanks a lot bro i also did the same mistake and i had no clue why my solution was wrong

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Yeah! Thank you for your valuable reply...

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 4   Vote: I like it +1 Vote: I do not like it

          Thnak you so much :) ....even editorial is containg unordered map

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Left element must be distinct blc you find max frequent element so not any other number have frequency more than this so you can eliminate all numbers if there are total even numbers ...you can also check it via taking some test cases so you have very clear view...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tutorial for D step1: first find frequency of elements using map...then put them into a priority queue of pairs.. (priority queue will contain highest freq on its top as first — its property of priority queue containg pairs)

    step2: within while we will pop out first two pairs of priority queue..we will decreament their first value (its like we are choosing a pair from these two combination) and if they dont become 0 we will push them

    here i am taking a confusing case ex. array size 6 , array elements are arr[]={1,2,3,1,2,3} 1's freq is 2 2's freq is 2 3's freq is 2 after 1st iteration.... 3's freq is 2 1's freq is 1 2's freq is 1 after second iteration.... 2's freq is 1 3's freq is 1 1's freq is 0 after 3rd iteration ...... all will become 0

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please put the code in spoiler tag.

»
6 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Hey, MikeMirzayanov Just wanted to bring before you plagrism of two users

cyborg_7459 and cyborg7458

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 111008607

Problem B: 111007814 and 111006918

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it -40 Vote: I do not like it

    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 problems

    Moreover, 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

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You can use second and third websites for contests. [Second website(https://m2.codeforces.com/) Third Website]

»
6 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

my solution for D

sorry for my english

let 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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    how can we prove if n%2 == 0 and MAX<=n-MAX then every number will get paired up

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      you can easily prove this by induction.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How would you prove it? Please provide a proof.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can u pls tell the proof??

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +41 Vote: I do not like it

      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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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 :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can G be solved with stack??

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Problems, Thanks for such a wonderful div 3 :)

»
6 months ago, # |
  Vote: I like it -41 Vote: I do not like it

VideoTutorial of problem (B + C) link : https://www.youtube.com/watch?v=wfmIZ6XgfTY

HAPPY CODING

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    Just a friendly advice, you should try and improve your coding skills and try streaming later when you are better at coding.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -56 Vote: I do not like it

      just a friendly advice too : Don't judge a Book by its cover and Oil your own machine ..

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +50 Vote: I do not like it

        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?

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I guess problems were easier than the editorial :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the problem 1506G — Maximize the Remaining String in simpler way?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Made a video on this, you can give it a watch. https://youtu.be/NMSiu-VNfYU

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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] does not happen, since q[i] — is the maximum element among the first i elements.

We get a greedy solution if q[i]>q[i−1], then a[i]=q[i], otherwise we put the minimum character that has not yet occurred in the permutation."

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it
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$$$?

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Can someone plz give a more beginner friendly explanation to problem G. I cant understand the one given in the editorial.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, it is obvious and correct that we need to subtract from the maximal (largest). But does taking off the second largest matter? I thought it did but I came up with some examples and it seems like the second item can be any number from the list. It seems like we don't need to use the second largest. Can someone provide a counter example for this?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

boooooooooooooooooring round

»
6 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with C.. My code

»
6 months ago, # |
  Vote: I like it +46 Vote: I do not like it

When Problemsetters don't want the police to bother them! Whats-App-Image-2021-03-26-at-9-30-19-AM Credits — Problem G
(For those who don't know, "AEZAKMI" is a cheat code in GTA San Andreas to escape from the police permanently)

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can see at max we have to do n removal operations and n insertions operations in the priority queue. We dont want to deal with the numbers exactly, instead with their frequency. Insertion and Removal operations take O(n logn) time where n is the number of elements already in the priority queue.

    Also it isn't necessary to use priority queue. I used multiset to solve the same problem but the idea was similar. Have a look.

    111083842.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay i get this point but how could you be sure that deleting the top two elements from the multiset would fail and the other way of deleting one from the top two values in multiset would work ??

      1 6 2 3 2 1 3 1 surely, our code with former logic would fail on this testcase, but pass the rest of them. What if this testcase wouldn't be there, then how would you reach to the above conclusion that the latter approach of decrementing the top two values by one would only work, and the former approach of deleting the second largest value from the top value at one go would give WA

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of the same thing during the contest. But the sum of n over all test cases wont exceed 2e5. So it passes.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yes, sum of n never exceeds 2*10^5. So, how do we write the time complexity of the whole solution? Definitely not O(t * n).

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<int> a(n); unordered_map<int,int> cnt; for(int i=0;i<n;i++) cin>>a[i],cnt[a[i]]++; priority_queue<int> 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<<ans<<"\n"; //This is update which gets accepted. priority_queue<vector<int>> q; //changes are here only int n; cin >> n; map<int, int> 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";
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        //i think to avoid that problem need to use below custom_hash(originally from neal's blog)
        struct custom_hash {
            //ex define like below
            //unordered_map<long long, int, custom_hash> safe_map;
            static uint64_t splitmix64(uint64_t x) {
                // http://xorshift.di.unimi.it/splitmix64.c
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
            }
        
            size_t operator()(uint64_t x) const {
                static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
            }
        };
        
        
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Weak pretests for problem E. Well, it was ultimately my mistake as I ignored the time complexity of my code

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same here, I slipped from 129 to 628 in standings. yet it was a nice learning

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For question D,why can map pass this questionAccepted but use unorderd_map will TLE

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have a read. Blog !

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using unordered_map i got ac when contest is running. After the contest its showing tle on a test case

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with E. Why my code got TLE? Code

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    while(used[r]) r++;

    this part of your code is the reason for TLE which makes the overall time complexity of your code as O(N²)

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain why there are collisions on using unordered_map in problem [D].If my hash-map is just used for storing frequency of every unique number in the array, then how can there be any collisions in keys ?????

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to Problem G has the time complexity of O(N^2), yet it has got accepted. Can anyone tell whether the testcases are weak or I have wrongly calculated my time complexity. Link to my code

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i don't why the E problem tutorial solution seems bit lengthy to me my solution 111102730

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem D Link Can anyone tell what gone wrong with my solution it giving tle now (same solution as given in editorial)

But now it give tle on 7 th test case . Thanks

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the solution of G?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    suppose you start from index 0 and move towards right. It's all good until and unless you encounter a character c at position pos, such that it is not present further on right hand-side. So you have to keep c either from this location or from left hand — side (from its possible previous occurrences). What you can do is take the maximum character in sub-array s[0..pos]. Lets max is at position maxpos. Now, you have thrown s[0...maxpos-1]. Since you had to make the next character as maximum(for lexicographically max string) as possible without violating the rules. You have done right. Now start from maxpos + 1 instead of 0 and again do the same as done above and do not consider the letters previously selected. Time complexity would be O(26 * N) as for every character we are traversing one time full array in worst case.

    my code : https://codeforces.com/contest/1506/submission/111239608

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my submission for D: AC Submission for D My idea is similar to that of the editorial, only difference is, in each step, I am deleting exactly one occurence of the most frequent number and exactly one occurence of the least frequent number. Its still getting ACed,

Why is this correct ?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ??

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

B, C solutions with regexes instead of usual loops. Perl: B — 111112920, C — 111113262

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help what is wrong with this code ?111115251

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this solution (in Python) for question E gives TLE, but this (in CPP) does not. Can anybody explain?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did problem D have anti-hash testcases? I feel that because my unordered_map solution got TLE after the contest but my map solution got AC after I submitted it now.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same thing happened to me as well. Well it because In Unordered_map if collision increases, resulting time-complexity rises up to O(N^2). That's the exact reason for TLE for big cases.

    Read more about this here : https://codeforces.com/blog/entry/62393

    Try to use safe-map to get around this limitation of unordered_map!

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Funnily enough, I know this trick. But I was kinda running out of time (had wasted a good lot of time on B), so I didn't get time to copy the snippet because I thought anti-hash cases are rarely used, and also it was very unlikely for anti-hash cases to be incorporated in a div 3 contest.

      Turns out they did incorporate anti-hash testcases here. So yeah, I'll keep the snippet in my main template from now on. "Learned the hard way out", yes.

      My problem verdicts' table looks like:

      • A — AC
      • B — AC
      • C — AC
      • D — TLE
      • E — AC

      feelsbadman

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Used the exact implementation as given in the editorial for Question D. But resulted in TLE as I have used Unordered Map instead of Map. Learned the hard way out.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone show why my E problem code got RTE? https://codeforces.com/contest/1506/submission/111127527

Thanks alot

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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);
    
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.com/contest/1506/submission/111132652

Accepted when used map instead: https://codeforces.com/contest/1506/submission/111132742

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use custom hash with unordered maps

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain G again ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    1. then i >index of last character in t
    2. 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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me this line in G :- unordered_set used(s.begin(), s.end());

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how does this make a set with members as letters of string and arrange them backwards ?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      unordered_set -> only stores unique elements using (s.begin(),s.end()); is just saying store all the unique characters in from the start of s to the end of s in used.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So basically in problem G . we are checking if a char can be the first char finding if all unique elements left in string s can be placed after that char or not , if yes then it becomes maxC and we do that for every char in s to find the maxC that can do that which makes the string t

we are also creating a filter string which has all the elements left to be placed after maxC is placed at the front , so removal of all elements before maxC and inclusion of all elements after maxC

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

**** 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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You wrote erase and find for a set in the loop so it's more than $$$O(n\ log\ n)$$$ .

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi there, I am trying to upsolve problems from this contest and I am struggling to see why I am getting the Runtime Error on test 2 for problem E. Here is the code:

https://codeforces.com/contest/1506/submission/111272555

Sadly I cannot see all the tests and have no clue where the error might be. Any help would be very much appreciated.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone tell me where i went wrong in D -

im getting tle for test case 8

my submission

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Since , Problem E is tagged with DSU any idea , how to solve it with dsu ?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem:1506G - Максимизируй оставшуюся строку
Submission: 111543776

I just used the brute for to find the maximum alphabet until a alphabet with single occurrence or all the occurrences of a alphabets occurs

For ex: 'codeforces' in this in first loop I scan upto 'd' as it is an alphabet with single occurrence and then continue further. 'abbac' in this for first loop I scan upto 2nd 'b' as this is the last occurrence of 'b'.

Can anyone help what is the error

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[Problem E] I invented a very clean implementation of the solution to problem E.

  1. Both for max and min, maintain a pool of unused numbers;
  2. If V[i] == V[i-1], pick the most relevant element from the pool and add to solution;
  3. 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).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new to code forces and I have been writing this contest in practice mode I need help! I have trouble regarding problem B this my code I didn't use the greedy or DP approach it has passed almost all tests but it was failing on some tests I have found out through the error that it might be the input where all characters in the string are '*'.but I couldn't fix this I still believe this the correct code can anybody help me through this

include<bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; for(int i=0;i<t;i++) { string s; int n,k; cin>>n>>k; cin>>s; int a[n]; for(int j=0;j<n;j++) { a[j]=0; } int l=0; for(int k=0;k<n;k++) { if(s[k]=='*') { a[l]=k; l=l+1; } } int c,d,e; c=a[0]; for (int p=0;p<n;p++) { if(a[n-1]!=0) {d=a[n-1]; break; } else if(a[p+1]==0) { d=a[p]; break; } else {d=c}

}

if(d==c||n==1) { e=1; } else { e=(d-c-1)/k + 2; } cout<<e<<endl; } return 0; }

I hope I will find a solution thanks

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The logic of your program is not correct. You cannot get correct answer with dividing by k the quantity (or positions) of asterisks. Asterisks may be located consecutively in one part and in (k-2) places in another part. Initialize array a with -1 instead of 0. Analize next asterisk position and remember position of the last asterisk you took to result.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      hey i'm having the same issue. can you give an example where the above logic fails. i couldn't think of any such test case

      Edit: I found a testcase that wrongs my logic taking s as ADADADADA (A is asterisk and D is dot) with k=5 gives 3 as answer but it should be 4 I think the greedy approach is the best method

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        The wrong idea of the solution above is to divide by k the distance between the first asterisk and the last asterisk. For example, k=3 and only all even positions filled with asterisks, all odd positions are filled with dots (1-started numeration):
        k=3
        n=30
        .*.*.*.*.*.*.*.*.*.*.*.*.*.*.*
        Correct answer is 15, all asterisks must be replaced.
        (30-2) / 3 is less than 15.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why for test case 7 5 **.... in problem B the answer is 3?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

whats the time complexity for problem g (the code presented in this editorial

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

PLS HELP T-T

I keep getting anything after testcase #302 wrong and have no idea why. I read the editorial and understood it, but I can't figure out whats wrong with my code since it's pretty different from the editorial solution.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef char ch;

/*
Convert first and last * to X
Go maximum distance each time to replace each *
*/
int tc, n, k, aP, res; str s;

void solve(){
  res = 0;
  cin >> n >> k >> s;
  int fs;
  bool first = true, found;
  for(int i=0;i<n;i++){
    if(s[i] == '*'){
      if(first){
        s[i] = 'X'; 
        first = false;
        fs = i;
        res++;
      }
      aP = i;
    }
  }
  s[aP] = 'X';
  if(fs < aP) res++;
  int l=0;
  while(l<n){
    if(s[l] == 'X'){
      found = false;
      for(int j=1;j<=k;j++){
        if(s[l+j] == 'X'){
          found = true;
          break;
        }
      }
      if(found == false){
        for(int j=k;j>0;j--){
          if(s[l+j] == '*'){
            s[l+j] = 'X';
            res++;
            break;
          }
        }
      }
    }
    l++;
  }
  cout << res << endl;
}

int main(){
  cin >> tc;
  for(int i=1;i<=tc;i++){
    solve();
  }
  return 0;
}

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1506/submission/113624690

Can someone help me in this? getting runtime on test 2 in E.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem D I followed the same approach as what was given in the editorial but still I am getting time limit exceeded I don't know why can anyone explain this to me this is my code for problem D

include<bits/stdc++.h>

using namespace std;

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin>>t; while(t>0) { priority_queue q; unordered_map<int,int> m; int n; cin>>n; int j; for(int i=0;i<n;i++) { cin>>j; m[j]++; } for (auto x : m) { q.push(x.second); } int total = n; while(q.size()>1) { int a = q.top(); q.pop(); int b = q.top(); q.pop(); if(b>0) { a--; b--; total = total-2; if(a>0) { q.push(a); } if(b>0) { q.push(b); } } else { break; } }

cout<<total<<"\n";

    t--;
}

}

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find the error in my code ?? getting WA https://codeforces.com/contest/1506/submission/119290797

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I through the comment side silently

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F: It would be much appreciated if someone explains the solution in more depth.

Thanks in advance.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a doubt in problem B . Let's say a testcase is -: 7 3 .*....* Then , the editorial solution will give ans = 1. But it should be two because first and last '*' must become 'x'.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is guaranteed that the distance between any two neighboring '*' characters does not exceed k.