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

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

Всем доброго времени суток. 17 января в 15:00 мск пройдет второй отборочный этап Зимней школы по программированию. Более подробно о школе можно почитать на официальном сайте.

Предлагаю обсудить задачи после окончания контеста.

UPD: Контест завершен!

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

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

На каком сайте проводится отбор?

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

Сколько длится контест? Не смог найти на сайте.

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

Сколько всего участников пройдут со второго отборочного тура ?

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

Как решать задачу D — Страна волшебников ???

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

    Переберем все пары городов. Далее найдем город x, лежащий на середине пути между текущими рассматриваемыми городами v и u. Расстояние h между городами можно узнать с помощью LCA, город, лежащий посередине между v и u, можно найти двоичным подъемом от более нижнего из городов u, v на h / 2.

    Теперь рассмотрим два случая: когда расстояния h четно, и когда h нечетно. В первом случае для того, чтобы данная пара городов являлась "честной" необходимым и достаточным условием является выполненное равенство sz[x] == n — sz[anc[x]], где sz[v] — это размер поддерева с корнем v, anc[x] — предок вершины x. Аналогично для нечетного h необходимо проверить равенство sz[x] == n — sz[x]. Осталось аккуратно рассмотреть случай, когда h[v] = h[u]. В таком случае пара городов является честной, если sz[child[x][v]] == sz[child[x][u]], где child[x][y] — это непосредственный потомок вершины x в поддереве, содержащее вершину y.

    Асимптотика O(N * N * logN).

    Код: http://pastebin.com/X4WpB33W

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

      Есть решение за O(N ^ 2).

      Подвесим дерево за вершину v, она будет являться первой вершиной.

      Теперь если идти в порядке обхода DFS от вершины v и поддерживать вершины пути, то можно просто найти среднюю вершину пути.

      А дальше почти все тоже самое что описал NedoL

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

Как решать E?

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

    Находим сжатую строку для данной. Дальше решаем для неё. Пусть у нас k строк s длины n. Для первых двух строк посчитаем префикс-функцию. Дальше пойдут значения n + 1, n + 2,.., (k — 1) * n — 1, (k — 1) * n. Строгого доказательства этого факта у меня нет.

    http://pastebin.com/e6C6z8GA

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

Объясните мне B, пожалуйста.

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

    рассмотрим текущую страницу: найдем для нее максимальный подотрезок 5рок и сравним его с ответом, потом найдем наибольший префикс и суффикс, ans = max(ans, prefSuffix + prefix) запомним суффикс и перейдем к следующей странице. код

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

      Если честно, то я не понял для чего искать префикс и суффикс. Можешь написать в лс поподробнее?

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

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

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

    Воспользуемся бинпоиском по ответу Для данного значения k будем за O(N) проверять, можно ли построить последовательность пятёрок длины k. Для этого заведём счётчик подряд идущих пятёрок cur, счётчик пятёрок с учётом стертой двойки cur1 и флаг, поднимая который мы говорим, что двойка уже взята. Соотв. Если флаг поднят и встретилась двойка, обнуляем все Если флаг опущен, поднимаем, обновляя cur. При переходе в следующий блок опускаем флаг. Всё. Хотя я сейчас сам не понимаю, зачем нам cur :D

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

почему не заходило такое решение на D: переберем все пары вершин, для каждой из них найдем LCA, если одна из них LCA, то для нее количество вершин до, которых расстояние строго меньше, чем до другой равно n — кол-во сыновей второй вершины — расстояние между этими вершинами, иначе ответ для вершины, расстояние от которой до LCA больше, равен кол-ву сыновей у предка этой вершины, до которого ее расстояние меньше, чем от второй вершины, а второй соответсвенно n — ответ первой. код

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

    "если одна из них LCA, то для нее количество вершин до, которых расстояние строго меньше, чем до другой равно n — кол-во сыновей второй вершины — расстояние между этими вершинами"

    Потому что есть вершины, лежащие между текущей парой городов v и u (lca(v, u) = v), которые находятся ближе к v, чем к u.

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

Можно где-нибудь дорешать эти задачи?

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

Как решалась задача F (портал 2D)?

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

    Используя Алгоритм Дейкреста.

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

    Я могу только предположить, так как я ее не сдал.

    Пустим очередь с тремя параметрами x, y — положение клетки и z — направление.

    Переходы будут двух типов:

    1) по направлению(если клетка не проходима, то не будем делать переход)

    2) мы не можем пойти по направлению, т.к. впереди не проходимая клетка, но в ней можно открыть портал. Посмотрим на свой путь от последнего прохода в портал, он будет от первой непроходимой клетки снизу до верхней. Мы можем перебрать эту клетку. Далее мы можем перейти либо в первую левую непроходимую клетку, либо в правую. (я рассмотрел случай когда наше направление up, для остальных случаев почти аналогично)

    P.S: Это всего лишь мои мысли, может оказаться что это неправильно.

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

      Это почти правда, но иногда надо возвращаться не до препятствия, а до стартовой клетки. Еще иногда надо стрелять назад (не только влево и вправо).

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

    Ключевое соображение: мы можем считать, что один из порталов всегда впереди нас. Пусть мы находимся в клетке (x, y) и летим в сторону d (одну из четырех). Тогда мы можем либо пролететь на клетку вперед, либо выстрелить порталом в одну из трех оставшихся сторон, после чего имеет смысл лететь только вперед, пока не пролетим через этот портал. Получаем взвешенный граф на O(hw) вершинах, ищем в нем путь Дейкстрой.

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

А где можно посмотреть таблицу результатов?

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

Как решить А?

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

    Минимум камней:

    Расположим в левом верхнем и нижнем правом углу min(a, b) и min(c, d) камней соответственно. Затем расположим в левом нижнем и верхнем правом углах min(b — min(a, b), d — min(c, d)) и min(a — min(a, b), c — min(c, d)) камней соответственно. Далее доложим в середины сторон камни так, чтобы суммарно получилось a, b, c, d камней на каждой стороне соответственно.

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

    Максимум камней:

    Ситуация противоположна — положим по углам минимально возможное число камней, а именно 0. Далее заполним середины сторон.

    Код: http://pastebin.com/1DMW57Ed