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

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

Странно, что еще нет этой темы, ведь соревнование уже почти началось.

Надеюсь вы не забыли и уже готовитесь его написать. Удачи.

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

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

Так все-таки, сколько будет идти контест? В системе 5 часов, а по идее должно быть 3 часа?

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

объясните, пожалуйста последние две

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

Как решать 4ую, 5ую, 6ую?

P.S. И вторую еще, пожалуйста.

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

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

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

      Делал примерно так же, 96

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

        120 у меня, это фулл?

        PS по зиме 20, печалька

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

          Да, это фулл

          У меня тоже по зиме 20 :( Даже непонятно из-за чего.

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

            как делали? Я двумя фенвиками сначала плюсовал отрезки, которые надо считать. Потом пробовал каждый из макс. отрезков увеличить до 3Т и выбирал тот, где больше всего не отмеченных клеток.

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

              Делал по-тупому, за O(N).

              P.S. Попозже расскажу.

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

      Порядок имеет значение в одном месте — на краях. Поскольку крайние числа войдут в сумму только один раз, то туда надо ставить наименьшие из группы наибольших (для максимума) и наибольшие из группы наименьших (для минимума).

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

        да, я так и написал, что особенного внимания стоят только края

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

          Тогда ещё можно обломаться на заполнении неэкстремумов, а так вроде всё то же самое — 120.

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

    Моё решение 5й (из-за бага не взяло 3 группы, потом допилил):

    На самом деле, задача — найти N-ое число, у которого при разложении нет простых сомножителей < P. Поскольку все числа, которые интересуют нас представимы в форме P * X, где Х — не содержит в разложении нет простых сомножителей < P, то найдём такое число и умножим на Р — получим ответ.

    Итого, если P >= 19, то можно запустить простое решето для поиска простых чисел (итерации < P, числа до (10^9)/P). Во время влазит. Если P < 19, то у решета период не будет большим (произведение всех простых чисел до Р включительно), и посчитав для периода, можно легко найти нужное.

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

    Для P = 2 и P = 3 — формулки. Для P > 17 — тупой перебор(для каждого числа от P^2, P^2 + 2 * P, P^2 + 4 * P, ... просто смотрим, делится ли оно на какое-нибудь простое меньшее P) Для P = 5, 7, 11, 13, 17 — небольшой предпосчет, и опять же, перебор.

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

    5я у меня так — если p >= 1000, то ответ — произведение p и (n — 1) го простого если считать с p (случай n = 1 разбирается в начале). Просто сгенерируем все эти простые и возьмем n-1 е. Если p < 1000, то будем искать бинарным поиском по ответу, а затем просто дфсом по формуле включения-исключения искать, сколько до данного подходят 6я — будем считать следующий хеш — если токен больше не встречается в строке, то на этом месте ставим 0, иначе расстояние до следующего вхождения. Посчитаем хеши всех подстрок нужной длины и сравним с хешом образца. У меня не прошли 2 последних теста по ML, вот код

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

double post

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

По зиме есть у кого 100? Как-то подозрительно...

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

    да, у меня 100

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

      расскажи же, что там такого?

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

        ну незнаю, вроде никаких подвохов.

        Для начала вычеркиваем те дни, которые лежать хотя бы в одном интервале 2T. Очевидно что эти дни точно войдут в ответ. Пусть их количество — res. Это можно делать как online за O(N log N), так и offline за O(N).

        Теперь посчитаем ДП ff[i] — количество вычеркнутых дней с 1 до N. Тогда для каждого периода наибольшей длины мы сможем узнать сколько не вычеркнутых дней находиться в интервале от 3T до 2T. Запомним максимум. Пусть он равен plus.

        Тогда ответ — res + plus.

        Осталось это аккуратно написать=)

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

The time limit for Q5 seems to be very tight :S I wrote PIE + DP but I still got TLE ...

Does anyone have any idea how to do Q6? I think you use something like KMP, but I have trouble trying to construct the recursion.

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

А тема то была создана мной :)

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

    извиняюсь, что отнял у вас пару единиц вклада, просто я не увидел тему в прямом эфире и решил, что ее нет.