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

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

Всем привет!

В это воскресенье, 21 января, мы начинаем сезон личных интернет-олимпиад — в 16:00 по московскому времени состоится первая личная интернет-олимпиада для школьников, которая также будет являться первым отборочным туром ИОИП. Вам предстоит помочь подросткам, попавшим в игру Джуманджи, со всеми возникшими у них трудностями.

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

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

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

Также спасибо Ильдару Гайнуллину (300iq) за помощь в тестировании задач.

Удачи!

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

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

It smells like long adventrure

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

Извините, а это нормально что я зарегестрировался, но не могу зайти на PCMS@ Web Client?

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

    Мало просто заполнить форму, еще необходимо дождаться подтверждения регистрации.
    тут можно посмотреть статус...

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

    Проблемы с доступом к PCMS? Просто добавь 2 и получи PCMS2...

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

Можно ли писать не школьникам вне конкурса?

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

У вас тоже не грузиться?

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

Подскажите, где найти условия задач? Возможно, у меня проблемы с отображением некоторых ссылок.

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

Как решать д?

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

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

    У нас ДП такая: dp[v, k, flag], где v -- вершина, k -- количество гепардов ягуаров, которых мы хотим поставить в поддереве с вершиной v, flag -- флаг, он обозначает следующее:

    • 0 -- через v не проходит путь никакого гепарда ягуара
    • 1 -- через v проходит путь, и не опускается назад в поддерево
    • 2 -- через v проходит путь, и опускается назад в поддерево

    Начальные значения: dp[v, 0, 0] = dp[v, 1, 1] = 0.

    В самом конце подсчета динамики для заданного v мы увличиваем все значения dp[v, k, 1] и dp[v, k, 2] на значение энергии в вершине v.

    Как делать пересчеты? Мы добавляем функцию merge, которая добавляет сына к ответу. Она работает за O(kk2), где k1 -- размер дерева, которое у нас уже есть, а k2 -- размер поддерева сына. Таким образом мы добавляем к нашей вершине v сыновей по одному.

    Можно доказать, что такая динамика работает за O(n2).

    Как она пересчитывается, смотрите код для лучшего понимания.

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

      Может быть тогда кто-нибудь поделится идеями решения на полный балл C и B? Хеши в третей задаче у меня зашли только на длины строк до 10^5.Что дальше? Из предположений только алгоритм Манакера, но может быть можно какое-нибудь ДП насчитать?

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

        В третьей да, Манакер. Конкатенируешь строку два раза, далее нужно найти наибольший палиндром, не превосходящий длины строки. Это делается так: находим наибольшие палиндромы четной и нечетной длин, затем их уменьшаем, пока они не станут не больше длины строки. Потом ищем максимум из них.

        Во второй надо все IP-адреса перевести в uint64-числа. Затем ответ магическим образом оказывается равен b - a - 1 - k, где k — количество IP-адресов i таких, что a ≤ i ≤ b. Осталось проверить случай, когда это невозможно (между a и b нет подряд идущих).

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

          Спасибо. В плане третьей всё понятно. Вопрос по второй: я так понимаю, что под uint64 подразумевается не unsigned long long. Если так, то можно чуть подробнее об этом / ссылку на какой-либо материал по данному типу?

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

            uint64 это, по сути, unsigned long long (64-х битный беззнаковый). Я написал uint64, чтобы было без привязки конкретно к языку C++.

            А вообще, я не любитель long long и всегда использую int64_t и uint64_t вместо long long и unsigned long long соответственно (если это возможно).

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

              Видимо, что-то всё-таки понял неверно. Во-первых, при вычитании у нас могут появиться маски, по типу 999, которые больше 255. Во-вторых, x <= 8, т.е. длина числа будет 8 * 3 = 24, что, в свою очередь, больше ограничений типа.

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

                x ≤ 8, каждое число по 8 бит, значит, все поместится в 8 * 8 = 64-х битный тип.

                Мы преобразуем IP-адреса в uint64-числа таким образом. Самую правую часть адреса мы помещаем в младшие 8 бит, следующую слева от нее -- в следующие в 8 бит и так далее. При таком преобразовании каждое число меньше 28x будет соответствовать валидному адресу и наоборот.

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

        Если попробовать убрать лишние взятия остатка от деления, то на 100 заходят хеши.

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

          Можно подробнее по этому поводу? Старался делать как можно оптимальнее и лишний раз не брать по модулю. Или может быть дело в том, что я считаю всё в long long?

           h[i + 1] = h[i] * P + s[i];
                if(h[i + 1] >= MOD) h[i + 1] %= MOD;
          
          ll get_hash ( int l, int r ) {
                return (h[r + 1] - h[l] * deg[r - l + 1] + MOD * MOD) % MOD;
          };
           
          ll get_revhash (int l, int r) {
              return (revh[l + 1] - revh[r + 2] * deg[r - l + 1] + MOD * MOD) % MOD;
          }
          
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            При сумме/разности по модулю можно использовать следующий трюк: вместо a = (b + c) % MOD писать как-то так:

            a = b + c;
            while (a >= MOD) {
                a -= MOD;
            }
            

            Утверждается, что, если a < MOD и b < MOD, то такая конструкция отработает быстрее.

            С разностью нечто похожее.

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

              Да, это понятно. Но не совсем понимаю, как этот метод применим к коду выше. Во всех случаях используется умножение, где в любом случае нужно брать остаток от деления. Мне кажется, что будет быстрее загнать сумму/разность под это же взятие остатка, т.к. один раз нам всё равно придётся это сделать. Разве не так?

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

                Остатки от деления надо брать поменьше, так что любое избавление от них полезно. Можно еще дальше подумать и пооптимизировать.

                В общем, полный простор для воображения :)

                Можно еще попробовать хэши по модулю 264 и надеяться, что анти-хэш тест авторы не нагенерили (скорее всего, это так).

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

                  Нет, там в подгруппе на 45 баллов было 1-2 теста на uint64(

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится
            int res;
            ll h[2000005], rh[2000005], deg[2000005];
            
            int getHash(int l, int r) {
            	if (l == 0)
            		return h[r];
            
            	res = (h[r] - h[l - 1] * deg[r - l + 1]) % mod;
            
            	if (res < 0)
            		res += mod;
            
            	return res;
            }
            
            int getRHash(int l, int r) {
            	if (r + 1 == str.size())
            		return rh[l];
            
            	res = (rh[l] - rh[r + 1] * deg[r - l + 1]) % mod;
            
            	if (res < 0)
            		res += mod;
            
            	return res;
            }
            

            И можно избавиться от ненужных ифов, если сделать нумерацию не с нуля, а с единицы.

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

Добавьте контест в тренировки.

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

Кто прошёл первый отборочный тур??