Здравствуйте, друзья.
В ближайшее воскресенье (16 июня) в 14-00 по Москве состоится отборочный раунд, который позволит 50 людям из 600 пройти на онсайт раунд, который пройдёт в сентябре.
Хочется обратить внимание, этот раунд будет длиться уже на один час больше, то есть ровно 3.
Всем удачи!
До свидания!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 146 |
| 3 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Только у меня решения перестали тестироваться в конце контеста? Решение, отправленное за 9 минут до конца, еще не протестировалось (контест закончился).
UPD: теперь его даже нет в очереди.
К сожалению, произошла нештатная ситуация. При компиляции вашего решения создается невалидное win32-приложение. Видимо правильно считать, что у вас CE, хотя можно и ML на ваш выбор.
а почему же ему сразу об этом не сказали?
Ситуация, когда скомпилированная программа не является корректным win32-приложением нестандартная. Система выдала ошибку. Пока мы разбирались, собственно раунд закончился. Участник задал вопрос через связь с жюри, мы также ответили.
Я сожалею, что так получилось, мы подумаем что с этим сделать.
Я не хотел обидеть уважаемого al13n, извините, если мой комментарий выглядел резко.
Что за 7-ой тест в задаче Е(геометрия)? Я один на нём валился?)
У меня падало на 7, когда у меня ответ не мог быть меньше 90 градусов (когда ответ больше 90 градусов, все правильно, а когда меншье — я вывожу 90).
У меня падало из-за точности, когда писал бинпоиск по ответу.
Мне кажется, или то, что D решается копипастом с e-maxx не делает чести авторам контеста. Тем более в свете последних событий.
Забанить всех, у кого копипаста!
В отличии от CF так не получится на RCC сделать:
Хотя конечно может быть возможна трактоквка, что копипаста -- это нечестное выполнение заданий. :)
Если несколько человек скопирают один и тот же код с e-maxx, то это может считаться списыванием, а оно запрещено на RCC.
Мне сегодня пришло письмо о регистрации на RCC 2014 и все-таки хотелось бы прояснить вопрос, разрешено использование чужого кода или нет? То есть легально ли копипастить с e-maxx?
А какой копипаст? Я немного переделал идею с кодами Грея, а потом ещё и 2 указателя впихнул.
http://e-maxx.ru/algo/generating_combinations добавить цикл и изменить формат вывода.
Oh... Неприятно. С другой стороны "не свой" код вроде как разрешено использовать, но давать такую задачу — некруто.
У меня например зашел тупой перебор в котором некоторые циклы поменяны местами)
А что за копипаст? Там ведь явная конструкция несложная.
Я отсортировал коды Грея по количествам бит через stable_sort
Задача А решается и без графа (как в разборе). Можно показать, что нужно использовать максимум 2 перехода, и если нужно, то они рядом с героями (сверху или снизу).
Ну да, а необходимые переходы найдем бинпоиском.
В случае если герои в разных башнях, нужен только один переход, и его вообще можно перебрать линейно.
Нестандартная локаль по умолчанию в Java — это была очень злая шутка... Заниматься debug-сабмитами значительную часть контеста было не очень приятно. Как вообще такое смогло получиться? Ведь у авторов есть решения на Java? Или авторы все как один не задумываясь писали Locale.setDefault(Locale.US), и их ничего при этом не смущало?
Я обычно передаю
Locale.USпрямо вprintf, этот способ не вызывает проблем сSecurityManagerами. Хотя в этот раз всё без проблем работало с обычнымprintln.Я обычно ничего никуда не передаю, т.к. везде по умолчанию стоит нормальная локаль. Но не здесь :( Если честно, с тех пор, как я стал писать контесты на джаве (почти 2 года уже), ни разу с этим не сталкивался. В любом случае, этого в правилах написано не было, так что шутка злая :)
У меня все работает без проставления локали. Хотя, возможно, это связано с моим хитрым выводом, который просто берет toString. Надо будет тогда в парсилку force locale проставить
В задаче E были у кого-нибудь постоянные TL 7,8? Я делал как в разборе. Может быть, не стоило для вычисления углов использовать atan2?
У меня были. Это все происходило в последние 5 минут контеста. Я сначала в панике дописал предподсчет всех длин векторов. Это с 7ого прыгнуло на 8ой. После этого я дописал предподсчет вообще всех углов между всеми парами смежных векторов. И это прошло.
Можно вычислить atan2 для всех пар точек (150^2), а углы между векторами считать как разности
Действительно. Спасибо. Не додумался до этого на последних минутах. Я зачем-то вызывал atan2 n^3 раз. Такая оптимизация более чем в три раза ускоряет у меня локально, с 1.7 до 0.5 секунд.
P.S. На Codeforces зашло за 1.437
Я углы заранее считал при построении ребер для графа с atan2 — зашло. А вот при использование acos — валилось по точности похоже :( из-за +9...
Я сдал с плюса с acos, кажется 1e-12 или 1e-13 eps в visual studio со 130 итерациями (пред подсчёт n^3 углов).
Я без бинарного поиска делал. Видимо проблема с точностью в комбинации дейкстра + acos.
А у меня всё нормально было в такой же комбинации.
вычислял углы и скалярным произведением и т.косинусов. тл7. кривые руки.
Если для каждой тройки точек в самом начале вызвать atan2, то с TL проблем быть не должно, у меня сразу зашло (+4 не по этой причине).
воу, авторы, что это за баянистая Е, казалось бы, классика бинпоиска по ответу + геом, разве нет?
Что, только я один решал E дейкстрой, без бин. поиска по ответу?
Не один.
А я один решал F за куб?
Я тоже за куб. Хотя для больших чисел всё равно получается ответ, меньший, чем n / 2 + 1, что неправильно.
Динамика за пятую степень делает прекалк примерно до 120, а потом 9-ый знак обнуляется и ответ — (n + 2) / 2.
А как за куб? Я честно за пятую, с отсечением, что подряд больше 50 не бывает. Мы тут только четвертую умеем пока.
А как за куб решать?
Динамика такая: будем считать количество последовательностей из нулей и единиц длины i, среди которых j единиц и подряд идут не больше k единиц. Такую динамику легко пересчитывать за O(n): будем перебирать, на сколько единиц заканчивается очередная последовательность. Теперь заметим, что при переходе мы считаем скользящую сумму на отрезке, и оптимизируем переход до O(1). Как из этой динамики посчитать ответ, придумайте сами (подсказка: каждое значение динамики входит с некоторым коэффициентом в ответ для n = i + 1).
Не один
Нет, я еще так делал...
ну суть в том, что задача с подобной идеей была в лкш, что-то там про кочки и прыжки, которая тоже решалась либо бинпоиском, либо дейкстрой.
Я написал поиск в ширину (точнее, модифицированый алгоритм Левита или как он там называется правильно). В худшем случае 4 степень, но здесь быстро отработало.
У меня бинпоиск не зашел. Так что тоже дейкстру.
А как это решать дейкстрой?
Сделать веса у ребер равные углам. А потом дейкстру по функции max(prev_weight, edge_weight), вместо prev_weight + edge_weight.
А, понятно, я что-то и не догадался, что максимум нормально работает здесь.
Я подумал о дейкстре, но решил, что бинпоиск будет проще написать.
В тренировках — 2013 Russian Code Cup, отборочный раунд
Не судите меня строго, но если понимать формат выходных данных в задаче F буквально, то правильным можно считать любой вещественный ответ на тест.
Из каких соображений?
Ответ считается правильным, если он отличается от правильного не более чем на 10^-9. Правильным является ответ, соответствующий условию. Далее, по индукции, любой вещественный ответ правильный.
Я бы поставил за сегодняшний раунд 3+:
— D, оказывается, стырена с e-maxx'а, что очень неприятно людям, которые решали ее сами (например, мне)
— A — очередная безыдейная как...шка, наподобие задачи B первого отборочного раунда — думать не надо, пишется долго и печально, и в конце не сдается =( Я не понимаю, что за талант придумывать такие задачи
— Е как-то долго упихивалась в таймлимит, причем, судя по результатам, не только у меня
Странно, что С нет в этом списке, так как решается простым перебором+мемоизация.
Ну, у меня ж претензии ведь не к уровню сложности. C — задача как задача, простая, но не в этом проблема контеста.
Несложно доказать, что это работает за log^2 на то, что вылезло из мемоизации.
Контест на самом деле очень похож на прошлогодний, дали кучу халяв, если не тупишь ни на одной из них — ты в финале.
Про задачу А совсем не согласен. Задача занимает свое место "халявной" задачи в контесте — в том числе и для "разгона" перед более сложными. Задача, конечно, совсем простая, но пишется не в две строки и есть несколько способов ее решения (например, без графа — аккуратным разбором небольшого числа случаев).
Что важно для простой задачи — она вроде не боян (по крайней мере для меня).
Ну да, в этом и проблема: унылая, идеи — ноль, надо писать, потом еще и не сдается. Это я и назвал "очередная безыдейная как...шка". Не боян? Но тут боянить нечего — идеи в ней нет совсем никакой.
Идея для сильных участников в том, как это написать, чтобы сдалось и чтобы при этом потратить меньше времени.
Для более начинающих участников — надо сначала еще придумать правильное решение (не ТЛ).
По-моему, там и писать нечего.
Но придется согласиться —
потом еще и не сдается:)Прилично такие задачи называются "ad hoc".
Кстати, мне кажется, что обычно авторская оценка сложности таких задач довольно сильно занижена. Например, здесь существует много способов придумать себе развлечение с этой задачей на полчаса как минимум — и только пара коротких правильных решений.
Не называются такие задачи ad hoc. Ad hoc — это как раз когда нужно придумать новое решение, работающее только в данной задаче, и обычно такие задачи очень красивые (и сложные). А идея рассмотреть 4 места для перехода — довольно стандартная для подобных задач (да и придумывается буквально сходу), поэтому на ad hoc не тянет при всем желании.
Кстати говоря, откуда пошел термин "ad-hoc" и что он, собственно, означает? Я его впервые встретил в какой-то статье на старой версии usaco, где говорилось о классификации задач. Статья достаточно древняя, поэтому не исключаю, что это первоисточник, но, все же, не уверен.
Вроде бы словарь даёт нормальное описание: ad hoc лат. (специально) для этого случая, для определённого случая
К сожалению, не вижу конкретного определения, разве что есть статья в Википедии, но она не противоречит ни одной из интерпретаций выше.
В Е не надо ничего упихивать в тайм-лимит. Нужно считать N^2 полярных углов вместо N^3, а вместо бинпоиска написать Дейкстру с сетом.
Это я и называю "упихивать". Не упихивать — это когда написал в лоб (с подсчетом N^3 углов) — и зашло. А когда начинаешь думать, где тут что соптимизировать — это упихивание. В результате у меня тоже зашел только чистый куб без бинпоиска. Да и судя по ограничениям (N до 150, а не до 100 или 200, например), авторское решение вряд ли в 10 раз быстрее ТЛ
Пардон, как написать чистый куб без сортировки O(n^3) углов?
Все считал за куб, не заходил бинпоиск + бфс, переписал с дейкстрой и сразу АС.
Да вы все офигели, по-моему. Это соревнование по написанию программ, а Вы требуете для себя права не уметь писать программы?
Мы ничего не требуем. Дискуссия вроде бы шла на тему "почему сегодняшний контест не очень понравился некоторым участникам". Кому понравился — могут в ней не участвовать.
А по поводу требований — мы не требуем, а желаем, чтобы на коротких контестах не давали задачи, в которых надо тратить время на упихивание.
Насчет D и E полностью согласен.
Хоть я и не катал D с е-макса, она для меня была баяном с локального соревнования.
В Е меня возмущает тот факт, что для Java и C++ для нее выставлены одинаковые ТЛы (на яве пропихивается только вылизанное решение, а на сишке, очевидно, пихается много какая ботва).
не соглашусь насчёт java в E. У меня зашло после пары лёгких оптимизаций со второй попытки (если не считать трёх WA перед ними).
У меня зашло без всякого вылизывания.
Ага, у Дейкстры (хотя мне это больше напоминает алгоритм Прима) константа ощутимо меньше...
А я имел в виду вылизывание бинпоиска по ответу.
У меня бинпоиск по ответу, упихивать не пришлось — сразу зашла
С каким множителем — log(1 / eps) или log(n^3)?
С ДФСом или БФСом (если с БФСом, то с какой очередью)?
дфс, захардкожено 40 итераций
Можно посмотреть код?
Код
Спасибо.
Ещё можно делать дих по весам всех ребер...
У меня зашел без упихивания бинпоиск с 60 итерациями и n^3 вызовов atan2 на Java.
Над Вами сидели с битой и заставляли писать на java? На perle, подозреваю, многие задачи не заходят по времени — это повод выставлять отдельный ТЛ? По-моему, раз каждый волен выбирать язык программирования — он должен принимать его преимущества и недостатки.
Ну, знаете, Java все-таки заслуживает особого внимания (как один из официальных языков ACM ICPC).
Но мои проблемы с таймлимитом были как раз не из-за жабы, а из-за моих кривых рук. После разговора с winger-ом я выяснил для себя, что вычисление угла между векторами по формуле acos(dot(v1, v2) / (len(v1) * len(v2))), даже с предпосчитанными длинами, работает раза в 3 медленнее, чем по формуле abs(atan2(cross(v1, v2), dot(v1, v2))).
Я как раз из-за этого решил сравнивать не углы, а косинусы углов при проверке того, что это хороший переход. А acos использовать только при выводе ответа.
По-моему, первые три — обычные простые задачи, D была бы прекрасной несложной математикой, если бы не копипастилась, E тоже очевидна, единственное, что там требовалось — это нормально реализовывать геометрию, чтоб не тормозило. Я, например, использовал acos только один раз. Зашло после лёгкой оптимизации.
F — действительно неплохая задача.
Не знаю про копипасту, я вот решал D методом "ну не может быть, чтобы коды Грея тут были не при чем", чисто на интуиции, ничего не доказывая)
Я тоже не копипастил, но придумал идею сам и написал только после того, как доказал (да, я примерно помнил идею кодов Грея, возможно, мне это подсознательно помогло).
Это, видимо, просто два разных подхода: потратить время на доказательство или рискнуть минусом.
Ну я, конечно, локально проверил выполнение всех условий перед сабмитом. Так что рискнул всего лишь временем написания (3-4 минуты)
А как тут минус можно получить? Здесь же всего 16 вариантов входных данных и все легко проверить локально.
Да, разве что случайно, это я не подумавши сказал. В данном случае, как правильно заметил dalex, рискуешь только временем написания программы.
Минусы по этой задаче, однако же, присутствуют.
Можно было случайно отправить не ту задачу, забыть закомментить файловый ввод-вывод, вывести ответ в stderr, создать маленький массив, написать решение за квадрат(?!?), рассмотреть случай n=1 руками и допустить ошибку, и много чего еще :)
ну да, я понимаю, что минус можно получить даже за A+B =)
У меня два минуса по этой задаче — в первый раз отправил файл из другой задачи, во второй раз я уже понимал, что решение неправильное, и делал случайные правки, подробно разбираться за несколько минут до конца, правильный ли ответ выдает программа или нет было некогда, я успевал только что-то по мелочи исправить и сдать. Третий сабмит в результате оказался успешным — за минуту до конца тура.
Третий сабмит стал успешным, потому что он сделан на питоне!
Нет, неправда. Я умею писать на C++.
У меня в решении явно нет кодов Грея, связи прямой тоже я не вижу.. И это не перебор :)
А есть среди нас проходящие на онсайт, но по какому-нибудь, счастливому для меня, стечению обстоятельств не имеющих времени на это мероприятие?
Даже не буду спрашивать, наберётся ли таких 25 человек))
Много было разговоров, что можно зарегаться 3 раза, отрешать все 3 квала и получить 3 футболки. Я так не делал, честно поучавствовал только в одном, но всё равно получил 3 абсолютно одинаковых футболки :) первая пришла недели 2 назад, а сегодня с почты забрал ещё 2, пришли одновременно. Такие дела)
Видимо, организаторам очень понравились твои решения :-)
Пиши еще!
Можешь выложить фото футболки куда-нибудь?
По-моему не отличается от прошлого года(кроме, собственно, года)
Там синие рукава.
У меня не прогружается твоя картинка. Если у кого-то тоже, то вот вид спереди, а вот тут вид сзади
В Украину футболки еще никому не приходили?
Мне не пришла. Вот так, одним по три штуки, а другим — ничего))
У меня даже в Санкт Петербург еще не пришла :(