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

Weighted sum problem
Автор P_Nyagolov, 10 лет назад, По-английски

Hello, everybody!

Yesterday I tried to solve this problem on spoj. I spent about three hours on it, but I didn't manage to solve it. In the comments I read that there is a solution in O(n) time complexity. Can you help me, please?

Thanks in advance! :)

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

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

Obviously, for non-negative Ai, Wi = Wi - 1 + 1. Making it smaller wouldn't help anything.

Take the last negative Ai. We can see that the sum of AiWi to its right is . The first term is fixed; the second works as the last element of a modified array A'. If it's negative, Wi = 2; otherwise, we can repeat the same idea on A'.

This leads to a simple implementation with one traversal of the array.

→ Ответить