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

Помогите с задачей
Автор abdukodir, 12 лет назад, По-русски

Здравствуйте все , даже JKeeJ1e30!

Уже пятый день не могу справиться с вот этой задачей. Пишу решение за O(N^2*logN) , не проходит по времени. Помогите кто как может.

Спасибо.

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

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

А по-моему смешно. Большинство конечно заступится за беднягу. Но все-таки поинтереснее, чем просто так попросить о помощи у сообщества. Молодец, неплохо придумал.

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

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

    Благодарю за помощь и оптимистическое восприятие моих слов насчёт JKeeJ1e30!

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

    К сожалению, такое решение ловит МЛ (64 мб) на больших тестах( В вершине дерева вроде как ничего лишнего.

    struct node
{
   node *pointer[2];
   int count;
   bool used;
};

    Не подскажете, как можно соптимизировать, или может у меня ошибка какая-то? http://ideone.com/TGMaxI

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

      А если заменить node *pointer[2]; на node* zero, one;?

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

      Такое решение можно пропихнуть. Моя реализация бора не на указателях, а на массивах (то есть ссылка — это просто индекс в массиве). Так как количество вершин — это величина порядка N^2, то можно юзать bitset место bool used[], что существенно лучше. (прошло за 65060 KB из 65536 KB)

      P.S. А если по-хорошему, то такая задача, только с более жесткими ограничениями, была в Харькове 2013. Задача М. Решается с помощью суффиксного дерева, можете посмотреть разбор.

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

        Спасибо.

        Увы, на зимней школе да и после суффиксное дерево я так и не осилил, поэтому ту задачу и не вспомнил =)

        А эту задачу пришлось решить за .

        Решение, кстати, получилось довольно небольшим и хорошим по памяти и времени (270мс, 1.2мб). А именно:

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

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

          Наверное, можно было вместо сортировки использовать функцию nth_element со своим компаратором и тогда решение работало бы за квадрат (в среднем).

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

            Но у меня же в том массиве хранятся не все возможные подстроки, а лишь n штук, такие, что ихние префиксы формируют все подстроки. А уже при проходе после сортировки, я прибавляю все подстроки, которые находяться между і-той и i+1-ой в моём массиве. То-есть до этого прохода я даже не знаю, какой по счёту элемент из массива мне нужен.

            Или это можно как-то обтанцевать в компараторе?

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

              Если написать nth_element полностью руками, то можно :)

              → Ответить