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

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

Во-первых, хотелось бы извиниться перед участниками за очереди тестирования в середине-конце первого часа. Для разогревочного раунда мы решили использовать задачи ИОИП — команда авторов задач 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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve E in ?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    There is one trick to search all cycles of length 3.

    code

    It seems that this code is slow but it works in O(n*sqrt) where n is number of vertexes in our graph (i don't remember proof of that). so use compression for numbers to make n = 400'000 not 1'000'000 in worth case

    so as you see this part solves when sides look like (x,y)(x,y) (x,z)(x,z) (y,z)(y,z). other cases, when answer looks like (x,x)(x,x)(x,x)(x,x)(x,x)(x,x) or (x,y)(x,y)(x,y)(x,y) (x,x)(x,x) can be solved in O(n*log) with map

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

D can be solved in O(1) by case-studying.

During contest, I coded a brute-force method to check all the possible assignment of knights and knaves for k ≤ 10. And, find out the pattern for each pair of