You must take modulus after every operation.
This is my solution - CodeChef: Practical coding for everyone
1 Like
this is what i tried
I was getting wa though three cases did pass later i got a tle . please help. also someone please upvote this because i am unable to ask questions because of just 1 karma i have.
#include<stdio.h>
#include<stdlib.h>
long long int x[100004],y[100004],z[100004],sumx[100004],sumy[100004],pro[100004];
long int binarysearch(long long int arr[],long int n,long int high,long int low)
{
//ignore the pro array it is insignificant
long int mid,i;
while(low<=high)
{
mid=(high+low)/2;
if(arr[mid]==n)
return mid;
else if(arr[mid]>n)
{
high=mid-1;
}
else
low=mid+1;
if(low==high)
return low;
}
}
//void merge(long int arr[],long int left[],long int right[],long int nleft,long int nright)
/*{long int i=0,j=0,k=0;
while(i!=nleft&&j!=nright)
{if(left[i]<right[j])
{arr[k]=left[i];
k++;
i++;
}
else
{arr[k]=right[j];
k++;
j++;
}
}
while(i!=nleft)
{arr[k]=left[i];
k++;
i++;
}
while(j!=nright)
{arr[k]=right[j];
k++;
j++;
}
}
void mergesort(long int arr[],long int n)
{long int i,nleft,nright,left[50002],right[50002];
if(n<2)
return;
else
{
nleft=(n+1)/2;
nright=n-nleft;
for(i=0;i<nleft;i++)
left[i]=arr[i];
for(i=0;i<nright;i++)
right[i]=arr[nleft+i];
mergesort(left,nleft);
mergesort(right,nright);
merge(arr,left,right,nleft,nright);
return;
}
}*/
int compare(const void* a, const void* b)
{
if(*(long long int*)a - *(long long int*)b < 0)
return -1;
if(*(long long int*)a - *(long long int*)b == 0)
return 0;
if(*(long long int*)a - *(long long int*)b > 0)
return 1;
}
long int main()
{
long int p,q,r,i,flag,kx,kz;long int j,m;long long int ans,mod=1000000007;int t;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%ld %ld %ld",&p,&q,&r);
if(p<r)
flag=p;
else
flag=r;
for(i=0;i<p;i++)
scanf("%lld",&x[i]);
for(i=0;i<q;i++)
scanf("%lld",&y[i]);
for(i=0;i<r;i++)
scanf("%lld",&z[i]);//printf("y");
//mergesort(x,p);
//mergesort(y,q);
//mergesort(z,r);//printf("k");
qsort(x,p,sizeof(long long int),compare);
qsort(y,q,sizeof(long long int),compare);
qsort(z,r,sizeof(long long int),compare);
for(i=0;i<flag;i++)
pro[i]=x[i]*z[i];
sumx[0]=x[0];
sumy[0]=z[0];
for(i=1;i<flag;i++)
pro[i]=pro[i-1]+pro[i];
for(i=1;i<p;i++)
sumx[i]=sumx[i-1]+x[i];
for(i=1;i<r;i++)
sumy[i]=sumy[i-1]+z[i];
/*printf("\n");
for(i=0;i<p;i++)
printf("%ld ",x[i]);
printf("\n");
for(i=0;i<q;i++)
printf("%ld ",y[i]);
printf("\n");
for(i=0;i<r;i++)
printf("%ld ",z[i]);*/
for(i=0;i<q;i++)
{
kx=binarysearch(x,y[i],p-1,0);//printf("kx is %d",kx);
kz=binarysearch(z,y[i],r-1,0);//printf("kz is %d",kz);
while(x[kx]<=y[i]&&kx<p)
kx++;
if(kx==p)
kx--;
while(z[kz]<=y[i]&&kz<r)
kz++;
if(kz==r)
kz--;
if((kx==0&&x[kx]>y[i])||(kz==0&&z[kz]>y[i]))
{
ans=(0+ans)%mod;
continue;
}
if(x[kx]>y[i]&&kx!=0)
kx--;
if(z[kz]>y[i]&&kz!=0)
kz--;
//ans=(((((kz+1)%1000000007*sumx[kx]%1000000007)%1000000007)+((((kx+1)%1000000007*sumy[kz]%100000000007)+((((((kx+1)%1000000007*(kz+1)%1000000007)%1000000007)*y[i]%1000000007)%1000000007)*y[i]%1000000007)%1000000007+ans)%1000000007;
ans=((((((((((kz+1)%mod)*(sumx[kx]%mod))%mod)+((((kx+1)%mod)*(sumy[kz]%mod))%mod))%mod)*(y[i]%mod))%mod)%mod)+((((sumx[kx]%mod)*(sumy[kz]%mod))%mod)%mod)+(((((((((kx+1)%mod)*((kz+1)%mod))%mod)*(y[i]%mod))%mod)*(y[i]%mod))%mod)%mod)+ans%mod)%mod;
//printf("tt");
}
//printf("%lld\n",ans);
printf("%lld\n",ans);
ans=0;
}
}
due to lack of karma i cannot upload the image of my code . please help
6 Likes
There is also an overflow in the code at the line where you accumulate the answer in sum variable.
This one is easy to miss.
what is happening is this :
sum += (somthing)%MODULO
which is same as:
sum = sum + (something)%MODULO
while I believe the correct one should be:
sum = (sum + something)%MODULO
Link to my AC using this approach :
https://www.codechef.com/viewsolution/13995178
kunal12libra →
-
You can use the “code sample” feature it will make your code printed correctly.
-
You can use pastebin, I find it a good way to share code.
I’ll directly discuss an approach for full points here.
F(X,Y,Z)=(X+Y)*(Y+Z) and condition to be satisfied is that Y>=X and Y>=Z as well. So now, You have Three arrays A,B,C. X will be from array A, Y will be from Array B and Z from array C. So, Suppose Array A contains a,b,c,d,e. Array B contains f,g,h,i and Array C contains j,k,l,m. First thing to do is to sort the Array A and C. By doing so, we will get to know how many elements in array A and Array C are less than particular B[i]. This will be done applying binary search for each value of B[i]. For example if after sorting A contains a,b,c,d,e and values in A which are less than or equal to B[0] are a,b,c(I’m discussing here for B[0],rest will be done in the same way) and after sorting if C contains j,k,l,m and j,k are the values which are less than B[0]. Now,
let B[0]=X then we have
(a+X)(X+j)+(a+X)(X+k)+(b+X)(X+j)+(b+X)(X+k)+(c+X)(X+j)+(c+X)(X+k)
After simplifying above calculation the formula which we get is
(( 3 * X)+(a+b+c) ) * ((2 * X)+(j+k))
In general manner :
((Number of elements in A less than or equal to B[i] multiplied by B[i] )+(sum of all the elements in A less than or equal to B[i])) * ((Number of elements in C less than or equal to B[i] multiplied by B[i])+(sum of all the elements in C less than or equal to B[i]))
This step should be done for all B[i]'s and sum of all will be our answer.
Note: Here number of elements <= B[i] can be found out by simple binary search and sum of all the elements <= B[i] can be found out by maintaining a Presum array.
AC Code: CodeChef: Practical coding for everyone
C++ users: please use scanf and printf
6 Likes
https://www.codechef.com/viewsolution/14068767
I am getting tle in one of the testcases. Can someone explain me why?
Complexity I calculated appears to be: O( q*(log p + log r) )
What I really did was sorted the A and C arrays, calculated cumulative sums of array A and C and then found the upper bound of A and C for every element in B.
I also did sort B in decreasing order so that once any element returns first element in either A or C as upper bound I just stop (since upper bound is first element aka 0th element I have none elements before it).
1 Like
The biggest mistake you are doing is sorting the b array which is wrong altogether because you need to answer the query as it is asked.
Look at my approach I did almost similar to you - link text
Ok listen…here is my approach…I first sort the x and z array using sort() function, then from given test case, I derived a formula for this problem which is (countx * y+sumx)*(countz * y+sumz) for every y where the countx = number of element in X array <= Y and similarly for countz. Sumx and Sumz represent the sum of all element which is <= Y.To find all these elements if you use linear search you will get tle , so instead of using linear search you can use binary search.that’s all and you are good to go!!
Here is link to my code…CodeChef: Practical coding for everyone
hey can anybody upvote me. I want to share my code which was executed in nlogn time
Here is my solution with 0.66sec. To solve this question You need to first solve the function and derive a simple relation which can give you the answer.For every element in B you need 4 things:
- Number of elements upto which the element in B is greater than elements in array A(sizeA)
- Number of elements upto which the element in B is greater than elements in array C(sizeC)
- Sum of all those elements in point 1.(sumA)
- Sum of all those elements in point 2.(sumC)
So I sorted all the 3 arrays in increasing order.Most people sorted only A and C but by sorting B you only need to traverse Array A and array C only once because the elements which are less than B[0] will always be lesser than B1,B[2]…B[q].
Here you go!
Observations:
- Mod in the sum also
- Make sure you have your exception of no numbers greater than B[i] taken care of
- More Mod.
P.S. Giff Karma ;-;
1 Like
this is what i tried but i am getting tle in 2 cases. Please help.
https://www.codechef.com/viewsolution/14219608
I think its complexity is O(n ln n) but i don’t know why it is giving tle. I have seen other solutions and their complexities is same.
my approach was:
1)take A elements
2)take B elements and store max element of B
3)take only those elements from C which are less than max of B
4)sort C
5)Now i for A ,j for B ,k for C
run loop till j<sizeof B
if condition satisfied if k has not reached limit and the next element is less than of B[j] increment k, otherwise if j has not reached its limit increment j, otherwise increment i.
still i got TLE please help!!!
Hey everyone ! Thanks for your awesome responses and solution links.
I learnt a lot from different approaches also realised the lame mistake I did -_-
Cheers !
1 Like
THe code which i have submitted use all the approaches discussed by you @sidhartp538 but still it is giving wrong answer in some of the cases I have applied mod after each operation , used quick sort and binary search too.I also derived the formula which seems correct to me . first the code was giving wa later it gave tle despite of the fact that the complexity of the code was same in both the cases . if anyone could precisely figure out what is the issue it will be highly appreciated . thanks!
@godslayer12 one more thing which no one pointed it is that you using lower_bound while you should be using upper_bound since you the last occurrence of element