Сегодня ночью закончился квалификационный раунд YTCF 2018. Хотелось бы обсудить задачи.
A: в задаче требовалось выбрать минимальное по размеру множество точек на прямой, от которых расстояние до остальных было бы не более R (от какой-либо из выбранных). В одномерном случае эта задача тривиальна, но мне интересно, существует ли какой-то эффективный алгоритм для двумерного случая?
B: стандартная одномерная динамика, нет особого смысла что-то по ней писать.
C: по условию вам даны две карты города — новая и старая — в следующем формате:
- множество ключевых точек, заданные двумя вещественными числами;
- улицы, являющиеся ломаными, построенными на ключевых точках.
Количество ключевых точек на карте N, количество улиц M и суммарное количество отрезков во всех улицах L1 + L2 + ... + Lm не превосходят 104.
Целью задачи было определить, какие старые улицы находятся близко к каждой из новой. Старая улица располагалась близко к новой, если все её точки находились на расстоянии не более D от какой-либо точки ломаной, образующей новую улицу. (D также дано во входных данных).
Я не придумал ничего оптимальнее, чем решение за 
— для каждой новой улицы проверить, находится ли к ней достаточно близко каждая из ключевых точек старой карты, а затем проверить условие для старой улицы как побитовое И всех ее ключевых точек. Грубая оценка подстановкой максимальных значений — 108· константа · операции с вещественными числами, что ожидаемо не влезло в 1 секунду на Java 8.
Для этой задачи существует оптимальнее асимптотически решение? Или подобное можно было упихать на C++ (я не стал переписывать, хотя время было, так как оценка выше навевала уж слишком плохие мысли)?
D: дано N (1 ≤ N ≤ 300) точек на плоскости Di — водители такси. Также дано N маршрутов, заданных точкой отправления Pjstart и точкой прибытия Pjend. Расстояния в задаче считаются по манхэттенской метрике (|X1 - X2| + |Y1 - Y2|), длиной маршрута считалась сумма расстояний (Di, Pjstart) и (Pjstart, Pjend). Требовалось распределить водителей по маршрутам, чтобы минимизировать максимальную длину маршрута.
Я сдал бинарный поиск по ответу с проверкой совершенного паросочетания внутри. Является ли это стандартным решением для такого рода задач или существует какой-то способ оптимальнее?
Совсем не понял, почему в контесте они обозначены как A,D,E,F. Где B и С? только правила успокоили что будет 4 задачи...
Под A такая же. Под E было видимо B, где надо подсчитать сколько кто-то работал. Под F такая же, оно заходит за куб через венгерский алгоритм о назначениях? Под D была отличная от С и вызвала непонимание и негодование своей постановкой:
Задача про очереди на космопорте: очередь — это 3+ машины(машина -уникальная точка в 3-ех мерном пространстве) на одной прямой. Найти минимальную очередь, если такая существует. Это действительно хорошая идея давать ограничения по времени, но не давать ограничения на N — количество машин, не давать ограничения на пространство? + Из условий не понятно очередь это любая прямая в пространстве или прямая проходящая через космопорт куда они и садятся, если даже любая то, одна машина может принадлежать 2 очередям?
Насчет букв — задача D в моей нумерации в контесте была G.
Насчет венгерского алгоритма — он все-таки минимизирует сумму ребер, а не максимальное ребро, так что вряд ли он здесь подходит без дополнительных фишек.
Тест который не пройдет венгерский дан прямо в примерах, я не поленился проверил
Спасибо, я думал что там все же сумму, а не ребро, плохо вник в условие.
Я был удивлен задачами. Думаю, подготовкой занимались далекие от этого люди. Не везде были ограничения (просто отсутствовали!), условия так себе.
Расскажу про C. Я прочитал условие и так и не понял что там имеется ввиду. То, что ключевые точки соединены отрезками — не написано. Но жёстче другое: основное требование в задаче было написано как-то так "старая дорога соответствует новой, если все её точки находятся не дальше D от новой дороги". Здесь было совсем не очевидно — речь о ключевых точках старой дороги или вообще всех. Вопросы по условию задать было нельзя — они были отключены. Понимай как хочешь.
Я в результате написал наивное решение за квадрат, которое понимает основное требование как "все ключевые точки старой дороги должны находится не более чем на D от новой". Оно прошло все тесты. Все 6 тестов!
Очевидно, что с тестами в С вообще явные проблемы, так как при большом D потребуется вывести ~108 слов, что никакое авторское решение не успеет сделать за 1 секунду.
Про соединение ключевых точек отрезок не было написано в условии, но в 1 семпле одна из точек старой дороги находилась близко к отрезку новой, но не близко ни к одной из ключевых точек, откуда я и сделал вывод про отрезки.
Да, про возможный размер ответа порядка 108 у меня тоже были мысли. Я решил (посмотрев на условие этой задачи в целом), что тестами являлись близкие к реальным (?) карты (ведь все эти задачи встречались разработчикам Яндекс.Такси), поэтому каждая старая улица будет хорошо соответствовать только одной/двум новым.
Про близость ключевых точек или близость всех точек отрезков старой дороги я тоже нигде не нашел ответа, но судя по всему из-за "реалистичности" (?) данных не подразумевались тесты, где ключевые точки рядом, а какая-то часть отрезка между ними далеко от новой улицы.
Но в любом случае задача С была подготовлена сильно хуже, чем остальные. Больше всего мне непонятно, зачем так задирать ограничения, ведь какого-то явно читерского решения они не отсекали.
А кстати как вы узнали про ссылку на яндекс контест? И какая ссылка на Финальный раунд, и кто прошел на него? Мне ни одного письма не приходит
Мне пришло два письмо от отправителя Яндекс.События ([email protected]) — "Завтра первый тур", где содержалась ссылка на сайт соревнований, а затем письмо-напоминание "Осталось 3 дня до конца первого тура", где также была ссылка на систему тестирования.
Про то, что я прошел в финальный раунд, мне пришло еще одно письмо, уже от Яндекс.Такси ([email protected]). там же была ссылка — финальный раунд будет на том же самом сайте, что и отборочный этап. Какого-то списка прошедших на сайте я не нашел, но мне дополнительно звонили уточнить, видел ли я письмо про финал, так что пропустить эту информацию (письмо + звонок) довольно сложно.
Для тех, кому ссылка не пришла Финал Яндекс Такси будет проходит https://contest.yandex.ru/ytcf/contest/8527/enter/
Так и не понял, что надо делать в финале в задаче B, условие дико запутанное.
(неправда, они известны сразу же)
А как же выглядит полигон, в которых две стороны пересекаются? По условию это же исключено, ведь описывается многоугольник.
Как выглядит полигон — непонятно. Даны точки и всё. Он может быть выпуклым (в таком случае в условии пишут что-то вроде "точки отсортированы по часовой стрелке, многоугольник выпуклый"), а может не быть.
Вычисляется суммарное время нахождения в полигоне за всю историю или "как появился внутри — так и не покидал пределов, пока не проверили"? Логика подсказывает, что последнее, но это не факт.
Как "едет" машина — загадка. То ли треки показывают ломаную движения, то ли машина респавнится на этих треках магией и стоит неподвижно до таймера следующего трека.
Еще: "внутри полигона" и "на границе полигона" разные вещи, но это мелочи.
Другие задачи понравились, весь контест рассчитан на всякие отсечения, оптимизации по памяти.
Меня условие этой задачи тоже сильно сбило сначала с толку. Помог абзац, что "машина находится внутри — ее ближайшая слева от времени открытия портала точка находится внутри портала. Это подсказало, что машины магически перемещаются от точки к точке, а не едут равномерно. Хотя слова "дана траектория машины" выглядит в таком контексте странновато...
Насчёт того, какое время внутри считается — АС решение считало, что это последний непрерывный отрезок. Хотя по условию ничего не отсекало вариант "суммарное непрерывное время до" или "максимальное из всех непрерывных до".