ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1457. Heating Main

ternary search
Posted by Григорий 1 Oct 2020 21:58
what about ternary search in this task?



Edited by author 01.10.2020 22:01
Re: ternary search
Posted by Neko_r_The_Best 29 Jul 2022 12:20
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
Re: ternary search
Posted by Kergan 8 Nov 2022 00:32
It's because of the first derivative.
Re: ternary search
Posted by sweepea 24 Feb 2024 20:20
I tried it, and get WA4. I suspect I have a bug but idk where.
Re: ternary search
Posted by sweepea 25 Feb 2024 18:59
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.