can anyone give a hint to solve this problem?

help
1

Any hint to solve this problem?
http://codeforces.com/problemset/problem/466/C

2

You can use a prefix sum array and binary search to solve it in \mathcal{O}(n \log n). Since you asked for a hint, Iā€™m not giving further details. You can also solve it in \mathcal{O}(n) with a little more clever thinking, and this way is described in the tutorial.
I can elaborate further if you get stuck, good luck :slight_smile:

1 Like
3

I have solved problems on prefix sums and brute force but how to apply binary search to it

4

for i:array
for j:i+1 to end
find a=do binary search for s/3
find b=do binary search for 2s/3
cnt+=1
kindly correct this answer

5

Let the sum of the whole array be S. If you find a valid i upto which the prefix sum is \frac{S}{3}, you can binary search the prefix sum array for the range where the values are \frac{2S}{3}, and those will be valid choices of j.

6

do we have to do upper bound-lower bound for 2s/3

7

Yes, exactly. If you are using C++ there is also the equal_range function.

8

Thanks for your help.

9

No problem!