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
“”"
Now we need to count the number of positions in Suffix [j,N−1] for which A[j]≤F[i]
“”"
Cannot this be done in a simple way like this instead of using order Statistic Tree?
Just maintain a set (cpp STL) of all elements from j to N-1 .for knowing the number of positions or which A[j]≤F[i] just use upperbound on that set.
when we want for i-1 just add ith element to that set and use upperbound again.
This takes logn time for each i .
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.
I think there are weak test cases because n^2 approach is working for 100 points . just make array of all different numbers then use two loops for checking all i and j .
here is my solution . .
https://www.codechef.com/viewsolution/21256684
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 https://www.codechef.com/viewsolution/21256684 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).
@motif
Lazy tester that what I can say.
If I were in place of tester, this counter tc would have been the first tc which I would have included.
From past seven rated contest I’m seeing complains about weak tc
P.S. - Posting as the separate answer instead of the comment. Hoping @admin will see this.
Yep you are right , this should be the first counter test case because if this problem can be solved in n^2,then the problem is a cakewalk and the whole story of this editorial ( that sort the array , f[i] , O(n) , observation etc…) makes no sense ,I hope that next time @admin will take care of this.