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