what about ternary search in this task?



Edited by author 01.10.2020 22:01

Well I tried to do so but got wa4.
I also looked at that guy's solution where he just takes the average of all p[i]. And I still cannot understand why it's right bcz, like, it's squared distance not just linear...

Edited by author 29.07.2022 12:21

It's because of the first derivative.

I tried it, and get WA4. I suspect I have a bug but idk where.

I did some more digging.

For those interested, try running your ternary search against the following test case (and then compare with the avg approach):
```
20
9 8 5 12 5 6 89 45205 3554 1585 554422 654235 545324 548835 456432 804654 234758 444 5668 56435
```

This in both cpp and python gives the wrong answer. By switching to the `Decimal` library in python, I was able to move past 4, and get TLE on 5.

Using gmp in cpp might get you to AC, but I think the takeaway here is to only use ternary search when you can set the problem up to have an answer close to 0.