### 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.