Всем привет!
Напоминаю, что первый квалификационный тур RCC 2013 состоится уже в эту субботу, 13 апреля, в 19-00. Регистрация идет на сайте http://russiancodecup.ru, там же состоится соревнование. Продолжительность квалификационного раунда — 2 часа.
Неудобно писать в субботу вечером? Ничего страшного, вторая квалификация пройдет в субботу 11 мая в 12-00, а третья — в воскресенье 2 июня в 14-00.
200 лучших из каждой квалификации пройдут в отборочный раунд, который состоится в воскресенье, 16 июня в 14-00, а 50 победителей отборочного раунда примут участие в финале, который состоится в Москве в сентябре.
А учитывая, что кроме квалификации RCC на этих выходных нас ждут квалификации GCJ и КРОК, нас ждет горячая пора. Всем удачи!
Необходимо принимать в каждом квалификационном раунде участие,или можно пропустить первый раунд и принять участие во 2-ом допустим или в 3-ем???
Достаточно поучаствовать и попасть в "топ 200" хотя бы в одном.
Mожно пропустить первый раунд и принять участие во 2-ом или в 3-ем.
Давайте скорее обсуждать задачи! Как решать Е?
разбор уже на сайте есть
Уже нет :)
[deleted]
Просьба к организаторам: можно сделать кнопочку "скрыть боковое меню с твиттером". А то сообщения вида "Влад Епифанов сдал 4" когда я сабмичу вторую немного демотивируют.
Влад-то ладно, а вот картинка там действительно отвлекала. Хорошо, что она уехала.
Для этих целей я использую adBlock
А Твиттер — это не реклама, AdBlock его не блокирует.
Можно добавить ручками в пару кликов
Отличная мысль обязательно попробую
Залейте в тренировки, пожалуйста, кому не лень.
Вот и тренировка — 2013 Russian Code Cup, квалификация 1
Спасибо.
Мне как бы все равно, меня она только в пределах добивания интересует... Но для полного соответствия не мешало бы длительность поменять (2 часа, а не 5, как сейчас).
Спасибо, поправил.
Тем временем разбор появился и опять пропал.
Но я успел)))
Мне вот разбор не понравился. Опять он какой-то слишком уж поверхностный, в этом году.
По поводу первой — я тоже написал очевидное решение с перебором. Но мне только что подсказали, что можно повернуть все прямоугольники в одну сторону (т.е. положить их на более длинную или более короткую сторону) и ничего не перебирать.
По поводу второй — авторский разбор выглядит, как издевка. Примерно с таким же успехом можно было написать "переберите за квадрат все варианты, просуммируйте, только аккуратно, чтобы не посчитать что-то несколько раз и ничего не пропустить". Было бы почти настолько же информативно. Я считал ответ как сумму числа квадратов, числа не квадратных прямоугольников, числа трапеций вида "3 стороны равны, четвертая — нет" и числа трапеций вида "основания не равны между собой и не равны с боковыми сторонами". Можно было как-то проще? Чтоб и случаев не слишком много, и формулы не слишком большие.
Ну и третью я из авторского тоже не сильно понял:(
Но разбор это мелочи) Спасибо авторам за качественную систему (ничего не падало от перегруза и все оперативно тестировалось), хорошие задачи... И новую фичу с "нажмите по никнейму и прочтите достижения". Или эта фича уже была раньше, просто я не замечал?)
Фича сохранилась с финала прошлого года. Собственно, она есть только у тех, кто туда вышел.
Было бы круто сделать её
для всехдля более широкого и логичного круга лиц.По первой, авторское решение такое и есть. Но, признаюсь, к тому решению я не смог формализовать доказательство, а писать просто так — как-то неправильно.
По поводу второй, могу сказать следующее, я пытался писать с наименьшим числом случаев, но у меня как-то не особо получилось. Приложу тогда ссылку на код — http://pastebin.com/7gjSLf1A.
В третьей я сдал такое решение: посчитаем количество пар чисел которые в сумме дают степень двойки из инпута. Скажем что каждая такая пара это связь. Тогда если связей k то ответ это 2^{n-k}. Почему никакие 2 свзяи не могут быть транзитивными я не доказывал, но видимо это можно сделать.
Если рассмотреть все связи конкретного числа x, то понятно, что x будет бОльшим не более чем в одной из своих связей (пусть x + y = 2^k, x > y, тогда 2^k-1 < x < 2^k, очевидно x не может удовлетворять такой оценке сразу для двух k). Тогда если рассмотреть связь как направленное ребро от меньшего числа к большему, в каждое число входит не больше одного ребра, то есть получившийся граф — просто какое-то ветвящееся дерево, в нем противоречий очевидно быть не может.
Спасибо, теперь я понял, что у меня такое же решение. А Copymaster выше дал красивое доказательство корректности.
Кстати, почему так много людей посыпались на четвёртой задаче?
Я, конечно, понимаю, что это геометрия=) Но всё же решение довольно простое и очевидное:
Для каждого астероида найдём время входа и выхода из атмосферы — это самое обыкновенное квадратное уравнение, забиваем их в 2 массива, сортируем каждый отдельно, и когда получаем очередной запрос, то ответом является: (количество-уже-влетевших — количество-уже-улетевших), и первое, и второе находится с помощью бинпоиска. Ну а для того, чтоб не было проблем с точностью, можно было все времена входа в атмосферу сделать чуть-чуть раньше, а выхода — чуть-чуть позже.
Никогда не понимал, почему многие так ленятся написать простую честную формулу, и лепят везде бинпоиски-тернарники. Господи, здесь же квадратное неравенство, ну куда уж проще? :-)
Да просто это такое шаблонное мнение, что геометрия — что-то сложное. Это далеко не всегда так. Я сейчас тоже ему поддался, в частности, гуглил "пересечение сферы и прямой", но ничего не нашел. Поэтому взял ручку и листочек и вскоре понял, что это, блин, квадратное неравенство!
БинПоиск по массиву — что может быть проще?) Вся геометрия заканчивается на квадратном уравнении.
Решение-то вот оно: http://ideone.com/Uw0rVr
Искать корни бинпоиском вроде никто и не предлагал)
Почему, кстати? Я искал корни бинпоиском, чтобы избежать даблов. Мне кажется если искать через дискриминант, то не хватает 64 бит, чтобы все сделать в целых числах?
Дискриминант в 64 бита влезает, а дальше корни можно округлить до целых.
Логично, это я протупил. Почему-то подумал что из-за деления на коэффициент при квадрате округлить нельзя.
Это же ИТМО. Они не делают тесты на точность
А зачем ставить лимиты под границу лонга и при этом не ловить решения в даблах на точность?
Понятно, что квадратное неравенство. Писать тернарник + бинпоиск не намного дольше, особенно если не протормозить с long overflow. Зато все в целых числах.
никакие сортировки/бинпоиски же не нужны, можно завести массив на 10^7 элементов, пометить в нём начало/конец.
В моём случае
, в вашем O(n + m + maxt) . Асимптотика разная, но и то, и то для данного условия подходит, поэтому говорить "не нужны" как-то неуместно. Увеличили б maxt или сделали б не целые запросы — не прошла бы ваша идея, увеличили бы n или m — моя б не прошла.
А по сложности кодинга, и то, и то — 5 строк.
А почему бы не добавить "-std=c++0x" в строку компиляции для с++? Было бы удобно пользоваться новшествами языка :)