Hello friends can someone tell me how to approach this problem ??
It’s a problem of counting sort.I hope you have already read the editorial. What part you failed to understand?
Yeah I have read the editorial but I am not able to get started with it. Mostly implementation is the problem.
As both have same formula (p^i)%q we know the value will lie in range 0 to q-1 so we will take 2 arrays of size qs and qb.
Then we will fill up the frequencies of each number from 0 to q-1 by iterating for their disciples. Something like this—
then in loop:
Then we can use the freq array to compute answer. We will have to use 2 pointers for each array(say i and j). Start from their back and find min(a[i], b[j]). If it’s zero then that means there is no disciple of same rank for both.
Subtract from both min.
Add (i-j)*min to sum.
If a[i]==0 decrease i
If b[j]==0 decrease j.
This means either there are no disciples of that rank or we have already taken them into consideration.
Finally print sum/max(n,m)
My submission : CodeChef: Practical coding for everyone
Thanks got it now