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

Автор DimaPhil, история, 9 лет назад, По-русски

Всем привет!

Уже в эту субботу, 20 февраля в 16:00 по московскому времени состоится четвертая личная интернет-олимпиада для школьников. На этот раз помощь потребовалась фантастической неповторимой четверке — Атосу, Портосу, Арамису и Д'Артаньяну!

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

Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client (русская версия).

Олимпиаду для вас подготовили Дмитрий Филиппов (DimaPhil), Илья Пересадин (pva701), Дарья Яковлева (Devushka) и Григорий Шовкопляс (GShark).

Удачи!

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

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

Новый год уже близко...

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

На сайте написано, что олимпиада начнётся в 16:00.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Это ошибка в посте, олимпиада начнется в 16:00

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

Автокомментарий: текст был обновлен пользователем DimaPhil (предыдущая версия, новая версия, сравнить).

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

Каналья! Тысяча чертей!

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

Почему мои посылки по D были на 60 баллов, а теперь WA #1?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Теперь ещё нельзя просмотреть код некоторых посылок по D. Что-то странно.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -44 Проголосовать: не нравится

    Все посылки по D были перетестированы. Можете проверить соответствующий комментарий во вкладке Messenger. Также советую, в будущем писать на почту Жюри по всем вопросам, потому что комментарии тут мы читаем не так оперативно, как почту. Пост используется именно для анонса, а не для связей с общественностью:)

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

Где можно порешать задачи этой олимпиады? (сдать их)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Как только закинут в тренировки наверное.

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

Разбор будет?

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

Может кто подскажет как решать B и С? А то, я так понимаю, разбора не будет

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

    Задача B:

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

    Задача C: Положим все строки в бор, каждая вершина в боре задает некоторый префикс, количество строк с этим префиксом — кол-во листов в этом поддереве.

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

    Теперь для каждой вершины знаем suff[v] — длина максимального суффикса t, lev[v] — глубина этой вершины. В предка на высоте lev[v] — suff[v] положим пару (lev[v], leafs[v]). Теперь просто спускаемся строкой t по бору, в каждой вершине для каждой пары релаксируем ans[first] = max(ans[first], second).

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

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

      Можно проще. Что мы хотим? Посчитать для каждой вершины бора наибольший общий суффикс с T.

      Давайте сделаем следующее, рассмотрим все строки положенные в бор (они заданы во входных данных), мы хотим у каждого префикса каждой из строк найти наибольший общий суффикс с T.

      Перевернём задачу. Поревёрсим строку T, а также все интересные нам строки, теперь задача свелась к поиску наибольшего общего префикса с ревёрсом T у каждого суффикса каждой строки. Решается Z-функцией.

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

    deleted

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

Как решать задачу D?

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

    40 баллов: можно за 27 попыток в худшем случае определить ответ по всем первым 4 тестам. Просто выводим сразу ответ. Если подошел, то оставляем, нет — прибавляем к нему 1 и отсылаем еще. Ограничений по посылкам не было.
    50-100 баллов: бинарный поиск нужного элемента, работающий за log(n) или log(n)+1. Вроде бы не подходит ко всем тестам. Но можно предположить, что номер искомого элемента при делении на 10 дает остаток 0, 1, 2, 3, ..., 9, и искать таким образом только среди таких элементов за log(n/10) и 10 посылок. Выбирайте сразу остатки от 30, чтобы наверняка получить результат.
    Не реализовывал, должно было зайти.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Авторское решение такое:

    Наблюдение: во всех тестах суммарное количество монет — степень тройки. Давайте тогда научимся для количества монет 3n решать задачу за n действий.

    Для примера рассмотрим тест с 13 золотыми и 14 серебряными монетами. Разделим эти 27 монет на три группы: (4 золотых, 5 серебряных), (4 золотых, 5 серебряных), (5 золотых, 4 серебряных). Взвесим первые две группы. Теперь рассмотрим три случая:

    1. Чаши весов уравнялись. Это значит, что фальшивая монета в третьей группе.
    2. Левая чаша весов меньше правой. Это значит, что фальшивая монета либо среди 4 золотых монет из левой чаши, либо среди 5 серебряных монет из правой.
    3. Левая чаша весов больше правой. Аналогично 2 пункту: фальшивая монета либо среди 4 золотых монет из правой чаши, либо среди 5 серебряных из левой.

    Во всех трех случаях мы перешли от 27 монет к 9, то есть уменьшили количество рассматриваемых монет в три раза. Значит мы научились решать задачу для 3n монет за n действий, ура!