Так, тут одно ребро неправильное осталось. - Может выпилим... | Технологии в Контуре

Так, тут одно ребро неправильное осталось.

- Может выпилим...?
- Ся.

Девятнадцать часов до конца контеста, мы полны сил и оптимизма, как видите. А я пришел к вам с историей о силе, усердии, плодах долгой работы и злой птичке из 93-ей задачи, которая чхать хотела на все вышеперечисленное.

Итак, дыра в виде птички, фигура в виде краба, девяносто третья задача и гарантированно существующее решение на ноль дизлайков. Это значит, что получившаяся фигура должна идеально вписаться в дырку, разместив на каждой вершине дыры по одной вершине фигуры. Это… непросто.

Во всяком случае, алгоритм с этой задачей не особо справился и от решения на ноль баллов был бесконечно далек. Для таких случаев у нас есть ручной решатель, где мы можем ручками помогать алгоритму. Подвигали вершины, запустили решатель, снова подвигали, снова запустили, снова подвигали.

Этим и занялся один из членов нашей команды, Дима — часов так семь назад. До этого он уже справился с несколькими такими задачами и был полон оптимизма. Задача выглядела грандиозно и обещала много баллов. Но…

⁃ «Как-то туго идет. А давайте запилим отображение оригинальной длины ребра?»

Через час стало понятно, что задача идет как-то медленно и хорошо бы немного подтюнить визуализатор. Подтюнили, визуализатор теперь умел отображать не только текущую длину ребра, но и ожидаемую. Новую функцию для визуализатора скидывали в телеге, потому что, ну… Ой, как будто вы никогда не перекидывали код в мессенджерах.

Обновление на лету прошло успешно, но глобально ситуацию не исправило. Поэтому ребята по ходу дела написали еще несколько улучшений для визуализатора. И вот после этого…

И после этого мучения продолжались. Дима все больше мрачнел, визуализатор все больше тормозил, но задача все же двигалась к решению. Часа так через четыре осталось всего несколько неправильно установленных вершин и загадочные 3 дизлайка, непонятно откуда берущиеся. Автоматическая решалка не справлялась, Дима не справлялся, а еще через несколько минут не справился ноутбук и намертво завис.

Всем резко стало грустно. На решение потрачена куча времени, сохранить его не выходит, все зависло, а время работы над задачей потихоньку подкатывало к пяти часам. Придумывались разнообразные варианты спасения ситуации, перезапуска всего на свете, какого-то сохранения решения. Был сделан отчаянный скриншот, по которому можно было попробовать восстановить решение — но это заняло бы кучу времени, а на чертову птицу уже и смотреть не хотелось. Впрочем, пока все эти варианты придумывались, ноутбук таки отвис.

И вот решение отвисло, но алгоритмический двигатель был больше недоступен, ноутбук бы точно завис. И началось долгое-долгое двигание вершин. Три дизлайка в какой-то момент превратились в четыре («нам что, уже сервер дизлайк поставил?»), а последние ребра никак не желали встать так, чтобы удовлетворять требования по максимальному растяжению.

Закончилось все благополучно и через полчаса перебора Дима таки добил задачу, убив на нее больше пяти часов. Ноль дизлайков, оптимальное решение, но чертова птица теперь навечно будет символом боли и страданий.