PROBLEM LINK:
Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar
DIFFICULTY:
Easy
PREREQUISITES:
Counting sort
PROBLEM:
Provided with means to generate 2 arrays, the task is to compare values of equal ranks in their respective arrays.
QUICK EXPLANATION
Since the number of elements in each array can be very large (<= 10^18) but the maximum possible value of an element is very small (<=100), it is suitable to use a technique similar to counting sort and calculate the answer.
EXPLANATION:
From the problem statement it is apparent that one needs to generate the 2 arrays, let them be S and B, sort them in non-increasing order, and finally find summation of S[i]$-B[i]** for all **i** and divide it by total number of elements. Since the size of **S** and **B** may not be same, the answer becomes summation of **S[i]-$B[i] for all i less than min(|S|, |B|) divided by max(|S|, |B|).
This procedure, if carried out by common O(n lg n) sorting algorithms, like quicksort, is not enough to pass the checker. Needless to say, O(n^2) algorithms are also too slow. We can see that the maximum value of any element in S or B is very less, 100 to be precise, so we can easily implement an O(n) counting sort procedure.
First we need to store the frequency of each element of S and B in separate arrays. Since each value is calculated as (p^i)%q, we only need arrays of size qS and qB for arrays S and B respectively. Next we simultaneously travel down the frequency arrays, adding the differences together appropriately. As soon as we reach the end of any one array, we have covered min(|S|, |B|) elements. All that remains now is to divide our sum of differences by max(|S|, |B|) and we get our answer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.