Блог пользователя Burunduk2

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

161A - Оденьте их скорее!

Будем рассматривать бойцов в порядке сортировки, то есть так как они заданы во входных данных. Утверждается, что для текущего бойца всегда выгодно из всех неиспользованных подходящих бронежилетов выбирать тот, у которого bj минимально.

В таком случае задача решается используя метод <<двух указателей>>. Первый указатель двигается по бойцам. Вторым указателем подбирается минимальный по размеру бронежилет из неиспользованных такой, что bj - x ≥ ai.

Асимптотическая сложность решения O(n + m).

Автор идеи: Burunduk1

161B - Скидки

Задача решается жадным алгоритмом. Пусть у нас есть x табуреток. Можно доказать, что всегда выгодно min(k - 1, x) максимальных табуреток разложить в min(k - 1, x) корзинок по одной.

Все оставшиеся табуретки и карандаши нужно положить в оставшиеся пустые корзинки. Заметим, что либо у нас не останется табуреток, либо останется ровно одна пустая корзинка.

Авторы идеи: Burunduk2 и Burunduk1

161C - Абракадабра

Предположим, что максимальный по значению символ в строке входит в ответ. Тогда ответ равен min(r1, r2) - max(l1, l2). Предположим, что это не так. Тогда нужно разрезать каждую из строк по этому символу (в одной из частей может получиться пустая строка) и запустить алгоритм рекурсивно от каждой из полученных пар строк. Можно доказать, что это решение имеет сложность O(K), где K — значение максимального символа.

Другое решение:

Задача решается перебором старшего (то есть, наиболее редкого) символа, который будет находиться в наибольшей общей строке. То есть, если x — старший символ, который встречайтся в обоих строках, и (это важно) в строках не встречаются более редкие символы, то ответ считает по несложной формуле. Второе условие (в строках не встречаются символы, более редкие, чем рассматриваемый) может, вообще говоря, не выполняться. Но его легко достичь, заменив строки на списки строк: если сейчас рассматривается символ x, то вместо каждой из строк у нас будет по несколько строк: изначальные строки, разбитые символами, которые старше x. Причём в каждом списке имеет смысл хранить не более двух строк: если более редкие символы разбивают на три и более подстроки, то среди этих подстрок встретятся «полные» строки. Например, если строку badabaca разбить по символам не младше c, получится список ba, aba, a. Очевидно, что из этих трёх строк достаточно оставить одну aba. Осталось научиться дробить строки и считать ответ для фиксированного старшего символа. Для этого рассмотрим, как зависит символ от позиции в строке.

Здесь удобно нумеровать символы строки с единицы, тогда:

  • на нечётных позициях стоят символы «a»
  • на чётных позициях стоят символы «b» и старше
  • на позициях, кратных четырём, стоят «c» и старше
  • на позициях, кратных восьми, стоят «d» и старше
  • и так далее, символ соответствует степени двойки, входящей в номер позиции

Используя эту закономерность, можно проверять, лежит ли в строке символ x или старше, и находить его позицию. Для этого достаточно найти минимальную степень двойки, не меньшую левой границы строки. Если она не выходит за правую границу, это и будет ответ.

В итоге решение может быть следующим:

  1. Перебираем символы, начиная со старшего. На каждом шаге храним два списка: подробленную первую подстроку и подробленную вторую. Изначально эти списки содержат по одному элементу, собственно, исходные строки.
  2. На каждом шаге перебираем пары строк из имеющихся списков и проверяем,лежит ли текущий символ в каждой из выбранных подстрок. Если лежит — обновляем ответ.
  3. Перед тем, как перейти к следующему (то есть, более младшему) символу, переразбиваем списки строк. Если в каком-то списке окажется хотя бы три строки, то из них можно оставить вторую (она гарантированно будет полной строкой соответствующего уровня).

Автор идеи: avm

161D - Расстояние в дереве

Эту задачу можно было решать методом динамического программирования. Подвесим дерево за какую-нибудь вершину. Для каждой вершины v дерева, посчитаем значания d[v][lev] (0 ≤ lev ≤ k) — количество вершин в поддереве, расстояние до которых равно lev. Заметим, что d[v][0] = 0.

Далее по этим значениям посчитаем ответ. Ответ равен, сумме по всем вершинам v двух величин:

  • Количество путей длины k, которые начинаются где-то в поддереве вершины и заканчиваются в самой вершине. Это количество очевидно равно d[v][k].
  • Количество путей длины k, которые начинаются где-то в поддереве вершины и заканчиваются в где-то в поддереве вершины. Это количество равно сумме по всем сыновьям u вершины v величины .

Считаем сумму по всем вершинам. Получаем решение за O(n·k).

Автор идеи: Burunduk1

161E - Медвежатник Поликарп

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

Так как матрица симметричная, то она полностью определяется своими элементами не ниже главной диагонали. Переберём все возможные значения цифр, которые находятся в клетках выше главной диагонали (не более 106 вариантов). Заметим, что теперь значения оставшихся неопределёнными цифр, которые стоят на главной диагонали, независимы между собой, так как каждое из них влияет ровно на одну строку матрицы. Поэтому достаточно независимо посчитать количество возможных вариантов для каждой из цифр на диагонали и перемножить полученные значения, чтобы получить количество способов дополнить матрицу до требуемой.

Более того это количество можно предподсчитать заранее для каждой неизвестной позиции и для каждого набора уже известных цифр. Такое решение уже укладывается в ограничение по времени.

Можно было пойти и дальше, отсекаясь при переборе значений цифр выше главной диагонали, если после добавления очередной цифры её строку или столбец больше нельзя было дополнить до простого числа (возможность это сделать так же можно предподсчитать заранее). Данное решение позволяет найти ответы для всех возможных тестов за отведённое время, но это не требовалось.

Автор идеи: avm

Задачи раунда готовили (в алфавитном порядке): arseny30, at1, avm, Burunduk1, Burunduk2, burunduk3, Gerald, levlam, MikeMirzayanov, Nickolas, vysheng

Полный текст и комментарии »

Разбор задач VK Cup 2012 Раунд 1
  • Проголосовать: нравится
  • +83
  • Проголосовать: не нравится

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

Здравствуйте!

Пришла пора первого раунда нашего соревнования VK Cup 2012. Напоминаем, что регистрация на этот раунд также необходима и завершается она за пять минут до начала.

Над задачами работал разнообразный коллектив авторов как со стороны ВКонтакте, так со стороны Codeforces и Саратовского государственного университета. Мы постарались сделать всё, чтобы процесс оказался интересным, а в следующий раунд прошли сильнейшие.

Раунд пройдёт по правилам Codeforces: с распределением на комнаты, со взломами и с обычным падением стоимости задач со временем. Раунд будет рейтинговым как если вы участвуете в чемпионате, так и если вы пишете вне него.

Из всех участников первые 700 пройдут во второй раунд сразу же. Ещё 50 участников смогут выйти во второй раунд через первый Wildcard-раунд, который состоится 18 марта по необычным правилам.

Отдельное пожелание от Burunduk1: «Пожалуйста, чтобы раунд для вас был еще интереснее, прочитайте условия ВСЕХ задач.»

Успехов!

Update: раунд завершился, поздравляем всех участников, набравших 1712 баллов (FatSheep) и более с проходом во второй раунд!

Update2: опубликован разбор задач: http://codeforces.com/blog/entry/4097

Update3: После удаления читеров результаты претерпели некоторые изменения. Во второй раунд проходят участники, набравшие 1684 и более баллов. Всех остальных участников ждём в первом wildcard-раунде, это последний шанс пройти дальше в турнире.

Полный текст и комментарии »

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