Всем привет!
Добро пожаловать на VK Cup 2012 Уайлд-кард раунд 2!
Вас ждет 7-дневное соревнование по решению всего одной задачи. Мы полагаем, что задача не имеет точного эффективного решения. Чем более оптимальные решения будут находить ваши алгоритмы, тем больше баллов вы получите. Конечно, это не все подробности. Полный текст условия и правил оценки вы сможете прочитать сразу после начала соревнования.
В основном конкурсе этого раунда участвуют те, кто официально прошел в VK Cup 2012 Раунд 2, но не прошел в VK Cup 2012 Раунд 3. По результатам VK Cup 2012 Уайлд-кард раунд 2 лучшие 25 участников завоюют право участия в VK Cup 2012 Раунд 3. Все остальные члены сообщества могут принять участие вне-конкурса, just for fun.
Во время соревнования вы можете сделать произвольное количество попыток решения, но на системных тестах будет тестироваться ваша последняя попытка, которая прошла хотя бы один тест.
Удачи! Пусть победит сильнейший!
P.S. Я не могу не оставить это здесь. Во время соревнования категорически запрещается публиковать/обсуждать алгоритмы решения задачи, подходы к решению, делиться какими-либо выводами о задаче. Нельзя делиться результатами (в том числе просто сообщать баллы) запуска своих решений на каких-либо тестах. Запрещено публиковать инструменты для упрощения или автоматизации процесса решения задачи.
И да, огромное спасибо Nickolas за великолепную задачу!
UPD: Контест закончен, тестирование завершено. Поздравляем первые 25 мест — результаты, вы вышли в VK Cup 2012 Раунд 3!
Повторюсь — можно ли в предстоящих соревнованиях указать сколько будет длиться этот раунд?
Укажем
Ого! Не будет вообще никакой информации о текущих результатах других участников?
Будет, но делиться чем-либо сверх — нельзя.
i really like this rules, although i'm an unofficially participant. i think it's like Marathon in top-coder a little bit, and it means that the problem is more real. i hope this kind of contest can be hold in the future regular.
look forward for it & good luck for everybody! have fun!
Sorry for a bit off topic. Mike, is the site having some trouble in recent hours? I’m not able to view solutions on the standing pages.
Спасибо, будет очень интересно поучаствовать в таком необычном соревновании!
Вопрос: будет ли раунд рейтинговым для конкурсных участников (прошедших в Round 2)?
Раунд нерейтинговый для всех, это было объявлено давно и много где.
Спасибо, видимо я это пропустил.
у кого-нибудь есть такая проблема: запускаю check.exe или gen.exe — системная ошибка: отстутствует libgcc_s_dw2-1.dll?
я скачал, но потом требует другую libstdc++-d.dll))
можете ссылку дать где скачали?
P.S. не надо, можно скомпилировать исходник gen и check, они там есть и ничего не скачивать
Скомпилируй файл gen.cpp (аналогично для check.cpp) из папки src любым C++ компилятором и запусти его.
да спасибо, я уж понял
Перекачайте архив
а где можно скачать? невижу
6-й абзац условия же.
может стоит сделать, чтобы run-gen и run-checker не закрывался сразу после запуска?
Он вроде не закрывается. Ты используешь батник или шелл-скрипт?
батник
да это не проблема, ну просто для порядка, поставить какой нибудь
_getche();вконце, чтобы не закрывался как бы его не запускалиКак-то неприлично так в программах делать. Допиши в батник строчку pause.
а почему неприлично?
так же неприлично, как и метки использовать?
Из чуть более логичных соображений — программа может запускаться не только руками, но и в автоматическом режиме. В случае наличия лишнего интерактива (как, например, "Нажмите любую клавишу") это становится сильно труднее, что неправильно — легче дописать строчку в bat'ник, чем просить у автора исходник программы и пересобирать.
По этим же причинам ввод/вывод на олимпиадах, казалось бы, происходит в достаточно чётком формате, без приглашений, комментариев и GUI.
Ты видимо запускаешь батник из папки в обозревателе Windows, поэтому у тебя и закрываетя. Варианта 2: либо запускай из cmd.exe или farа, либо сделай так как написал ниже Hohol
да я пробовал с cmd, тоже какой-то путь не находит
да вообще забей, я уже давно все настроил как надо мне, просто думал выяснить все таки, почему закрывается окошко
Мой первый дабл-коммент.
С почином.
@JOKE@ Забыли добавить уже традиционную запись "Пожалуйста, чтобы раунд для вас был еще интереснее, прочитайте условия ВСЕХ задач." ^_^ @JOKE@
И в комментах должны спросить про взломы и динамическую стоимость.
А какой максимальный балл можно получить по задаче? (пока)
Вот вам и бонусное задание — придумайте размещение, которое подходит под заданные ограничения и набирает максимум баллов. То, что в нас не произвольные прямоугольники — это уже детали.
Число баллов не ограничено явно, но оно зависит от решения, поэтому его ограничивает только теоретически оптимальное решение.
З.Ы. А ответ по поводу того, какое максимальное теоретически возможное число баллов можно набрать на претестах, даже если эта инфа есть у авторов/админов/коготоещедругого — думаю, является обсуждением задач, что правилами запрещено.
Вот, кстати, интересно, если кто-то наберет максимум возможных баллов на претестах, у него статус изменится на "претесты пройдены"? :)
хватит вам уже задачу обсуждать
Если бы я принимал реальное участие в соревновании (т.е. выкладывался на полную и соревновался за место в топ-25), то мне бы сильно помогла кнопка, аналогичная топкодеровской history of submissions.
Чтоб можно было по основным конкурентам посмотреть, какой у них прогресс за последнее время, есть ли у них "в рукаве" сабмиты с более высокими баллами (которые они специально или не специально затерли свежими) и т.д.
Понимаю, что это можно делать вручную... Например, по профилях лазить. Но получается неразбериха в том случае, если участник еще где-то соревнуется/решает архив. Да и по времени это дольше.
Дело хорошее, что-нибудь такое поимплементим.
Или я туплю, или в визуализаторе бага.
Инпут:
Аутпут:
Прямоугольники не касаются, но визуализатор рисует между ними красную линию, будто соприкасаются. При этом очки за эту красную линию не отнимает.
Fixed. Новая версия архива 1.0.2
Ффу, теперь можно и поспать.
Извините, я не совсем понимаю, почему во вкладке стутус у кого-то написны баллы, а у кого то "х претестов из 10"? Как можно пройти претесты, тут ведь в том то и соревнование кто больше баллов наберет. Или на каждом претесте нужно набрать какое-то минимальное число баллов?
Претест можно пофейлить — то есть получить на нем WA, PE, TL, RE.
Предполагаю, что выходные данные в некоторых претестах просто неверные. прямоугольник на другой заехал, или еще что.
Тестирование повисло.
Развисло.
Hello,
Are we allowed to include the checker's code in our submissions?
Yes you can use code of checker and generator.
Nickolas в своем репертуаре...
Собственно, это (марафоны) и есть мой основной репертуар, ULR — это так, баловство :-)
Визуализатор не проверяет выход прямоугольников за границы области, хотя чекер проверяет.
А входные ширина и высота прямоугольника только целочисленные? И после масштабирования должна ли сохраняться целочисленность? Вроде в первый раз читал, это было в условии, а сейчас не нашел. Или я сонный такой уже %)
Я делаю довольно много отладочной печати в поток cerr, но не знаю, разрешено ли это вообще. Не получу ли я внезапно какой-нибудь Security Violation на систестах, если много писать туда буду?
Если не получишь ТЛ все будет нормально. Но лучше обернуть весь дебаг вывод в ifdefы.
Вопрос немного не по теме, но почему перестали показываться коды решений в прошлых контестах при двойном нажатии на них? Или это только у меня так? И если нет, связано ли это с VK Cup 2012 Уайлд-кард раунд 2?
Только я не могу посмотреть код участников в любом раунде?
Кстати, теоретически возможно такое, что у нескольких участников в итоге будет одинаковое число баллов. Если 25ое место будет поделено, по какому признаку будут выбирать тех, кто прошел? По более раннему последнему сабмиту? Или дальше пройдут все?
О, спасибо что показали. Уже и забыл о тех правилах, искал только в локальных.
Цитата из анонса Vk Cupa : "В случае, если несколько участников имеют одинаковый балл в отборочном этапе и попадают на границу отбора, то все они выходят в следующий раунд."
It looks like that the grader stopped working.
Раунд окончен, ждем тестирования.
Кто как решал?
Жадник.
Ставим первый прямоугольник в угол. На каждом шаге перебираем, какой прямоугольник поставить следующим, какой стороной, как его растянуть и куда поставить. Ставим так, чтобы угол нового прямоугольника совпадал с одним из старых углов, то есть при фиксированной ориентации и размере есть 8*n возможных расположений. Каждый раз жадно выбираем следующий ход. Еще стоит запустить жадник несколько раз. У меня не было времени особо все оптимизировать, поэтому я успеваю сделать немного — на ста прямоугольниках всего раз пять-шесть.
После этого выбираем лучший ответ и пытаемся его улучшать. Я это делал локальными оптимизациями: возьмем один прямоугольник и попробуем его чуть-чуть куда-нибудь подвинуть. Если ответ улучшился, двигаем.
Само собой, на это навешана куча всяких эвристик вроде сортировок по параметру MAGIC, запрета на сужение/расширение в определенном интервале, чтобы один прямоугольник не занял все свободное место, и тому подобное. Написано все практически за одну ночь и один день — я слишком поздно понял, что раунд скоро кончается :) Результат — 5171 на претестах.
Я тоже писал похожую жадность, только без фичи с углами. Плюс в конце, после расстановки всех прямоугольников, увеличивал те, увеличение (без перемещения) которых ничего не портит. Ну и тоже всякие мутные эвристики. Из-за того, что вариантов расстановки очень много, пришлось ставить отсечение по времени. Результат на претестах — 4257.
Да, увеличение в конце я тоже делал. Но мне оно мало что дало почему-то. Наибольший подъем баллов был после того, как я добавил локальные оптимизации — видимо, касания, от которых можно избавиться сдвигом на миллиметр, очень уж портили общую картину. Ну а отсечение по времени — само собой :) Для каждой части решения было строго описано, сколько ей можно работать.
После добавки оптимиза с увеличением в конце мой балл на претестах увеличился на 3 :) Но я все равно оставил, хуже точно не будет. У меня лучшие подъемы были после подгонов с сортировкой и с масштабированием. Я не придумал как можно вменяемо масштабировать (перебор позиции + коэффициента работает уж очень медленно), поэтому пришлось подгонять отдельно; видимо, это главный провал моего решения.
Тоже самое.
Были ещё отсечения такого вида — для каждой точки можно хранить информацию какой угол в ней заканчивается, тогда соответственно в эту сторону растягивать не имеет смысла.
Ещё при масштабировании для минимального масштаба брал так, чтобы его периметр был больше чем найденный мной результат не текущем шаге, т.е. что он потенциально может его улучшить.
При равенстве очков, выбирал с наименьшим периметром, а среди таких наибольшую по |x|+|y|, т.е. как бы сдвигал все в одну сторону, а в конце пробывал когда сдвигам при равенстве очков выбирал с минимальным |x|+|y| — это хорошо когда у нас последовательно стоят блоки, тогда он их сможет растащить.
Также пробывал двигать не только на чуть чуть, а до упора в какую либо сторону и чуть чуть не до упора. Количество итераций на больших тоже очень маленькое... 4-5.
Результат 5314. Максимальный был 5380, но это с rand(0), а так привязал rand к входному тесту.
Тоже жадный алгоритм.
Сортируем по "вытянутости", тоесть по величине w/h. Берем первый прямоугольник, вытянутый в одну сторону, ставим (увеличивая по максимуму: не более чем в два раза и чтобы хватило места), берём второй вытянутый в другую сторону — ставим, но ставим переворачивая. Соприкосновение получаеться по стороне что подлиннее. Так расставляем всё, что можем. Получаем как бы стопку из прямоугольников.
Потом дописал разбиение всего доступного пространства на 4 части (ширина, само собой перебираеться и береться разбиение получше) и заполнял части последовательно тоже жадно: первая, вторая и т.д.
Потом еще брал один сильно вытянутый прямоугольник и ставил его поперек между третьей и четвертой частями. При этом прямоугольники состыковываем с этим вертикальным (но только те, что дадут + к баллу). Он много место жрал, но зато +60 балов на претестах я получил :).
Вот иллюстрация второго претеста (тут разбиение на 3 части и прямоугольник между вторым и третьим "столбиком"): картинка
Решение на претестах получает 4990.8 баллов
Я написал перебор, который хранит линию границы уже поставленной области. Каждый раз беру левую нижнюю точку и ставлю туда самый выгодный прямоугольник. Либо не ставлю ничего и сдвигаю эту точку. Для выбора прямоугольника используются всякие шаманства, а также перебор отсекается по времени. Чтобы лучше работало, я перебираю внешним циклом магическую константу и затем уже для нее запускаю перебор на 0.05 секунд либо 1000 итераций (что раньше наступит). В самом конце жадно улучшаю ответ. Набирает 5602 на претестах.
Можешь выложить свой код? Непонятно, когда посылки смотреть можно будет, а очень хочется увидеть, что у одного из лидеров генерится.
Вот ссылка. Я не сильно заморачивался и не удалял из кода лишние функции и переменные. Там много всего лишнего, но если не пытаться разобраться, то использовать можно :)
Красивейшие результаты.
Вот например очень радует
У меня рассматривалось несколько вариантов решения, плюс почти каждый из них зависел от какой-то величины (положение базовой линии, ориентация линии, номер начального прямоугольника). Набиралось порядка нескольких тысяч решений (макс. ширина/высота x 10), они сортировались по количеству баллов и начиная с самых лучших улучшались до тех пор, пока не кончится время. Улучшение заключалось в попытках прилепить неиспользованные прямоугольники к каким-то из использованных, работало очень медленно — поэтому фактически успевали улучшиться только несколько вариантов.
Одним из самых эффективных подходов оказался такой: фиксируем линию (горизонтальную или вертикальную), перпендикулярно ей начинаем класть слои чередующейся ориентации (плюс еще разной ориентации по разные стороны от прямой). Каждый слой — прямоугольники, масштабированные под ширину слоя, с интервалом в 1 точку. Ширину слоя перебираем, выбирая максимально заполненный прямоугольниками. В результате в плюс идет (в идеальном случае) примерно количество слоев, помноженное на ширину поля, плюс высота поля.
Ну, на картинке понятнее, думаю (уже после оптимизации, финальный вариант на втором тесте):
Симпатично.
Я клал прямоугольники слоями, стараясь делать так, чтобы верхние прямоугольники образовывали лесенку с чередованием цветов. А затем запускал оптимизу, которая заполняла пустые места маленькими прямоугольниками. Мой код.
How much time is the testing on the final tests expected to take? :)
It seems like they won't start ((
Will the sources be open after the contest?Or is there going to be any tutorial or summary? I'm just wondering how they(especially who with a high score) got that high score...
А можно узнать хотя бы приблизительные сроки оглашения результатов?
Предположительно, тестирование начнется сегодня ночью.
И пройдет до выходных))...
в чем дело, почему до сих пор нет системного тестирования? во вкладке "статус" можно поставить фильтр "вердикт: выполняется" и удивиться: там "выполняется" тест двухдневной давности!
The system test has ended!!! It took so long a time...
How about publishing the submissions, now the contest is over?
You may use "submission" tan in profiles now to see solutions
Will it be possible to submit in practice mode later on?
I think the link of stndings in UPD is wrong.
как у yefllower может быть отрицательное кол-во баллов??
Цитата из условия: