Автор RussianCodeCup, 11 дней назад, По-русски,

Всем привет и спасибо тем, кто принял участие в разогревочном раунде.

Во-первых, хотелось бы извиниться перед участниками за очереди тестирования в середине-конце первого часа. Для разогревочного раунда мы решили использовать задачи ИОИП — команда авторов задач RCC и ИОИП в целом совпадает — тур подготовили Виктория Ерохина (viktoria), Илья Збань (izban), Станислав Наумов (josdas), Михаил Путилин (SpyCheese), Андрей Станкевич (andrewzta), Дмитрий Филиппов (DimaPhil), Григорий Шовкопляс (GShark). Мы хотели дать возможность всем желающим познакомиться с довольно интересным, на наш взгляд, набором задач.

К сожалению, мы не учли один аспект. Можно заметить, что в RCC мы стараемся делать мультитест в задачах, ведь самая затратная операция — запустить решение участника на тесте. Поскольку ИОИП расчитывалась на меньшую нагрузку, в первой задаче оказалось 32 теста. Это не так много по меркам олимпиадной задачи, но когда в течение 15 минут 400 участников прислали правильное решение этой задачи, наших проверяющих мощностей не хватило.

Мы оперативно уменьшили число тестов в задаче и к середине контеста ситуация нормализовалась. Мы учтем этот эффект и будем тщательнее планировать формат тестов в задачах будущих контестов.

Перейдем теперь к разбору.

A. Космический корабль

Заметим, что если сила босса равна x, то сумма сил всех врагов равна 2x. Следовательно, чтобы найти силу босса, необходимо посчитать суммарную силу всех врагов и разделить ее на 2. После этого необходимо найти какого-нибудь врага с такой силой и поменять это значение в массиве f со значением последнего врага.

B. Рейнджеры в автобусе

Будем обрабатывать пассажиров по очереди и для каждого определять, кем он мог бы быть. Сразу заметим, что Розовый Рейнджер может есть куда угодно, поэтому каждый пассажир мог бы быть Розовым.

Для каждого места будем помнить, свободно ли оно. Для этого заведем unordered_set, в котором будем хранить занятые места. Проверим, мог бы очередной пассажир быть Красным Рейнджером. Для этого найдём место, на которое сел бы Красный. Переберём циклом ряд от 1 до n, если попался ряд, в котором есть свободное место, выбираем левое, если оно свободно, или правое, если нет — это и есть место, куда сел бы Красный. Поскольку он выбирает место однозначно, мы можем определить, мог бы этот пассажир быть Красным — нужно проверить, что он сел именно на это место. Таким же образом узнаем, куда сели бы Синий, Жёлтый и Чёрный – разница будет в порядке перебора рядов (от 1 до n или наоборот) и в порядке выбора места в ряду (сначала левое или правое). После обработки пассажира отметим его место как занятое.

Решение работает за O(nk) и использует O(k) памяти.

Чтобы улучшить решение, заметим, что каждый из циклов останавливается, когда находит ряд, в котором есть свободное место. Это означает, что нужно быстро находить первый и последний незанятые ряды. Будем поддерживать эти значения — first и last. Изначально first = 1, last = n. После каждой итерации цикла обновим эти значения. Будем увеличивать first на 1, пока ряд first занят, затем уменьшать last на 1, пока ряд last занят. Занятых рядов не может оказаться больше k / 2, поэтому first и last сделают O(k) шагов. Таким образом, улучшенное решение работает за O(k) и проходит все тесты.

C. Волшебное оружие

Предпочитаем массивы: R[a][b] — количество фрагментов у красного рейнджера, у которых первая цифра равна a, а последняя равна b; G[a] — количество фрагментов у зеленого рейнджера, у которых последняя цифра равна a; и B[b] — количество фрагментов у синего рейндждера, у которых первая цифра равна b.

Если бы у разных рейнджеров не было одинаковых моделей фрагментов, ответ был бы равен сумме по всем a и b значений G[aR[a][bB[b].

Чтобы учесть ситуацию, когда у какой-то пары совпадают модели, посчитаем количество пар фрагментов с одинаковым номером модели у красного и синего, красного и зеленого и синего и зеленого рейнджеров, соответственно (например, с помощью std::map). Заметим, что подходящими являются только номера, у которых первая и последняя цифра совпадает. Воспользуемся формулой включения-исключения, вычтем из ответа число таких пар, и добавим удвоенное количество троек фрагментов, когда у всех трех рейнджеров совпадают модели.

D. Рыцари и лжецы

Будем решать задачу динамическим программированием по профилю. Найдем для примера максимальное количество рыцарей.

Пусть dp[i][mask_prev][mask_cur] — максимальное количество рыцарей, которые могут быть в расстановке из первых i столбцов, mask_cur — маска i-го столбца, а mask_prev — (i - 1)-го.

Затем переберем маску для (i + 1)-го столбца и проверим выполняются ли ограничения на соседей, для солдат из i-го столбца, так как теперь известны все их соседи.

Для первого и последнего столбца ограничения нужно проверять отдельно, потому что у них нет одного из соседей.

База: dp[2][mask_prev][mask_cur] равно количеству единиц в mask_prev и mask_cur, если mask_prev может стоять слева от mask_cur.

Переход: dp[i + 1][mask_cur][mask_next] = dp[i][mask_prev][mask_cur] + ones(mask_next), где ones(x) — количество единиц в маске x.

Ответ будет максимумом среди всех dp[k][mask_prev][mask_cur], таких что mask_cur может находится справа от mask_prev.

Наконец заметим, что случай k = 1 стоит разобрать отдельно, поскольку в этом случае нет предыдущего столбца.

E. Параллелепипед

Расскажем об основной идее решения. Во-первых, рассмотрим отдельно все параллелепипеды, у которых две или три стороны совпадают, это можно сделать за O(n).

Пусть теперь все три стороны различны. Построим следующий неориентированный граф: вершинами будут возможные длины сторон, соединим ребром числа a и b, если имеется хотя бы два листа размером a × b. Задача свелась к рассмотрению треугольников в получившемся графе, это можно сделать за O(n2 / w) или O(nsqrt(n)) (здесь w обозначет размер машинного слва, 32 или 64, этот множитель возникает при битовом сжатии в поиске треугольников).

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +23
  • Проголосовать: не нравится  

Автор RussianCodeCup, 2 недели назад, По-русски,

Всем привет!

Мы рады представить Russian Code Cup 2017! Отборочные раунды начнутся в апреле, а финальный раунд пройдет онлайн в сентябре. В каждом из трех квалификационных раундов в отборочный раунд выйдет по 200 лучших участников, а 50 лидеров отборочного раунда попадут в финал. Задачи будут предложены на русском и английском языках.

Найти полное расписание турнира и зарегистрироваться можно на http://russiancodecup.ru, обратите внимание, что тем, кто участвовал в прошлые годы, необходимо подтвердить регистрацию на этот сезон.

Пока до первого квалификационного раунда еще больше двух недель, мы хотели бы пригласить всех на разогревочный раунд в воскресенье, 19 марта, в 14-00 по московскому времени. Раунд пройдет на http://russiancodecup.ru, продлится 2 часа и позволит познакомиться с системой и потренироваться перед основными раундами.

Удачи всем и до встречи на раундах!

UPD: Напоминаем, контест начнется в 14-00 по московскому времени. Задачи разогревочного раунда базируются на задачах заключительного этапа ИОИП, которую готовит та же команда авторов. Мы просим участников ИОИП поступить честно и не принимать участие в разогревочном раунде. Всем удачи!

UPD2: Спасибо всем участникам, которые устоили нам настоящее стресс-тестирование. К сожалению, в первый час контеста очереди были существенными, мы постарались решить эту проблему, и где-то с середины тура задержки уже не должны превышать 2-3 минут. Мы не допустим образования очередей в квалификационном и отборочном турах.

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +87
  • Проголосовать: не нравится