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

Автор purplesyringa, история, 3 года назад, По-русски

Традиционное обсуждение (или осуждение -- кому как) регионального этапа ВсОШ 2022 года. Кажется, к 15 часам МСК он уже должен был закончиться везде.

Традиционная сборная таблица результатов: https://reg.prog.cf/. Пока данные берутся только из опроса (заполните!) и нескольких официальных таблиц, когда появятся остальные -- добавится информация оттуда.

Отдельная просьба организаторам и другим людям с доступом к результатам своего региона: пожалуйста, перешлите их @prog_cf_bot.

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

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

Ура, написал худший регион

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

Кажется, что очень просто.

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

Такое чувство, будто градация сложности несколько более ломаная, нежели раньше. P.S. в чем идея в D?

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

    У кого-то в D алгоритм Манакера, у кого-то хеши + бинпоиск. В целом примерно то же самое, что и в задаче поиска палиндрома максимальной длины. Могу поподробнее рассказать чуть позже, если будет нужно и еще не будет разбора

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

      Я получил 46 баллов за алгоритм Манакера, не дадите подсказку как его использовать, чтобы полный балл получить?

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

        Кажется, я не правильно кого-то понял. Видимо, на 100 Манакера не получается загнать.

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

          Можете дать подсказку о решении, которое можно загнать на 100? Я смог узнать, что можно сделать палиндром из подстроки A, только если есть подстрока B, где разность b[i]-b[n-i+1] == a[n-i+1]-a[i], но я так и не нашёл ни как искать такие штуки быстро, ни как быстро их строить :/

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

            Пусть у тебя есть массивы x_1, x_2, ..., x_n и у_1, y_2, ..., y_n. Тогда заметим, что хэш массива x_1 — y_1, x_2 — y_2, ..., x_n — y_n равен разности хэшей массивов x и y. Тогда если есть подотрезок в a или b, то можно его представить как разность хэшей его левой и правой половины. Сделаем бинпоиск по ответу (чётные и нечётные отдельно, получится 2 бинпоиска), внутри бинпоиска считаем такие разностные хэши всех подмассивов b заданной длины, затем проходимся по подмассивам a и проверяем их на наличие в b (set или unordered_set).

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

            Написали ж сразу, что хеши (см хеши со строками на e-maxx, если не знакомы).

            Задачу можно интерпретировать как поиск максимального k такого, что можно взять подстроки длины k из A и B дающие в сумме палиндром.

            Если нужна подсказка, а не решение, то дальше смотреть осторожно.

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

              Для того, чтобы не было коллизий, можно, кстати, просто использовать два хеша или большой хеш (у меня порядка $$$10^{13}$$$ зашел).

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

      Подзадачу про поиск палиндрома наибольшей длины можно было решать в тупую за квадрат, спасибо тестам

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

Таблица результатов для регионов, которые писали на Codeforces:

https://codeforces.me/spectator/ranklist/01ee6bf8e561980c5201d4b494ad5e8d

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

А есть дорешка?

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

Предварительные результаты первого тура на Яндекс.Контесте: https://contest.yandex.ru/roiarchive/results/

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

Результаты Липецкой области, похоже, тут: https://ejudge.strategy48.ru/ejudge-new-standings/regional/regional-2022-day1-wonaumokicasakoome

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

Есть у кого-нибудь мысли по B? У меня так и не получилось придумать ничего стоящего. 10e7 платформ. Я даже не уверен, что алгоритм отработает за секунду при O(n).

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

    O(n) на C++ даже при n <= 1e8 заходит.

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

      Это радует) У тебя есть какие-либо мысли по задаче?

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

        Я не решил последнюю подзадачу, но мысль есть. Там m = min(n, 1e5), Так что, наверное, нужно задачу решить для Первых m элементов, как в подзадаче (f = 1, n <= 1e5, на 20 баллов) за O(nlogn), а потом эти подсчеты использовать для решения последней подзадачи. Я подумал, что может старт начинается с этой же платформы, с которой найдет наш алгоритм для первых m. Но это не так, я пробовал.

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

          В полном решении при f = 2 я просто восстанавливаю массив d по формулам, так что я даже не знаю зачем это сделано, может быть для более простого создания тестов.

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

            Это сделано что бы отсечь решения за nlogn. Отсечь n от nlogn с обычным вводом не представляется возможным, потому-что сам ввод занимает примерно столько же времени что и nlogn алгоритм

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

        Напиши решение за O(n^2) и посмотри для каждого элемента, сколько нам нужно, если начать с него. Дальше посмотри на получившийся массив с конца и вроде становится очевидно как писать за O(n).

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

    Там максимум на префиксе и cуффиксе. Вот формула подсчета: dp1[i] = max(dp1[i-1]+1, d[i-1] — n +1) , dp2 = max(dp2[i+1]-1, d[i+1]-1). Ответ: Минимум по всем max(dp1[i], dp2[i+1]).

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

      Можно проще, записать в массив d все расстояния из входных данных, и обойти этот массив с конца в начало по формуле d[i] = max(d[i], d[i+1]-1). Потом найти минимум среди этих значений, это и есть ответ. Зашло на 100

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

        dp[i] = max(d[i], dp[i+1]-1), почему нигде не пишут про это решение?

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

А второй день легче будет или такой же? В прошлом году второй полегче был.

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

Предварительные результаты второго тура на Яндекс.Контесте: https://contest.yandex.ru/roiarchive/results/

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

Сводная таблица по двум турам для регионов, принимавших участие на codeforces: https://codeforces.me/spectator/ranklist/6ab02a1660b6b40e3baae60b689299fb

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

Как же я люблю $$$O(nk^2log)$$$ в $$$D$$$ на сто баллов)

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

Публичный контест на Яндекс.Контесте: