RSRECIPE - Editorial

editorial
feb12
medium
rsrecipe

#1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EXPLANATION

Let A 1 , A 2 , …, A[N] be an array that we should restore. Consider the sequence of partial sums S[k]=A1+…+A[k], 0<=k<=N. In particular, S[0]=0. Clearly, conditions on array A[] mean that

S[Yi] - S[Xi - 1] = Zi, 1 <= i <= M. & nbsp; (*)

Let’s build a weighted graph on numbers 0, 1, …, N, where for each triple (Xi, Yi, Zi) from the input we add edges from Xi- 1 to Yi with weight Zi and from Yi to Xi-1 with weight -Zi. We consider this graph as not-oriented when talk about connectivity but weights of edges depends on direction. Then if in some connected component of this graph we set value S[v] for some vertex v, all other values of S[] in this component can be restored by simple DFS using equalities (*). Namely, if we are in some vertex v and the value S[v] is known then for each neighbor u of v the value S must be equal to S[v]+e[v] where e[v] is the weight of the edge from u to v. So if it is not known we set S to this value and run DFS for it. Otherwise if it is known but not equal to this value the recipe can’t be restored. This leads to a simple algorithm for restoring array S[]. Then array A**[]** can be restored by formulas A=S-S[i-1], 1<=i<=N**. The total complexity is O(N+M).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.