PIB '20 P5 - 4D Matrices - Olympiads Online Judge

PIB '20 P5 - 4D Matrices

Points: 10 (partial)

Time limit: 0.5s

Memory limit: 256M

Author:

Ninjaclasher

Problem type

You are given a grid $d$ $d$ of size $N \times (N-1)$ $N \times (N - 1)$ .

Using this grid, you are to generate a new grid $a$ $a$ of size $N \times N$ $N \times N$ as follows:

The first element in each row $i$ $i$ will be assigned a value of $v_i$ $v_{i}$ . The array $v$ $v$ is unknown to you.
For each element $2 \le j \le N$ $2 \leq j \leq N$ in row $i$ $i$ , $a_{i,j} = a_{i, j-1} + d_{i, j-1}$ $a_{i, j} = a_{i, j - 1} + d_{i, j - 1}$ .

A third array, $k$ $k$ will then be generated as follows:

The $i^\text{th}$ $i^{th}$ element is the median of the $i^\text{th}$ $i^{th}$ column in $a$ $a$ .

It is known that the median of the array $k$ $k$ is exactly zero. Can you determine any array $v$ $v$ that makes the median of $k$ $k$ zero, or state that it is impossible?

Note: For odd $N$ $N$ , the median of the array is the middle element in the sorted array. For even $N$ $N$ , the median is the minimum of the two middle elements in the sorted array. For example, the median of $[1, 6, 4, 3]$ $[1, 6, 4, 3]$ is $3$ $3$ .

Input Specification

The first line will contain the integer $N$ $N$ $(2 \le N \le 1000)$ $(2 \leq N \leq 1000)$ .

The next $N$ $N$ lines will each contain $N-1$ $N - 1$ integers, $d_{i,j}$ $d_{i, j}$ $(|d_{i,j}| \le 10^5)$ $(| d_{i, j} | \leq 10^{5})$ .

Output Specification

If it is impossible, print NO on one line.

Otherwise, print YES on the first line.
On the second line, print $N$ $N$ space separated integers, the array $v$ $v$ . $v_i$ $v_{i}$ must fit in a 32-bit integer $(-2^{31} \le v_i < 2^{31})$ $(- 2^{31} \leq v_{i} < 2^{31})$ , or you will receive Wrong Answer.

Subtasks

Subtask 1 [7%]

$N \le 5, d_{i,j} \ge 0$ $N \leq 5, d_{i, j} \geq 0$

Subtask 2 [24%]

$d_{i,j} \ge 0$ $d_{i, j} \geq 0$

Subtask 3 [69%]

No additional constraints.

Sample Input for Subtask 1

Copy

Sample Output for Subtask 1

Copy

YES
-1 -3 -2 0

Explanation for Sample for Subtask 1

The array $a$ $a$ that is generated with the array $k$ $k$ below is:

Copy

-1  1  2  2
-3  0  3  3
-2 -1  5  6
 0  1  2  3
-----------
-2  0  2  3

The median of the array $k$ $k$ is $0$ $0$ . Note that there could be multiple answers. For example, $[-2, -3, -3, 0]$ $[- 2, - 3, - 3, 0]$ is also an answer. You are only required to print any one of them.

Sample Input for Subtask 2

Copy

7
1 2 2 2 1 1
3 0 0 1 1 1
0 0 0 0 0 0
1 0 2 1 0 1
2 0 0 1 4 0
2 1 1 2 4 5
1 1 1 1 1 1

Sample Output for Subtask 2

Copy

YES
5 1 -2 -3 1 -5 -8

Sample Input for Subtask 3

Copy

Sample Output for Subtask 3

Copy

YES
-1 5 -1

Comments

There are no comments at the moment.