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

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

4 августа стартовала традиционная летняя серия индивидуальных соревнований SnarkNews Summer Series-2014. Соревнования проводятся на системе Яндекс.Контест, также доступна страница проекта на Яндекс.Контест. Опубликовано расписание серии.

Участвовать в серии могут все, кто имеет логин на Яндексе. Соответственно, для регистрации нужно зарегистрироваться на Яндексе и войти хотя бы в один из раундов серии. логин и пароль от почты и являются логином и паролем на вход в систему Яндекс.Контест.

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

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

чуть-чуть по-раньше бы об этом узнать.

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

    Самое логичное время для объявления — за пол-часа до конца первого раунда.

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

      Мне почему-то показалось, что некоторые участники начали решать после окончания. Или я как-то неправильно понял обозначения в таблице, и если в участника в 15:30 под никнеймом пишет 1:10, то он начал не в 14:20:) Или в часовых поясах запутался, не знаю...

      По задачах: какая оптимальная асимптотика в D? Наивная динамика за N^4 проходит со временем 0.1 или даже быстрее. Если переписать ее в другую сторону и прикрутить частичные суммы, то вроде бы получим решение за N^3. Можно ли еще быстрее? И можно ли решить С за чистый квадрат? У некоторых, говорят, квадрат на логарифм получал TL.

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

        Если считать, что int'ы можно сортировать за линию, то С можно решать за квадрат:)

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

          А если у нас квантовый компьютер, то все вообще круто)

          Если длины отрезков уже отсортированы, то каждый раз при просмотре новой группы отрезков нам нужно уметь брать максимум по всем предыдущим ребрам вершины, можно эти максимумы хранить отдельно, это понятно) Я думал — вдруг надо как-то вообще с другой стороны к задаче подойти.

          Еще я понял, что все же не умею решать D за куб:)

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

            У меня решение в D за O(N^3*K) — это, по-твоему, куб или 4 степень? Интересно, зачем такое маленькое К в задаче?

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

              Как решать с такой асимптотикой?

              У меня динамика какой отрезок нужно решить — сколько шариков тащим с префикса и какой у них цвет, и внутри я перебираю, какую часть отрезка порешать независимо от префикса — а к другой части "протаскиваю" то, что осталось от префикса. Получается вообще N^3*K*C, где С — число различных цветов.

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

                Динамика — сколько стоит удалить отрезок, если к нему слева добавить еще Х (X < K) шариков такого же цвета, как и первый шар. Пересчет — смотрим, как в конце концов удалится первый шар. Либо его удалим первым ходом, либо вместе с каким-то шаром такого же цвета из отрезка (переберем его). Во втором случае нам точно нужно вначале удалить все шары, которые между этими двумя, а потом переходим к задаче для меньшего отрезка, когда есть (Х + 1) шар такого же цвета, как шар в начале отрезка.

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

          Как решать С? Опишите пожалуйста)

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

            Состояние можно однозначно определить последней парой вершин, которые мы посетили. Одна из них определяет, откуда мы можем ходить, другая — какое у нас сейчас ограничение на длину хода. Отсюда получаем очевидное решение за N^3 — отсортировать все отрезки по длине, решать от более длинных к более коротким, для каждого отрезка перебирать всех валидных соседей, с которых мы могли на него перейти.

            Чтобы получить из этого N^2*log(N), вместо перебора предыдущих отрезков по одному, будем вытаскивать каким-нибудь Фенвиком максимум среди всех вариантов, у которых длина не меньше необходимой. Если заметить, что нас каждый раз интересует максимум среди всех рассмотренных соседей, за исключением соседей с такой же длиной, то можно вместо Фенвика банально хранить максимум для каждой из точек. Только тогда нужно добавлять отрезки группами (сначала добавляем все отрезки одной длины, потом обновляем максимумы), чтобы не получилось пары соседних переходов с одинаковой длиной — например, (0,0)->(1,0)->(2,0).

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

        Я еще это не писал, но кажется, что это верно. Если мы можем пройти с одной точки в другую, то проведем ребро между ними (ориентированное). Найдем все компоненты сильной связности. Теперь у нас есть ациклический ориентированный граф. В таком графе можно искать путь максимальной длины за проход ДП-шкой. Вроде все :)

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

          Проще: посортируем ребра по уменьшению длины + ДП-шка.

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

          А когда нельзя из точки пройти в другую?

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

            Если dist(0,0,A.x,A.y) <= dist(A.x,A.y,B.x,B.y), тогда нельзя пройти с точки А в B. Вроде так.

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

              Следующий ход можно сделать только если dist(B, C) < dist(A, B). Кажется, ты не так понял условие.

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

                Да, сорри :) Нужно думать новое решение.

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

          У тебя "точка" — это точка из входных данных, или пара точек? В первом случае нельзя определить, можно ли сделать ход (мы не знаем, какая была длина последнего перехода), во втором — в графе динамики будет N^4 ребер.

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

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

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

    Проверьте, ссылка на результаты есть на snss2014.snarknews.info

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

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

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

Как получить доступ к английским условиям? На сайте написано, что условия есть и на анлгийском, но если в правом-верхнем углу поменять флажок, то меняется язык интерфейса, а условия те же.

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

А как B решалась?

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

    Я делал так. Пусть расстановка тарифов существует, обозначим di кратчайшее расстояние от истока до i'ой вершины. Заметим, что для любой дуги uv верно dv ≤ du + 2 и dv ≥ du + 1. Заметим, что эти условия на di — ещё и достаточные (при условии, что di — целые). Преобразовав второе условие в du ≤ dv - 1, получаем линейную программу для кратчайших путей следующего графа: в исходном графе каждой дуге делаем стоимость 2 и добавляем обратную дугу веса -1.

    Осталось поискать в полученном графе отрицательный цикл (или, если его нет, кратчайшие расстояния от истока). Ограничения несколько страшные для Форда-Беллмана, но он, как ни странно, заходит. Возможно, для графа такой специальной структуры можно и без ФБ сделать.

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

    nvm

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

Чего-то никто не спрашивает про задачи с новых раундов... Как решается с третьего раунда задача F?

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

    Согласно условию, необходимо найти ближайшее к Е число Х, которое дает указанные остатки по модулям 1, 2,..., n. Найдем значение этого числа Х по модулю LCM(1,...n)=T; пускай это значение Q. Далее среди всех чисел вида pT+Q выберем лучшее — достаточно рассмотреть только соседей Е с каждой стороны.

    Чтобы найти Q, можно использовать какой-нибудь алгоритм Гарнера, но ограничения позволяют писать почти любые переборы:)

    Обидно профукать победу в раунде, написав if (ans==0)ans+=res; вместо if (ans==0)ans+=rl;

    У меня вопрос по В из раунда 2 — какой там максимально возможный ответ? У меня получилось что-то далеко за пределами 64битного типа, но я не подумал о int128, длинку писать тоже не стал, а отправил в открытую с обычными long long. Тесты убогие?:) Я сейчас в очередной раз перечитал условие, никаких ограничений вида гарантируется, что ответ... не нашел.

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

Как решать D со второго раунда?

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

    Заметим, что хотя бы один квадрат будет содержать одну из следующих пар точек: (самая нижняя левая, самая левая нижняя), (самая нижняя правая, самая правая нижняя), (самая правая верхняя, самая верхняя правая), (самая левая верхняя, самая верхняя левая). Решим для первого случая, а остальные сводятся к нему путем отражения всех точек относительно вертикальной и/или горизонтальной оси.

    Мы решили, что один квадрат будет содержать самую нижнюю левую и левую нижнюю точки, значит мы однозначно можем определить позицию его левого нижнего угла. Для удобства перенесем эту позицию в начало координат. Теперь, если сторона этого квадрата будет равна S, то в него попадут все точки, у которых max(x, y) <= S. Отсортируем точки по max(x, y) и будем перебирать их по убыванию этой величины. Пусть мы рассматриваем какую-то точку, тогда все, которые идут в порядке сортировки раньше нее, точно попадут в квадрат, при условии что текущая точка лежит на его стороне. Следовательно, нам нужно найти наименьший квадрат, который покрывает остальные точки, после чего попробовать обновить ответ. Ну а этот второй квадрат ищется просто: его сторона равна max(X_max — X_min, Y_max — Y_min), где X_min — наименьшая X координата точки, которая не попала в наш квадрат (т.е. лежит в порядке сортировки после текущей точки), и т.д. Ясно, что поскольку мы перебираем точки по убыванию max(X, Y), то как только мы рассмотрели какую-то точку, мы можем обновить X_min, X_max, Y_min, Y_max при помощи ее координат, т.е. по сути мы будем на ходу поддерживать эти величины и за О(1) находить площадь наименьшего квадрата, в который попали все "остальные" точки. Сложность O(NlogN).

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

А как присуждаются баллы, когда место делится? В лексикографическом порядке по хэндлу?

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

    Там же скорее всего с точностью до секунды считается (и судя по таблице, округляется round'ом: у вас 0:58 + 0:08 — D = 56, у azizkhan.almakhan — 0:58 + 0:07 — D = 56).

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

как решать c и f из последнего раунда ?

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

    F — если мы зафиксируем длины строк из ответа, то можно проверить, что такие длины могут быть за O(|T|) хешами. Чтобы понять, какие длины x, y нам подходят, решим уравнение ax + by = |H| в целых числах; решений, где x, y ≥ 0 приблизительно , то есть их можно просто все перебрать, и работать все будет за .

    Точнее, решений не , а , но время работы такое же получается.