ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1457. Теплотрасса

ternary search
Послано Григорий 1 окт 2020 21:58
what about ternary search in this task?



Edited by author 01.10.2020 22:01
Re: ternary search
Послано Neko_r_The_Best 29 июл 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
Послано Kergan 8 ноя 2022 00:32
It's because of the first derivative.
Re: ternary search
Послано sweepea 24 фев 2024 20:20
I tried it, and get WA4. I suspect I have a bug but idk where.
Re: ternary search
Послано sweepea 25 фев 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.