Сегодня, 26-го апреля в 18:35, начнется VK Cup 2017 - Уайлд-кард раунд 2.
Участникам раунда будет предложено за неделю максимально продвинуться в решении одной необычной задачи. Официально в этом раунде смогут принять участие команды чемпионата VK Cup 2017, которые прошли в Раунд 2, но не оказались среди тех топ-100 лучших по его результатам, кто проходит в Раунд 3. Кроме того, этот раунд будет открыт для всех желающих для неофициального участия вне чемпионата. Зарегистрироваться на раунд можно будет в любое время пока он идет.
Продолжительность раунда — одна неделя. После ее окончания мы выберем последнюю попытку, набравшую положительный балл, каждого из участников и проведем финальное тестирование.
Удачи!
UPD 1: Соревнование завершено. Лучшие 20 команд получают путевку в VK Cup 2017 Раунд 3! Спасибо за участие.
Но сегодня только 25-е апреля!
Unusual rules like VK wild round 1？Interesting! Hope surprised rules and problems.
How many participant advance to Round 3?
20
Надеюсь, что хотя бы в этот раз задача/ограничения будут подобраны не как в прошлый раз, когда простейшие решение на Java падало по TL 17582651.
If I registered for this round .. can I also compete in Educational Codeforces Round 20 ?
Yes, they are completely independent.
I can only participate out of contest as a single person, why can't i register unofficialy with a team?
It will be enabled in 10-20 minutes.
Would the people not actually in VK Cup be rated for this?
Why can't I register it as a team?
Is this round rated?
No
Thanks.
Раньше была возможность использовать java 8 zip, сейчас этого нет — есть вариант, что появится?
А есть ли ограничения на количество посылок?
Жалко, что нельзя отменять свои посылки: например сейчас висит мое багнутое решение, которое не дает ответ за 10 секунд и зря расходует ресурсы кф((
http://codeforces.me/blog/entry/44548?locale=ru#comment-290814
Согласен! Тут под ^ этим комментом кто-то написал, что это проблема решается локальным пакетом тестирования — минималист :D Для удобства уж лучше добавить, я вот дофига решений отправил локально непроверенных
Тупо. Жадно. Переборно.
Мы набрали ~10075 баллов с какой-то дичью.
Сортируем профессоров по убыванию общего кол-ва уроков, которое они должны провести и аналогично сортируем группы.
Теперь пытаемся пройтись по всем профессорам и для каждого профессора перебираем 42 * 42 (магические константы :D) перестановки дней * перестановки уроков.
Теперь в таком порядке проходимся по группам и пытаемся назначить все уроки текущей группе.
Назначение делаем жадное — проходимся по урокам и дням (именно в порядке перестановки, которая определена выше), пытаемся ставить урок на (lesson, day) если там достаточно аудиторий, из всех таких выбираем (lesson, day) где наименьшее изменение усталости происходит.
Теперь ту же фигню мутим, но изменяем порядок — теперь проходимся по группам и назначаем профессоров.
Вроде с горем-пополам нашли какое-то норм решение. Но не тут то было!
Теперь его ещё подоптимайзим — для какой-то группы будем свапать уроки её профессоров пытаясь минимизировать усталость.
А потом ещё для каждого профессора попробуем просвапать уроки для его групп.
В конце выводим это чудо-наоптишмайзенное решение.
У кого какие решения?
Мы находили начальное расписание венгерским алгоритмом.
Не помню сколько он набирал сам по себе, но после жадной оптимизации вышло набрать немного больше.
С нежадной оптимизацией как-то не сложилось.
Как показала практика, от изначальной расстановки ничего не зависит. Изначально можно расставить любым доступным способом. Далее необходимо свапать много-много раз пары с парами и пары с пустыми клетками, так же отдельный эффект придаст то, что надо выбирать для свапа пары, которые являются первыми или последними за день у группы или препода. Возможно, если выбрать для свапа по три пары — можно добиться еще меньшей усталости, т.к. будут за один раз свапаться те тройки, которые, возможно, не будут давать эффекта, если свапать их последовательно, как и ранее.
С тремя парами свапов пробовали — хуже, чем только с двумя. Возможно криво пробовали, возможно оно дает незначительный прирост по сравнению с двумя, сжирая очень много времени при этом(что ухудшает общую производительность).
Так же была идея следующая: когда свапами зашли в тупик (ни один свап не улучшает), то можно запомнить ответ, некоторое количество пар (рандомных) отменить и распределить пары рандомно по новой, после чего опять свапать. Но если честно поленились реализовать:)
Берет что-то около 10075. Сплошной нахаченный рандом.
Написал отдельно два решения: одно лучше оптимизирует группы, другое — преподов, выполнял оба по 5 секунд.
Решение делилось на две части: сначала сгенерим произвольное (более-менее неплохое) расписание, потом в течение 500 мс будем брать произвольную пару (в последнем решении пара не произвольная, а какая-то из рандомного дня рандомной группы, что находится близко к началу дня, не обязательно самая близкая), вынимать ее и ставить в наиболее оптимальное место.
Генерю в начале так: раскидаем равномерным распределением пары конкретной группы (препода в противоположном решении) по всем доступным дням и подобавляем в произвольном порядке в расписание, так сделаем для всех групп (преподов) опять же в произвольном порядке.
Добавляю следующим образом: сортирую дни по длине занятых в них отрезков по возрастанию, выписываю все свободные клетки, ставя им ту цену, что добавляется при постановке, сортирую их и пытаюсь взять наиболее дешевые. При равенстве смотрю по цене дней соответственно. Пытаюсь обновить ответ после каждой итерации удаления-добавления пары (проверяя, что все пары поставились).
Вроде довольно неплохо в среднем кидает. Генерация начального расписания оказалась не так важна, свапы неожиданно очень хорошо релаксируют ответ.
Берет 10117.016 Решение состоит из двух частей.
Первая часть: рандомно выбираю пары групп и учителей и ставлю все их уроки на расписание. Ставлю таким образом, чтобы они максимально лежали ближе к началу дня и максимально возможно распределены по дням равномерно. Работает: 0.4 сек
Вторая часть: берем два рандомных урока и пытаемся поменять местами. Если улучшили ответ, то меняем местами и сохраняем в таблице расписаний. Работает: 9.5 сек
Храним глобальный лучший ответ и обновляем каждый раз если нашлось лучшее решение.
Быстро и легко пишется! Вообще не ожидал, что такое решение так хорошо улучшает. Получается все кто с 10117... отличаются только нахаченностью решения :D
Вот-вот! Я не могу поверить, что у меня написано вот ровно то же, просто чутка недохачено! :D Ожидал, что какие-то серьезные идеи у людей в топе.
Когда ждать финальное тестирование?
Не терпится узнать, когда будет финальное тестирование?
Как-то было анонсировано, что не будет систестов(Соревнование сейчас перешло в "закончено + дорешивание")? Каждый год были систесты, отличающиеся от претестов, и перестановка участников зачастую резко менялась, из-за того, что многие участники переобучали свои решения под конкретные тесты.
Я сейчас посмотрел анонсы предыдущих лет и этого, и везде одна и та же фраза "Продолжительность раунда — одна неделя. После ее окончания мы выберем последнюю попытку, набравшую положительный балл, каждого из участников и проведем финальное тестирование.", намекающая на то, что будут финальное тестирование на основе новых тестов.
Кто-то может пояснить где я упустил изменение по сравнению с предыдущими годами?
Терпение :)
Возьмите первые 30 команд, пожалуйста! :D Крик души
Кстати, а что за авторское решение?
Набирает ровно 10к)
10117.158:
Построим какое-то начальное расписание. Далее будем какое-то количество раз убрать все пары какого-то лектора/группы с вероятностью 50% и после чего возвращать их жадно в случайном порядке.
Разве не правда, что описанная задача является задачей целочисленного квадратичного программирования, и для таких небольших ограничений успешно решается за разумное время (почти) любым предназначенным для этого пакетом?
А что за "задачей целочисленного квадратичного программирования"?
Это как задача целочисленного линейного программирования, только в целевой функции всё немного поквадратнее.
TLDR: ЦЛП — это если есть линейные ограничения и линейная целевая функция, которую нужно (макси-)минимизировать. Квадратичное — это если в целевой функции допускаются квадраты.
При наивном подходе будет много (порядка 10**5) переменных. Это по всей видимости не будет работать за вменяемое время(афаик большинство солверов используют одной из стадий симплекс), хотя я могу ошибаться.
Есть идеи как обойтись малым числом переменных?
Да, симплекс в любом случае используется, но во-первых, после ряда оптимизаций (которые, в том числе, могут понизить как число переменных, так и ограничений), и во-вторых, с регулярными проверками решения на оптимальность по различным критериям.
Тем более, нам (участникам) не так уж и приницпиально найти именно оптимальное решение, было бы достаточно "погонять" солвер 10 секунд и остановиться на достигнутом :)
When can we view contestant solutions?
Переместились с 1 места на 24 :( Финальные тесты очень порадовали!
Кол-во человек набравших больше 32 тысяч ровно 32(42), и тем более это степень двойки (1 << 5) по-моему идеально кол-во человек чтобы взять:)
Их же 42, разве нет? А с неофициальными — 51.
32 Россия Poohlyash_ТаТаРиН Team: dani_bw, TaTaPiH 32203.507 33 Украина МАМОЧКА НА САНОЧКАХ: pisos_pro, Mem4ik 32196.96
32196.96 > 32000, верно?
сейчас я понял что ничего не понял, бывает, как я вообще мог это написать)) извини