Hello friends can someone tell me how to approach this problem ??

@vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299 @meooow @john_smith_3

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 : CodeChef: Practical coding for everyone

Thanks got it now