Correction: Both are going to be plagiarized. xD
1 Like
âŚXD
It will depend upon the internal implementation of the unordered map. Maybe make a random test case generator and match output with Accepted solutions.
Whatâs your logic precisely?
Actually @tarini_1407 havenât made any attempts on any questions. It just posts to annoy @taran_1407 xP
1 Like
For (a, b) to contribute to the answer, freq[a] >= b && freq[b] >= a. Thus, if we for some number(say num), we know the freq[num], candidates for b are 1, 2, 3, ⌠num. Which ones will actually be considered? The ones whose frequency is > num.
So, build merge sort tree on frequency array. Iterate through all the numbers, say freq of current number is curr. Check how many numbers have frequency > curr by querying the merge sort tree in range 1 to curr.
I hope it is clear!
Oof I did the exact opposite. My underlying array for the merge sort tree was the numbers 1 to 1e6 instead of the frequency values 
Thanks for explaining your way
I actually solved this in java. In Java, there is no such way where we can get the number of elements smaller than x. We have the function floor, which returns the element less than or equal to x. So, Order statistic tree is a must, at least for java users.
Thatâs not n^2, read the editorial, see Quick Explanation point no. 2.
Happy Coding.
If all elements are distinct, the inner loop will be executed only F[i] times, which is 1 in your test case. So, the Inner loop terminates after one iteration each time.
In my code CodeChef: Practical coding for everyone inner loop is running k times where k = no of distinct elements so in worst case (n times)
so the complexity is n^2. for the value of n=10e6 it should give TLE??? PLEASE HELP âŚ
Or it could be one of his real fangirls appreciating his editorials? We never know 
Your soln takes more than 15 sec in the worst case and you are right. For now, assume that test cases are weak and each test case had no of unique elements <5k.
Haha. (slow claps). Very funny.
but i lose 60 rating points by considering the problem is correct and many users get 100 points just by using brute force (that shouldnât be work even for 30 points).