Hello friends can someone tell me how to approach this problem ??
@vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299 @meooow @john_smith_3
1 Like
It’s a problem of counting sort.I hope you have already read the editorial. What part you failed to understand?
1 Like
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—
initially,
score= p%q;
then in loop:
a[score]++;
sc=(p*score)%q;
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 : https://www.codechef.com/viewsolution/18311708
Thanks got it now 