Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have an array $A[1..N]$ with unknown values and a set of intervals $[L_i, R_i]$. For each interval we know sum $S_i$ of values in the array $A$ in the given range $[L_i, R_i]$.

So the question is to recover possible arrangement of numbers in the array $A$ without contradiction to the sums on the intervals.

I am wondering about solution which envolves usage of partial sums. Cause there is a solution for the task, when we have parity information instead of sums on the intervals.

share|improve this question
add comment

1 Answer

This looks like just a system of linear equations in $N$ variables, so I'm not exactly sure what you're looking for, but here's a quick algorithm:

Let $\sigma[k]$ be the partial sum $A[1] + \cdots + A[k]$, and let $\sigma[0] = 0$. Then each interval $[L_i, R_i]$ gives the constraint $\sigma[R_i] - \sigma[L_i -1] = S_i$. So now we have a list of equations.

Working backwards from $k = N$ down to $k=1$, if in our list there are two or more equations of the form $\sigma[k] - \sigma[m] = s$, then we will rewrite the equations with small $m$ by cutting out the overlapping parts. For example, if we have $$\begin{align} \sigma[10] - \sigma[7] &= 4000 \\ \sigma[10] - \sigma[5] &= 5000\\ \sigma[10] - \sigma[4] &= 9000 \end{align}$$ then we would replace the bottom two with $$\begin{align} \sigma[7] - \sigma[5] &= 5000 - 4000 = 1000\\ \sigma[5] - \sigma[4] &= 9000 - 5000 = 4000 \end{align}$$ If we ever have two equations with the same left-hand-side expression $\sigma[k] - \sigma[m]$ but different right-hand-side values, then of course the constraints are unsatisfiable.

After that, we just work forwards from $A[1]$ to $A[N]$. If when we get to $A[k]$ there is no equation in our list of the form $\sigma[k] - \sigma[m] = s$, then we just let $A[k] = 0$. Otherwise, there is exactly one equation of the form $\sigma[k] - \sigma[m] = s$, and since the values of $A[1]$ through $A[k-1]$ are determined at this point, there exists exactly one value of $A[k]$ (namely, $s + \sigma[m] - \sigma[k-1]$) that will make the equation $\sigma[k] - \sigma[m] = s$ true. In this way assign all the $A[N]$.

share|improve this answer
    
That would be great, if we have overlapping intervals only in {start,end}points. However, there is a case such as: [1,5] and [3, 10]. What about this situation? –  Andrei Feb 5 '12 at 9:13
    
Oops, I made a small error; it's been corrected. Suppose we have $A[1] + \cdots + A[5] = 60$ and $A[3] + \cdots + A[10] = 220$. Then the algorithm gives $A[1] = A[2] = A[3] = A[4] = 0$; $A[5] = 60$; $A[6] = A[7] = A[8] = A[9] = 0$; $A[10] = 220 - 60 = 160$. –  JohnJamesSmith Feb 6 '12 at 2:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.