P_Nyagolov's blog

Weighted sum problem
By P_Nyagolov, 10 years ago, In English

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! :)

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply