Thanks for sharing such a valuable insight with us.

Thanks man!!

Thank you bro you saved my life

It is very annoying. Please MikeMirzayanov fix.

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

Seems like spoilers are broken now

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

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

Blog about it! Luckyli I faced this while practicing. And today that experience helped me!

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

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.

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

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.

Hope this helps

Maybe 111074804 this can help.

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.

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

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";

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.

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.

Have a read. Blog !

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

Hopefully this will clear your doubts — https://codeforces.net/blog/entry/76206?#comment-606743

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

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

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

Its because of this line :-

auto itr = lower_bound(s2.begin(),s2.end(),-a[i]);

As said in this comment using lower_bound like this would result in O(n) complexity . Hence the overall time complexity is O(n^2)

Instead of this use this:-

auto itr = s2.lower_bound(-a[i]);

I submitted your code only with this modification and it gave AC

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