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

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

Всем привет!

10 февраля в 12:00 по московскому времени состоится вторая личная интернет-олимпиада для школьников, которая также будет являться вторым отборочным туром ИОИП. Вам предстоит помочь людям-паукам разобраться с их проблемами и вернуться в родные вселенные!

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

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

Олимпиаду для вас подготовили Николай Будин (budalnik), Михаил Анопренко (manoprenko), Дмитрий Филиппов (DimaPhil) и Григорий Шовкопляс (GShark).

Для связи с жюри можно использовать адрес электронной почты [email protected].

Удачи!

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

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

Итак, раунд закончился Как решать, желательно все?

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

    Я справился, к сожалению, только со второй, но, если кому-то нужно:

    Сначала стоит вспомнить об импликации Если A -> B = 111....11__2 = -1, то в двоичном представлении A нет ни одной единицы, чтобы ее не было в B Назовем это А полностью входит в В

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

    После удаления нужно проверить, получим ли мы вообще ответ. Можно сделать ИЛИ для всех чисел и посмотреть, полностью ли входит в полученное В. Если В входит, значит получить можно, иначе — какой-то бит мы не заполним

    И, наконец, чтобы ускорить решение, удалим все числа, полностью входящие в А. Теперь сортируем числа по убыванию и применяем самые большие к А. Применив самое большое, удаляем все невходящие в новое А и повторяем процесс, пока список подходящих чисел не закончится

    Надеюсь, что это хоть чуточку понятно

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

      Скоро должен быть разбор. Вот, что зашло по TL у меня: C: Воспользуемся динамическим программированием. Будем хранить достижимость состояния dp[i][j][k], где i, j отвечают за номер ячейки в нашей таблице, а k — это разница между площадью восточнее линии раздела и западнее линии раздела (k может принимать значения от -N * M до N * M). Чтобы ускорить решение, будем хранить состояние в битсете. Получаем решение за O(n^2 * m^2 / 64). Чтобы хватило памяти, пересчитывать надо по слоям.

      D: На 67 баллов построим обычный бор, будем удалять/добавлять в него строки. Клавишу "tab" можно использовать, пока из текущей вершины есть только один путь вперед. Чтобы получить 100, будем хранить в каждой вершине, куда приведет нас нажатие в tab, когда мы находимся в этой вершине (на сколько символов вперед мы переместимся и в какую вершину бора). На запрос мы отвечаем за O(answer_length). Получаем решение O(Q * sqrt(C)), где C — сумма длин всех строк в боре (1млн).

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

        Да, авторское решение по C на полный балл такое же, как у вас.

        А вот авторское решение по D отличается от вашего :) Забавно, что есть решение с корневой эвристикой.

        Разбор скоро появится.