19-го апреля в 18:35, начнется VK Cup 2018 - Wild-card Round 2.
Участникам раунда будет предложено за неделю максимально продвинуться в решении одной необычной задачи. Официально в этом раунде смогут принять участие команды чемпионата VK Cup 2018, которые прошли в Раунд 2, но не оказались среди тех топ-100 лучших по его результатам, кто проходит в Раунд 3. Кроме того, этот раунд будет открыт для всех желающих для неофициального участия вне чемпионата. Зарегистрироваться на раунд можно будет в любое время пока он идет.
Продолжительность раунда — одна неделя. После ее окончания мы выберем последнюю попытку, набравшую положительный балл, каждого из участников и проведем финальное тестирование.
Удачи!
How do I register for the contest? It displays "Registration is Private" message. Will the unofficial participation for public start after the official Wild-card Round 2 is completed? Please clarify.
Official and unofficial participants will be able to register before the contest starts. The registration will be open for 7 days. But for now relax and watch the ICPC World Finals!
Было бы неплохо отображать не только "Неправильный ответ", а и причину (как это уже было в некоторых марафонах). Так как сейчас очень сложно устранять баги, только наугад
Готово, пользуйтесь на здоровье!
Почему опять стало отображать только "Неправильный ответ", без подробностей?
Написал в личку запрос на подробности.
Так отображение причины неправильного ответа вернется?
Исправлено.
Is It Rated?
Ну что, какие у вас были подходы?
У нас было: на каждом шаге (каждый раз, когда приходит новый заказ + дополнительные точки, ~20 точек для каждого заказа) найти минимальное взвешенное паросочетание между начальными точками ещё не посаженных пассажиров и машинами со свободными местами (венгерка), затем для каждой машины найти порядок выполнения её заказов с максимальным количеством очков (полный перебор). Интересно, доводится ли это до полного решения (у меня 90% на 5 и 27 тестах).
затем для каждой машины найти порядок выполнения её заказов с максимальным количеством очков (полный перебор).Как вы это делали? За какую асимптотику?
Кажется, быстрее чем за факториал это не сделать (если не жадник), так что втупую генерировал все перестановки. Для каждой машины я брал не более 4 заказов одновременно в очередь (на каждом из 500*20 шагов), так что в TL заходило.
Если не ограничивать количеством человек в очереди до четырех, то можно взять больше баллов (была группа тестов, где пассажиры идут волнами, между которыми ~6к тиков). А перебирать, например, рандомом.
Во-первых, для каждого автомобиля поддерживаем список текущих его заказов и считаем score для каждого автомобиля -- количество очков, которое получим при выполнении всех имеющихся на текущий момент у него заказов.
Далее при поступлении каждого нового заказа пытаемся выкинуть 2-3 самых неоптимальных пассажиров из каких-нибудь автомобилей (смотрим, как изменяется score при их удалении) и пересаживаем их в другие автомобили. В принципе, тоже венгерка (ищем максимальное взвешенное паросочетание), хотя можно и тупее было. Так делаем раз 5-10.
Плюс было еще несколько оптимизаций вида "Давайте автомобили будут ездить не по границе прямоугольника, а по диагонали (кидаем фиктивные точки на диагональ)" и "Запустим несколько раз на рандоме и выберем наилучший результат"/
Решение, которое набирало 22293:
Берем очередного пассажира. Перебираем такси, куда его посадить. Для каждого такси за квадрат смотрим позицию для посадки и позицию для высадки среди текущих инструкций. Пересчитываем функцию (достаточно пересчитать только для текущего такси за линию). Сажаем в то место, где функция была наибольшей.
Не очень хорошо, если такси не двигаются после обработки заказов => разобьем плоскость на k прямоугольников, возьмем их центры, отправим такси венгеркой (ребро — точка конца исполнения заказов и центр прямоугольника). Но были тесты, где заказы распределены неравномерно. Их обработаем отдельно, учитывая частоту запросов в конкретный прямоугольник.
Точки, куда отправляем такси после исполнения всех заказов, пересчитываем на каждой итерации. Еще долгое время мы вставляли инструкции типа 0, чтобы машина ехала разнообразнее, но, как внезапно оказалось, это только ухудшает результат.
И это детерминированное решение.
Решение на 22300+:
В прошлом решении мы жадно сажали людей в такси. Но это не всегда хорошо. Давайте будем брать TO_RESET последних, еще не сидящих ни в каком такси, людей и попробуем добавить их в рандомном порядке тем же жадником. Шафлить будем REPEAT раз. Да, это работает жутко долго, поэтому добавляем отсечение по времени. После того, как превысили временную отметку, пользуемся прошлым алгоритмом (а он работал не дольше 1.5 секунд на всех тестах). Поперебирав константы, приходим к REPEAT = 20, TO_RESET = 9.
Ну и еще надо было пострадать с определением некоторых констант, вроде той, что отвечает за отправку такси по точкам после исполнения заказов для <<плохих>> тестов.
Для каждого нового пассажира мы перебирали номер машины, а так же позицию посадки и высадки среди инструкций этой машины, сравнивая выгодность жадно (по сумме значений функции для каждого пассажира). Еще была генерация k * k рандомных точек, при выводе инструкций, каждой машины в конец её очереди пробовали добавлять просто движение в ближайшую точку из сгенерированных (расстоянием являлось расстояние между точкой и конечной точкой после выполнения всех инструкций в машине, которое умножалось на какой-то коэффициент), при этом умножая коэффициент этой точки на некоторую константу, чтобы не брать одну точку много раз.
When will the system tests start?
I'm working to start it. I expect to run system tests in ~2 hours.
Отжиг не очень зашел(((((
А у нас решение набирало 22237 баллов, но оно не учитывало, что машину в свободные моменты времени можно посылать куда угодно. Решили сделать 6 циклов немного сжатой синусоиды вдоль всего поля, так что машины равномерно распределены по этой синусоиде. Решение стало набирать 22282 балла, что кинуло нас где-то на 10 мест вперёд и тогда мы встали на четвёртое место. Жаль только в последние пару часов заметно опустились и встали на 7 место.
Довольно удивлен что наше идейно простое решение смогло набрать такое кол-во баллов(85809). Сам алгоритм: для каждого заказа полностью перебираем все машины и все позиции посадки и высадки нового пассажира, для каждого варианта за линию пересчитываем значение функции стоимости, выбираем вариант с максимальным значением, назначаем туда пассажира. И если после заказа остались пустые машины, распределяем их равномерно по полосам на поле, выдавая каждой случайный столбец.
TL;DR Как получить 22349 (86088):
(это в самом деле кусок кода из финальной посылки, LuL)
А если серьезно, основная идея решения у нас примерно такая же как и у большинства (видимо). Научимся добавлять выполнение заказа к уже сформированной последовательности команд за O(C3), чтобы оно максимально увеличивало количество очков. Новый заказ назначаем такси, которое может дать максимальный профит. Далее делаем что-то вроде локальных оптимизаций: возьмем два заказа, назначеных различным такси, и попробуем поменять их местами (естественно, оптимальным способом). Сделаем эту операцию много раз. К этому всему добавим побочные оптимизации типа движения лесенкой, а не уголком (интуитивно понятно, что таким образом матожидание расстояния до всех точек должно стать меньше), и отправку пустого такси в (почти) случайные точки, чтобы их распределение по всей карте было более равномерным.
Будет возможность дорешивания?
Hey MikeMirzayanov is it possible to judge my better solution (i know changing the rank list is too much for a request but at least we deserve to know our actual score!) for this round because i didn't know that the last positive score solution will be judged,Kind of my mistake that i did not read the blog properly :( but i feel very sad because my score was zero as a wrong solution was considered in which i got some positive points, but i had a better solution which i submitted earlier! please consider this request as i would like to know my actual score at least!