1
$\begingroup$

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.

1 Answers 1

1

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]$.

  • 0
    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$.2012-02-06