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

Автор vlade087, 11 лет назад, По-английски

Hello anybody can say me what mean when the problem have a tag two pointers. What mean this approach?

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

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

Look here

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

One of the recent problems involving two pointers is problem I:Pirate Chest from ICPC world finals 2013

This problem reduces to one-dimensional case: in integer array, for each element you want to find element that is lower than current on the left and right sides.

For every element you keep left and right positions for the element which is less than this element. (initially set to itselft). Iterate over descendant sorted array and update your info about pointers.

The problem's time limit pretty large. But involving some other NlogN approaches (such as fenwick tree) gives TL. By pointers you achieve lower constant.