Обсуждение @ 1535. Хоббит или Туда и обратно @ Timus Online Judge

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

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

svr 1535 Proof? [1] // Задача 1535. Хоббит или Туда и обратно 4 мар 2007 20:17

Simple algorithm but hard proof?
How to prove that some construction in this problem
is optimal?

Victor Barinov (TNU) Re: 1535 Proof? // Задача 1535. Хоббит или Туда и обратно 4 мар 2007 22:55

For minimal permutation must be:
(p[i] - p[i+1]) * (p[i-1] - p[i+2]) < 0