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

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

Тут короткие разборы и решения задач второго тура отборочного этапа Олимпиады Университета Иннополис, который прошел 14 декабря 2019 года. Порешать задачи можно в тренировках: Отборочный этап Олимпиады Университета Иннополис. Второй тур. 2019-2020. Здесь еще был анонс и некоторые обсуждения.

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

102461A - Expression Formatting

Разбор
Решение на Python

Авторы задачи: niyaznigmatul, pashka

102461B - Contest Rescheduling

Разбор
Решение на C++

Авторы задачи: niyaznigmatul, pashka

102461C - Advertisement Profit

Разбор
Решение на C++

Авторы задачи: budalnik, Aksenov239, VArtem, niyaznigmatul

102461D - RSA factoring

Разбор
Решение на Kotlin

Автор задачи: VArtem

102461E - Black Friday

Разбор
Решение на C++

Авторы задачи: never_giveup, Burunduk1

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

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

Если решать задачу Е, поддерживая множество непересекающихся отрезков, то как тогда восстановить ответ?

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

    При добавлении отрезка нужно не удалять старое множество отрезков, а перезаписывать его заного и обновлять новым отрезком. В конце у нас получится N множеств, каждое размером не более 90, поэтому уложится по памяти.

    Теперь будем идти с конца по отрезкам, каждый раз либо включая текущий отрезок в ответ, либо нет. Множества, сохранённые вначале, помогут нам понять, можем/должны ли мы взять текущий отрезок в ответ или нет.