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

Timus — Later is better than never contest
Автор Timur_Sitdikov, история, 5 лет назад, перевод, По-русски

Контест на Тимусе закончился. Как решать D и J?

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

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

Как нормально решать G? А то я какой-то дичью с битсетами и отсечениями загнал. И по B у меня решение с какой-то подозрительной асимпотиткой (что-то в духе $$$tl^3/k*log_k{n}$$$), подозреваю, что есть проще и изящнее.

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

    В G каждая печать красит не более 100 уже покрашенных клеток (иначе можно завершиться), а остальных не более n * m суммарно, так что можно просто проэмулировать.

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

    У меня в В решение с такой же подозрительной асимптотикой. На самом деле не исключено, что оно валится каким-нибудь макстестом, где $$$100$$$ раз задается $$$k=2$$$.

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

Может ли кто-нибудь дать подсказку по А 2128. Пасьянсу Рубины? Это задачка не совсем пока моего уровня, по всей видимости, но никак из головы не могу выбросить её. Прямолинейное решение, конечно же, не зашло.

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

    Надо для каждой стопки запустить рекурсивное удаление: если можно удалить карту с вершины, то удаляем и запускаемся от следующей карты в стопке и от следующей карты той же масти (если она на вершине какой-то стопки).

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

Я уверен, что решение задачи D использует суффиксное дерево всех строк, а также объединения множеств вдоль него.

→ Ответить