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

Solving "Another Problem On Strings — codeforces" using two pointers

Автор codolove, история, 9 лет назад, По-английски

I was trying to solve Another Problem On Strings using two pointers since it was mentioned in its tags but I am not getting an idea of it. I have solved it by using hashing and binary search by considering the prefix sum. It will be helpful if one can give some idea of approaching it with two pointers.

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Let

  • pnt1[i] = maximum j which contains strictly lesser than k+1 "1" in interval [i, j-1].
  • pnt2[i] = maximum j which contains strictly lesser than k "1" in interval [i, j-1].

calculating both are a trivial two pointer exercises.

Now answer is Sum(pnt1[i] — pnt2[i]) for all i = [0, len-1].

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

How to solve it by dp? It has 'dp' tag too.

→ Ответить