USACO

USACO 2022 December Contest, Silver

Problem 3. Range Reconstruction

Contest has ended.

Log in to allow submissions in analysis mode

Bessie has an array $a_1, \ldots, a_N$ , where $1 \leq N \leq 300$ and $0 \leq a_i \leq 10^9$ for all $i$ . She won't tell you $a$ itself, but she will tell you the range of each subarray of $a$ . That is, for each pair of indices $i \leq j$ , Bessie tells you $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$ . Given these values of $r$ , please construct an array that could have been Bessie's original array. The values in your array should be in the range $[-10^9, 10^9]$ .

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains

$N$ .

Another $N$ lines follow. The $i$ th of these lines contains the integers $r_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}$ .

It is guaranteed that there is some array $a$ with values in the range $[0, 10^9]$ such that for all $i \leq j$ , $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Output one line containing

$N$ integers

$b_1, b_2, \ldots, b_N$ in the range

$[-10^9, 10^9]$ representing your array. They must satisfy

$r_{i, j} = \max b[i\ldots j] - \min b[i\ldots j]$ for all

$i \leq j$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

1 3 2

For example, $r_{1, 3} = \max a[1\ldots 3] - \min a[1\ldots 3] = 3 - 1 = 2$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

0 1 1

This example satisfies the constraints for subtask 1.

SAMPLE INPUT:

SAMPLE OUTPUT:

1 2 3 2

This example satisfies the constraints for subtask 2.

SAMPLE INPUT:

SAMPLE OUTPUT:

1 2 2 0

SCORING:

Test 5 satisfies $r_{1,N} \leq 1$ .
Tests 6-8 satisfy $r_{i,i+1} = 1$ for all $1 \leq i < N$ .
Tests 9-14 satisfy no additional constraints.

Problem credits: Danny Mittal

Contest has ended. No further submissions allowed.