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

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

Прошел первый этап XV Открытого Кубка по программированию. Как решать задачи А, Е, К?

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

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

Авторы, пожалуйста, делайте сэмплы не на "отгребись", а для людей!

Цель сэмпла — в том, чтобы человек не мог сесть писать задачу с неправильным пониманием условия. Сэмпл в задаче I не демонстрирует ровным счётом НИЧЕГО. Пока мы не задали два клара, а Олег не прогнал их в авторском решении (их потом броадкастнули, кстати), понять, что называется одинаковыми подстроками, а что -- разными, было совершенно невозможно.

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

    Ага, мы тоже задавали до бродкаста, нам ответили Read the problem statement.

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

      Приведу переписку с жюри, так как это единственный приходящий мне в голову случай, когда жюри командного соревнования отвечает вопросом на вопрос :)

      
      13 сен 2015, 13:20:56 Important Or Not?
      Distinct strings
      Does distinct in third type of message mean "distinct pairs (y, q) such that string (y, q) contains string (x, p) as a suffix" or "distinct substrings s of a string A such that s contains string (x, p) as a suffix" (in the other words, does distinct occurrences of a same substring counts several times)?
      
      13 сен 2015, 13:36:28
      Aren't (x,p) and the substring of A the same set?
      
      13 сен 2015, 13:46:35 Important Or Not?
      No, they aren't :)
      For string "abacaba" pairs (2, 1) and (2, 5) represent both string "ab". Pairs (2, 1) and (2, 5) are distinct but substrings are the same.
      
      If the quries are:
      1 2 1 (activate first "ab")
      1 2 5 (activate second "ab")
      3 1 1 2 (ask for substrings containing "b" as suffix)
      
      The answer is 2 (if two occurrences of "ab" count) or -1 (if not)?
      
      13 сен 2015, 14:14:13
      -1
      
      13 сен 2015, 14:26:22 Important Or Not?
      Enabling one occurrence and disabling another
      If we activate one occurrence of a substring and deactivate another, is this substring still considered activated or not?
      
      Example:
      A = "abacaba"
      1 2 1 (activate first "ab")
      2 2 5 (deactivate second "ab")
      3 1 1 1 (ask for substring containing "b" as suffix).
      
      The answer is 2 ("ab") or -1 (if "ab" is indeed deactivated by second query)?
      
      13 сен 2015, 14:28:29
      -1
      
      
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать B и M?

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

    M: возьмём и положим все полиномы в мультисет с компаратором, сравнивающим значение полинома A в точке xA и полинома B в точке xB (начинается всё из x = 1), а дальше будем составлять последовательность по условию задачи: забираем из мультисета полином с наименьшим значением и вычисляем, плюсуем его точечку и кладём обратно, и так ещё k - 1 раз.

    В B я придумал какую-то глупость, не знаю, насколько она близка к реальности. Диагонали разного цвета не пересекаются, посчитаем количество клеток каждого цвета под боем, думая о диагоналях, как о строчках (/) и столбцах (\) в прямоугольной матрице, тогда количество клеток под боем можно посчитать по формуле включений-исключений: rows * n + columns * m - rows * columns. Из этого надо ещё вычесть «лишние» клетки, потому что диагонали на самом деле все разной длины.

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

И еще хотел узнать почему ответ gcd(n,k) в задачи G?

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

    Пусть мы циклически сдвинули последовательность 1,2,3..n на k вправо, тогда последовательность примет вид k+1,k+2...n-1,n,1,2,3..k можно убедится что при каждом ходе в раунде мы переходим на к клеток вправо циклически, так мы переходим пока не попадем на перевернутую карту, то есть можно подсчитать, что на каждом раунде убирается lcm(n,k)/k тогда нужно сыграть n/(lcm(n,k)/k) = n*k/lcm(n,k) = gcd(n,k) раундов.

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

A Let's compute answer for vertex v. We can visit an associative vertex u like this:
Firstly go some steps using given edges, after that go using reversed edges.
So Dfs(vertex, isReversed) will work perfect here.
From isReversed = false we can go to isReversed = true, but not in other way.

Code

K, dynamic programming and meet in the middle divide and conquer

Sorry that I am in english.

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

    Can you explain in more details problem K?

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

      K dp(i, j) — first i keys are assigned, and we have covered first j alphabets.

      dp(i, j) = min dp(i-1, k) + cost(k+1, j)
      Let's denote optK(i, j) — optimal k that gives for us minimum.
      We can prove that, optK(i, j) <= optK(i, j + 1)

      let's calculate recursively calc(i, l..r, optKl, optKr).
      Firstly, we can calculate dp(i, mid), then recursively solve for
      calc(i, l..mid, optKl, opt(i, mid)) and calc(i, mid+1..r, opt(i,mid), optKr)).

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

      Also, you can use convex hull optimization. Lets dp(i,j) — first i keys are assigned, and we have covered first j alphabets.

      dp(i, j) = min dp(i — 1, k - 1) + cost(k, j) 
      Lets sum(i,j) = a[i] + .. + a[j].
      dp(i,j) = min(dp(i-1,k-1) + cost(1,j) - cost(1,k-1) - (k - 1) * (sum(1,j) - sum(1,k-1)) 
      dp(i,j) = min(m[k] * sum(1,j) + c[k]) + cost(1,j) . 
      Where m[k] = - (k - 1) and c[k] = dp(i-1,k - 1) - cost(1,k-1) + (k-1) * sum(1,k-1).
      

      Code

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

    K can be done by dp with a convex hull trick.

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

    I would call it "divide and conquer" rather than "meet in the middle".

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

A: Конденсируем граф. Далее с помощью динамики по ориентированному ациклическому графу + битсетами определяем в каждой вершине битсет из её "потомков". Далее динамикой по развёрнутым рёбрам проталкиваем эти битсеты в потомков. Таким образом в битсете каждой вершины список потомков её предков, пройдёмся по ним и прибавим к ответу нужные числа. O(n2)

E: Из условий nk ≤ 105, k ≤ n следует, что k2 ≤ 105. Сортируем всех рабочих по опыту. Пишем динамику за nk2 вида dp[число рассмотренных рабочих][число взятых асистентов]["баланс" между асистентами и шефами ]. Баланс не должен становиться отрицательным.

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

    Можно по-подробнее про А? Мы потратили немало времени на то, чтобы понять, как по набору множеств потомков за O(N^2) получить список пар, которые одновременно находятся хотя бы в одном множестве — не вышло, написали решение, которое описал Madiyar комментом выше.

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

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

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

        Ага, точно. Спасибо!

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

          А: вы тут все извращенцы. Пустим из каждой вершины bfs по обратным рёбрам чтобы найти предков, теперь используем уже готовую очередь чтобы найти всех потомков этих предков. Либо dfs по парам (вершина, вверх/вниз). Из-за того что рёбер мало, сложность одного прохода O(N), по всем вершинам O(N2);

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

            Зачем dfs по парам. dfs из многих вершин тоже можно запускать, просто used не надо чистить.

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

    Вместо баланса можно хранить сколько пар уже взято, это более понятно :)

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

    Мы решали А похожей идеей. Правда граф не конденсировали. Честно пускали дфс из каждой вершины, если в ней еще не были, и за дфс запихивали в битсет(назовем его Cur) все вершины, которые мы прошли в этом дфс. Пройдем по всем единичкам в битсете Cur и к битсетам(у нас для каждой вершины есть битсет вершин, с которыми эта вершина ассоциативна) всех вершин, в которых единички сделаем Or битсета Cur. Понятно, что если мы запустили из этой вершины дфс, из всех вершин, до которых мы добрались, запускать дфс бессмысленно, так как ответ останется таким же. Оценивать это решение не умею, может быть что-то около O(N^2)

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

Какое соответствие задач на украинской 1/8 и сегодня?

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

Как решать H, L?

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

    H — будем считать ожидание времени до конца — величину D[components][v], где components — отсортированный вектор размеров компонент связности (таких всего 627, кстати), и мы стоим в вершине v. Формула пересчета — линейная, но внутри группы с одним components зависимости циклические, поэтому внутри группы будем считать Гауссом. А по components группы состояний образуют ациклический граф, поэтому получается решение а-ля динамика с Гауссом, которая работает за 627 запусков Гаусса.

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

      А много кто знает как эту задачу решать за полином?

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

        Я знаю другой способ, который полиномиальный и использует теорию случайных процессов. Можно понять, что мы фактически генерим случайную величину ξ, которая говорит, сколько нужно случайных ребер добавить в граф, чтобы он стал связным, а потом считаем сумму , где — первый момент, когда блуждая по графу, мы собрали k успехов (фактически, процесс восстановления некоторого случайного процесса). Распределение можно найти из уравнения восстановления, а распределение ξ как-то искалось аналитически (не помню, честно говоря, как).

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

        dp[edges][v]

        Заметим, что все несвязные графы с одинаковым количеством рёбер равновероятны. Дальше всё как у Zlobober, для переходов мы предподсчитали кол-ва связных/несвязных графов с фиксированным кол-вом рёбер, а также суммарное количество мостов в связных графах при фиксированном количестве рёбер.

        Предподсчёт за O(n6), гауссы за O(n5)

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

          У меня очень похоже, а для чего нужно количество мостов?

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

            Чтобы посчитать вероятность закончить игру прямо сейчас.

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

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

Как решать I?

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

    Построим суффиксное дерево. С помощью двоичных подъёмов можно для каждой строки определить вершину, в которую ведёт ребро, в середине которого мы бы оказались если бы искали её в суфф дереве как в боре. Давай в каждой вершине дерева хранить список длин "хороших" подстрок, которые кончаются в ребре, которое ведёт в неё. Выпишем вершины в порядке захода в них. Тогда когда к нам приходит запросов можно рассмотреть два случая:

    1. Ответ лежит на ребре. Находим его.
    2. Иначе вычитаем из k число хороших строк, которые длиннее нашей и лежат на ребре. Задача свелась к k-статистике на подотрезке in[v] + 1, out[v]. Это можно делать с помощью дерева отрезков, храня в каждой вершине ДО сет из длин, которые встречаются на подотрезке и выписывая из каждой вершины с разбиения отрезка первые k чисел.

    Итого решение работает за . При желании можно хитрыми махинациями переписать k-статистику за и решение станет не зависеть от k, то есть, .

    Код: #1zLpMn

    P.S. Видимо, альтернативно можно решать суффиксным массивом. Для этого можно определять лексикографические границы заданной подстроки. Это всё ещё будет k-статистика на отрезке, однако это решение представляется мне громоздким и более сложным в реализации.

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

      Umm can you please translate it into english? I could not quite get it by translator

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

        Sorry for late answer.

        Let's build suffix tree. After that with some kind of sparse table you can find the edge on which [l, r] substring lies in . After that let's in every node of suffix tree keep the set of strings which are important and lie on the edge that leads to this node. Also let's build segment tree on the nodes of suffix tree in the in-order of dfs, so any subtree of some node will be contiguous subsegment. At last, we can answer the queries. Let's consider two cases:

        1. Answer string lies on the edge leading to the node we found with sparse table. We can simply iterate some of such strings and find it.
        2. Answer can also be in the subtree of that node. Then it is some kind of k-th statistics whith updates on the subsegment which is well-known problem and can be solved in which is the case because k is small. Also it can be solved on with some non-trivial technique.

        My code: #1zLpMn

        Sorry for poor English :)

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

          Thanks for the translation, I forgot to update that, I understood the solution looking at your code in previous post. I think you used Suffix Link tree of Suffix Automata, not Suffix Tree, right? Or are they equivalent (don't think so)?

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

    Идейно простое решение (немного не успели на контесте, но в дорешку зашло): возьмём все подстроки из запросов (а из запросов 3 типа — дополнительно подстроки + большой символ в конце), и тупо посортим (хешами, итоговая сортировка за ).

    Поверх посорченного массива сделаем дерево интервалов, которое умеет добавлять элемент за и считать k-ую статистику на отрезке за . Итого получается .

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

Как решать J?

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

    Бин. поиск по ответу. Степени, которые  > 4 очень быстро заканчиваются. Их быстро смерджим и в бин. поиске используем lower_bound. Для остальных, если они есть, можно посчитать число элементов оттуда, меньше середины отрезка в бин. поиске с помощью формулы включений-исключений.

    Код: #aWIhkW

    P.S. Теоретически должно заходить и когда мерджим последовательности с  > 3, но на деле это получает TL. По крайней мере у меня.

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

      Или можно ничего не мерджить, а посчитать количество членов искомой последовательности, которые не превосходят x. Для этого нужно воспользоваться формулой включения-исключения. Конечно, если ее считать напрямую, то это работает за экспоненту. Но степеней больше 60-ти для чисел, начиная с двойки, "не бывает" из-за ограничений задачи, а единичку вообще можно отдельно всегда посчитать. Для того, чтобы посчитать "правильные" коэффициенты для степеней от 1 до 60, нужно 1) считать их только для степеней, кратных хотя бы одной степени из инпута 2) рассмотреть их все по возрастанию, вычислить coeffs[i] — сколько раз мы уже "посчитали" i-ю степень, и затем "добавить" ее с коэффициентом (1 - coeffs[i]). Вот код.

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

Когда-нибудь чудо случится, и рандом в Яндекс.Контесте исчезнет. Не сегодня. Техника "пошли одно и то же решение 3-4 раза, если не проходит, и прогрей Яндекс" работает до сих пор.

Сабмитим на контесте

Сабмитим в дорешечку

Другая задачка без богомерзской джавы

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

Господа из ННГУ, которые сдают H до заморозки с плюса, КАК?

Я вот начиная с 3:00 полтора часа смотрел в AC-код и пытался понять, почему же он не работает на втором сэмпле. На клар нам ответили неправильно.

Вряд ли с этим что-то сделают, но осадочек неприятный.

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

    Я тоже минут 40 смотрел. За это время успел посчитать на бумажке ответ, и он у меня сошелся с моим решением. Ну я забил и решил так отправить.

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

      Мы тоже посчитали. Посабмитили минимум из всех вершин.

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

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

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

          Изначально в условии сказано "arbitrary" :)

          Ну там есть слова типа "His goal is ...". Так что логично было бы ему хотеть побыстрее)

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

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

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

Расскажите, пожалуйста, как решать L?

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

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

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

Кто такой Е.В. Панкратьев?