PIB '20 P5 - 4D Matrices

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 0.5s
Memory limit: 256M

Author:
Problem type

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

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

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

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

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

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

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

Input Specification

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

The next N lines will each contain N-1 integers, d_{i,j} (|d_{i,j}| \le 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 space separated integers, the array v. v_i must fit in a 32-bit integer (-2^{31} \le v_i < 2^{31}), or you will receive Wrong Answer.

Subtasks

Subtask 1 [7%]

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

Subtask 2 [24%]

d_{i,j} \ge 0

Subtask 3 [69%]

No additional constraints.

Sample Input for Subtask 1

4
2 1 0
3 3 0
1 6 1
1 1 1

Sample Output for Subtask 1

YES
-1 -3 -2 0

Explanation for Sample for Subtask 1

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

-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 is 0. Note that there could be multiple answers. For example, [-2, -3, -3, 0] is also an answer. You are only required to print any one of them.

Sample Input for Subtask 2

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

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

Sample Input for Subtask 3

3
3 -12
-6 3
6 -5

Sample Output for Subtask 3

YES
-1 5 -1

Comments

There are no comments at the moment.