Обсуждение @ 1651. Кратчайшая подцепь @ Timus Online Judge

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

Обсуждение задачи 1651. Кратчайшая подцепь

Sq1 Could anyone provide me with an O(n) solution? My works O(n log(n)) [1] // Задача 1651. Кратчайшая подцепь 5 янв 2017 21:36

Could anyone provide me with an O(n) solution? My works O(n log(n))

Solver Re: Could anyone provide me with an O(n) solution? My works O(n log(n)) // Задача 1651. Кратчайшая подцепь 8 июн 2026 15:30

BFS for shortest path, but not over original graph - over the chain itself. There are edges of weight 1 and 0.