Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

TL 2004 год
Автор skrydg, 10 лет назад, По-русски

Решаю задачку 2004 года с ограничениями MAXK <= 2000 MAXN <= 20000

Умею решать её за O( MAXK * MAXN )

Зашла бы такая асимптотика в 2004? И умеете ли вы ее решать быстрее?

Задача IOI 2004 Гермес. https://yadi.sk/i/oF7CX1tEaSsSX

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

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

Зашла бы такая асимптотика в 2004?

Глубоко сомневаюсь.

Задача же совсем халявно решается за O(N + MAXK), либо за . Идея такая: возьмем "четвертьплоскость" с левым нижним углом (X;Y). Если мы сможем разместить нашу "четвертьплоскость" так, чтобы строго внутри нее не было ни одной точки, то это даст нам ответ X + Y. Ну так мы можем двигать ее "лесенкой" справа налево, снизу вверх (ну или наоборот).

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

Если речь о динамике по состояниям (x_i:?) и (?:y_i) с 80М операций с последовательным обращением к памяти — да, в 2004 зашла бы за секунду.

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

Нагуглил авторское решение за n^2.

Расстроился :(

Ужасно, думаю надо решить за что то быстрое n log n или n sqrt(n).

А тут решение за квадрат. Ужасно.

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

Нет, не могу

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

Казалось бы, не сильно сложно улучшить решение до O(n*log(min(n, MAXK))) с помощью дерева отрезков.

→ Ответить