Why ternary search fails for Div2c Today.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
2 | maomao90 | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Why ternary search fails for Div2c Today.
Name |
---|
Mine didn't.
Yours is binary search
No? I found the lowest value by ternary search and then did lower bound on original array.
its binary search.
Finding the minimum of the parabola doesn't guarantee that the line won't intersect with 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
you are correct, I just shared my approach from what I remembered from JEE quadratic equations :).