Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

OmarAnalog's blog

By OmarAnalog, history, 16 months ago, In English

Why ternary search fails for Div2c Today.

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Mine didn't.

»
16 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Finding the minimum of the parabola doesn't guarantee that the line won't intersect with it.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Code
  • »
    »
    16 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    why can't we just find k that is closest to b through binary search?

    We need (b-k)^2 -4ac to be <0

    So, we need to find the value of k closest to b. If this doesn't satisfy <0 condition then rest values will never satisfy. Am I missing something? Handle SHARANTEJAREDDY

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      you are correct, I just shared my approach from what I remembered from JEE quadratic equations :).