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

round 6 problem Е
Автор PanZverski, 15 лет назад, По-русски
Кто нибудь знает решение за O(n) ?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
За O(n) задачу надо решать с помощью двух указателей. Т.е. поставить первый на индекс 0, а второй двигать вправо пока условие из задачи верно (попутно, если надо изменяя ответ). Потом сдвинуть первый указатель на 1 вправо и продолжить движение второго. Так далее.

Так для каждой позиции мы найдем максимальный по длине отрезок, который начинается в данной позиции и удовлетворяет свойству с разностью максимума и минимума. Так как каждый указатель двигается только слева направо, то в сумме они пройдут 2· n позиций. То есть если делать проверку для текущего отрезка на выполнимость условия про разность за O(1), то задача будет решена за O(n).

Для того, чтобы проверять условие за O(1) надо на очереди уметь искать минимум (и максимум, но это делается симметрично) за O(1). Для этого очередь моделируется двумя стеками (в книге Шеня есть упражнение - и тогда минимум на очереди это минимум из минимумов двух стеков), а на стеке искать минимум за O(1) очень просто - надо всего лишь класть текущий минимум рядом с элементом.
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо за ответ! действительно, все просто оказалось. я, правда, использовал деки для поиска минимума и максимума.
    странно, то, что я очень часто пользовался подобным приемом для поиска ближайшего меньшего или большего соседа, и никогда не задумывался применить его для поиска min/max в окне.

    кстати, большинство из решений, и по-моему все что были посланы во время контеста использовали для той же цели либо multiset, либо hand-made double heap)
    хотя, по простоте кодирования и длине кода, решение с multiset, конечно, лидирует... а то, что сложность O(N*logN), при данном условии не важно...

    многие даже не запаривались, с перемещением указателей, а просто подбирали длину интервала дихотомией...
    → Ответить