I tried really hard for this problem but kept getting WA till the end (though i got partial points using brute-force).
Here’s what I tried :
https://www.codechef.com/viewsolution/14076399
2 Likes
One mistake that I could clearly see is that you need to define lx and lz as long long, as there would be overflows and I think your solution doesn’t work because of overflows, try taking mod after each operation and declare all of them as long long rather than ints.
You are calcutaing the prefix sum in the beginning and then sorting the arrays, which makes the prefix sum wrong. Later the whole algorithm which returns index does not match with the prefix sum.
So first sort and then find the prefix sum. Use long integer to escape from overflow issues.
1 Like
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.