Please help me in SUMQ

help
, , ,
1

Request help for Triplets(SUMQ) from June 2017 long challenge. I arrived at the following optimization (http://ideone.com/nSLdfk) however I got a WA for all my test cases. I would be thankful if anyone could take a look. Regards.

2

Your program isnt working for larger values-

Input
1 
3 3 3
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
Your Output
0
Expected Output
5292

Most common reasons for error is -

int a= 1000000,b=1000000;
long long int c = a*b // a and b are still int. Thus overall a*b is int and it overflows. The overflowed result is stored in c

Or

Not using modulo properly, such that overflow occurs before modulo.

EDIT: Can you explain your approach? I’m having trouble finding whats wrong because i cant perceive what you intended and what must have went wrong.

3

My approach:
Sort arrays A and C; calculate and store their sum in arrays (to minimise computations later). Then for each of the elements in B, find ‘index’ in arrays A and C and apply the following optimization to the calculation part : (( (indexA+1) * B[i])%mod+(sumA[indexA])%mod )%mod * (((indexB+1) * B[i])%mod+(sumB[indexB])%mod)%mod

4

The logic part seems fine. I think you should look at another person’s code for comparison to catch any implementation error. There was a thread discussing this Q and many similar codes were posted there, give it a try. I can only help this much cause i havent solved the Q yet (planning to solve sometime later when i forget the approach and stuff)

5

Indeed, your logic and modulos are correct. However, you have an issue with your binary search, it’s not searching for the upper bound correctly, effectively missing middle cases. You know what, you can use STL for common functions like upper bound to reduce errors. Try changing to the following lines:

int indexA = (int) (upper_bound(sumA, sumA+p, B[I]) - sumA) - 1;
int indexC = (int) (upper_bound(sumC, sumC+r, B[I]) - sumC) - 1;
 // make these "<" instead of "==", since it is possible to count sumA[0] and sumC[0]
if(indexA < 0 || indexC < 0)
{
	main_Res +=0;
	continue;
}

I tried it and I think that’s enough for AC.
If you’re having trouble with binary search (implementation part), you can refer to tutorials like TopCoder and GeeksforGeeks.

1 Like
6

Yes!! Even i was thinking that the issue is somewhere in that search (and using that upper bound would solve the problem).

7

@hikarico tried it with both suggestions; got AC in the second part of test cases still WA in the first part : https://www.codechef.com/viewsolution/14264650 ; Any suggestions?(BTW thanks for the help :slight_smile: )

1 Like