Gives WA on "The king of snakes" {CodeJunk Contest}

help
, ,
1

Problem Link

This is the question from recently CodeJunk Contest, It gives me WA , I try my best but I can’t Figure out how to correct my code.

My approach->>
Basically Using Binary search from low =1 to high=m , where m is the maximum value element in the array
comparing the f(mid) with my global ans, and simultaneously also check for mid-1 and mid+1 half{similar that we do ne Binary search with some required modification}

PS:->> I have done 2 hours on this but doesn’t reach to the solution, Please help me if you can.

My solution

Thanks in Advance.

@anon56994723

@anon70990627

2 
while(l<=r)
{
     mid=(l+r)/2;
     sum1=sum(mid-1), sum2=sum(mid),sum3=sum(mid+1)
     if(sum1>sum2 && sum2<sum3) {ans=mid; break;}
     if(sum1>sum2 && sum2>sum3) l=mid+1;
     else r=mid-1;
}

try this, it will work
why? beacuse the function f(x) is a curve which is decreasing and then increasing

4

Thanks Buddy!!, but can you please elaborate what is this sum function ?? , I didn’t understood this.

5

Its not necessary to check function values of both mid-1 and mid+1.
We know that the function attains the peak in a singular point and from that point the function value increases.So we use the same binary search to calculate the peak value by comparing the function values of mid and mid+1 alone,till the binary search auto finishes by using (l<r) case.
The last value of mid is the answer which we computed in O(n*log n)!

If stuck ---->https://pastebin.com/h7i1N6S6

Happy Coding!

6

It’s just the f(x) I think

1 Like
7

yes its f(x)

8

I didn’t get the part where you said that it will have only one minima. Can you give me some hint regarding this?

9

my bad…it can have 2 minima as well, but the conditions i used probably made sure we are choosing the smallest one.[ arr={1,4}, k=1, x=2,3 will give f(x) as 3]
I believe it can be proved mathematically that minima will always lie in a range of at most 2 elements, but i didn’t try to prove it during the contest, and i didn’t think much about it later

10

This condition is valid for any minima. So, how can we tell that it will be global minima?

11

@sebastian There will be only two integers x1 and x2 such that f(x1 ) = f(x2 )

Differentiating f(x) twice, we find that f''(x) will have only one root corresponding to a single minima/maxima. f'(x) shows that the it will be a minima.
If x is an integer, a single value will give the minima else, two values will give the minima.

12

Minima will always be at sum/n. So, it can be solved in O(n)
https://www.codechef.com/viewsolution/35877309

2 Likes