PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Observation, Amortized analysis and data structures.
PROBLEM:
Given an array A of length N, find out the number of ordered pairs (a,b) such that a appears at least b times in array while b appears at least a times in the array.
QUICK EXPLANATION
- Sort the given array, and for every position, iterate over the positions having less than the frequency of current element.
- Above solution works in overall O(N) time because, at every iteration, we iterate over at most F[i] elements in each iteration where F[i] is the frequency of A[i]. Since \sum F[i] = N, Overall complexity is O(N).
EXPLANATION
For this problem, I have two solutions to offer, First the intended solution, which is used by Setter and Tester, while the other one is my solution.
Let us make input in form of frequency mapping tuples (A[i],F[i]), where F[i] denote frequency of A[i] in input array.
Bruteforce Solution: Iterate over every ordered pair (i,j), i \leq j of values and check if F[j] \geq A[i] and F[i] \geq A[j] holds.
Since we iterate over all pairs of values, this solution has complexity O(N^2).
Now, let us rewrite the conditions of a valid pair. For pair (A[i], A[j]) to be valid, we need F[j] \geq A[i] and F[i] \geq A[j].
Let us sort these tuples in increasing order of A[i] and run the same loops as BruteForce. Now, notice, that for any (A[i], F[i]), if we get the position A[j] > F[i] for any position j, we can safely see, that No position k, k > j will satisfy F[i] \geq A[k]. Hence, we can break out from internal loop as soon as we reach a value A[j] > F[i].
Now, What is the time complexity of this solution? This is where Amortized Analysis comes into play.
See, For every position, we iterate over at max F[i] element in inner loop. Since N = \sum F[i], The overall solution complexity is bounded by N, resulting in overall O(N*logN) solution due to sorting.
Now, Let’s discuss Editorialist solution in brief, who didn’t get the observation at first.
Make frequency tuples same way as above solution and sort tuples by non-decreasing order of F[i]. If we focus on condition A[i] \leq F[j], we know that this condition will hold for a suffix of the array due to the non-decreasing order of F. This way, Now we need to count the number of positions in Suffix [j, N-1] for which A[j] \leq F[i]. Let’s call (j, F[i]) a query, and j is the left end of query range, right end being the end of the array.
There exist a more general problem which can be applied here. Given an array of length N, Perform two type of operations. First is to update a single element. Other is to count number of elements \leq x in range [l, r].
Editorialist just uses Order statistic tree, along with sorting queries (j, F[i]) by decreasing order of j, and answer queries and add elements to order statistic tree as the j decreases, and making queries when the current range of added elements correspond to query range.
The time complexity of this solution too is O(N*logN) but is probably slower than the first solution due to the constant factor.
This was a lesson, that observations matter. 
Related problem
The problem Tufurama seems a lot similar to this problem, though have quite a different solution which is worth a try.
Also, The problems KQUERY and KQUERY2 are nice problems to practice if you tried the second solution.
Time Complexity
The time complexity of both solutions is O(N*logN) but the first one has lower constant factor than the second solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
