Please explain the O(m+n) approach of this editorial https://discuss.codechef.com/questions/61687/amr14c-editorial.
Asked by: Raghav_Grover on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
Its brute force solution of O(n^2) is quite clear. Here we check the condition for each pair of number in array.
The naive solution would be:
long long int answer = 0;
for(int i =0 ; i < N ; i++)
for(int j = 0 ; i< N ; j++)
if( (A[i] + A[j] <= x)
answer++;
cout<<answer<<endl;
However, this solution will result in TLE verdict.
Better Approach
We are required to find all such pairs (A[i],A[j]) in A[] such that A[i]+A[j]<=X
First recall the property of modulo:
(a + b)%m = (a%m + b%m)%m
Using the value of a%m and b%m instead of a and b respectively will produce same result.
Thus, if our array contains A[i]%M, there will not be any change in result. For eg., if inputs are like
1
6 10 8
3 8 23 5 33 15
Array A = {3,8,3,5,3,5}
As we can see that
A[i]<M, so
A[i]+A[j]<2*M, where(A[i] and A[j] are any two elements of A)
This range could be divided into four regions:
0<=region1<=x, x<region2<M, M<=region3<=M+x, M+x<region4<2*M
It could be seen that if our sum lies in region1 or region3, sum%M<=x
Here, cases which may arise are:
Case 1: A[i]<=x
Here for each A[i], valid A[j] could lie in region1 or region3.
Valid range of A[j]:
For region1, 0 <= A[j] <= x-A[i]
For region3, (M-A[i]) <= A[j] <= (M-1)
Case 2: A[i]>x
Here, for each A[i], valid A[j] could only lie in region3
Valid range of A[j]:
For region3, (M-A[i]) <= A[j] <= (M+x-A[i])
Therefore, the problem reduces to find the count of A[j] which lies in certain countinous range. To do this, we make another array B whose size is equal to M and ith index stores the number of i in array A[]. Thus, B = {0,0,0,3,0,2,0,0,1,0} (as per example given above)
And let another array C store prefix sum of B,i.e.
C = {0,0,0,3,3,5,5,5,6,6}
Now, count of numbers whose value lies in range say r1 to r2 will be C[r2]-C[r1-1](when r1=0 the ans will only be C[r2]).
Hope this clears your doubt!!