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

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

@anon56994723

@anon70990627

``````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

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

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!

It’s just the f(x) I think

1 Like

yes its f(x)

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

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

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

@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.

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

2 Likes
The text passage is a discussion about a coding problem, specifically a binary search algorithm to find a minimum value in a function. It includes a question about the mathematical properties of the function and its minima.
no_question

the passage does not contain a direct mathematical question that requires a numerical or algebraic answer. instead, it is a discussion about a coding problem and the mathematical reasoning behind the solution. while there are mentions of mathematical concepts, they are not presented as questions to be solved but rather as explanations or justifications for the coding approach.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Gives WA on "The king of snakes" {CodeJunk Contest}

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

@anon56994723

@anon70990627

``````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

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

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!

It’s just the f(x) I think

1 Like

yes its f(x)

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

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

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

@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.

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

2 Likes
user
The text passage is a discussion about a coding problem, specifically a binary search algorithm to find a minimum value in a function. It includes a question about the mathematical properties of the function and its minima.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question that requires a numerical or algebraic answer. Instead, it is a discussion about a coding problem and the mathematical reasoning behind the solution. While there are mentions of mathematical concepts, they are not presented as questions to be solved but rather as explanations or justifications for the coding approach.