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

Автор LaKsHiTh_, история, 4 года назад, По-английски

This is in reference to the question Rice hub in IOI 2011. I'll try to state specifically what i need so you don't have to go through the whole pdf.

when an array of points (sorted in non decreasing order), a starting index s and end index t of the segment is given calculate the absolute difference between each point in the segment s t and the mid point ( (s+t)/2 ).

i.e array: 1, 3, 5, 8, 11, 15

s: 1

t: 5

Here we have to consider the segment 3, 5, 8, 11, 15

Answer = |8-3| + |8-5| + |8-8| + |8-11| + |8-15| = 5 + 3 + 0 + 3 + 7 = 18

I want to do this in constant time. The solution suggests a way using prefix sum but i can't understand it.

Answer = (p - s)*arr[p] - (T[p] - T[s]) + (T[t + 1] - T[p +1]) - (t - p)*arr[p]

where s =  starting index, t = ending index, p = (s + t)/2, T is the prefix sum array

Can you please describe the above equation so that i can understand it.

I wrote the above equation because i can't exactly copy paste as it's with Latex. Check this in case it's not clear
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

From all indices in the range s -> (p — 1) the equation (arr[p] — arr[ind]) will be positive, so you can represent that as # of elements in that range * arr[p] — sum of all elements from s -> p — 1. The same logic is applied from indices (p + 1) -> s except the difference will be negative, so you do sum of the elements in that range — # elements in that range * arr[p]

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

    Thank you.

    Now i understand. It's like i wrote (arr[p]-arr[i]) for every element and then simplified it. Got the common term arr[p] outside and got sum s of arr[i] by the prefix sum. :)