text: 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
explanation: The document is a discussion thread from a coding contest, specifically about a problem titled "The king of snakes" from the CodeJunk Contest. The user is seeking help with a solution that is giving a wrong answer (WA). The thread includes the user's approach, a code snippet, and explanations from other users about the function and the binary search method used. The discussion revolves around the mathematical properties of the function and how to find the minimum value efficiently.
  
  The document contains multiple questions and answers related to the problem and the solution approach.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: 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
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a discussion thread from a coding contest, specifically about a problem titled "The king of snakes" from the CodeJunk Contest. The user is seeking help with a solution that is giving a wrong answer (WA). The thread includes the user's approach, a code snippet, and explanations from other users about the function and the binary search method used. The discussion revolves around the mathematical properties of the function and how to find the minimum value efficiently.
  
  The document contains multiple questions and answers related to the problem and the solution approach.
  
  Label: multiple-question-and-answer