krillin is dead help

general
1

Can someone please tell me where I am wrong . Here is my


[1]. I maintained 2 segment trees for maximum query and for sum query and then I found lower bound of prefix sum for the interval where my sum/2 lies . Please someone reply :( what is the error in my code


  [1]: https://www.codechef.com/viewsolution/18887866
2

The problem is in your (sum/2) thing…see this testcase->

1

2 1

3 4

1 1 2

Now when you run this testcase, your code will give 2 as output which is correct but when you see your median, it shows 1 which is wrong…So what i want to say is that for this testcase your answer is right but your median is wrong…the wrong calculation of median leads to WA in some other testcase.

The problem is in (sum/2) as i said…in this testcase sum is 7 so sum/2=3…now you are searching for 3 whereas the median element is 4(middle element) . Since first element is 3 your code displays index 1(1-based) as median whereas median is 2.

So simply replace your (sum/2) by (sum+1/2)…if sum will be even then both will be same but if sum is odd, they will differ and hence the median.

I did this change to your code and got AC.

Hope this helps!!

5 Likes
3

can someone help me please? Here is my


(https://www.codechef.com/viewsolution/18902163). I know its lengthy. but just tell me the test case where it fails please.
4

Thank You very much @swapnil159 , This comment could have saved my whole day. I was doing the same mistake (sum)/2 thing instead of (sum+1)/2 . Thank you :slight_smile:

5

Holy Moly.
Thanks a lot man , it helped me for sure.Silly mistake during contest cost me a question :slight_smile:
Thanks again for helping me out.

6

@swapnil159 thanks a lot dude. I made the same mistake.

7

its okk guys…took me 3 hours to figure out this in my code.

1 Like