(Analysis by Benjamin Qi)

Solution 1:

First set $a_N=0$. Next, we determine $a_i$ for $i=N-1,N-2,\dots,1$ in that order. We know that $a_i=a_{i+1}\pm r_{i,i+1}$. We can first try setting $a_i=a_{i+1}+r_{i,i+1}$; if this is incompatible with some $r_{i,j}$ then set $a_i=a_{i+1}-r_{i,i+1}$ instead. Using induction, it may be proven that this recovers the original array up to a negation and a translation.

Ben's code:

N = int(input())

difs = [list(map(int, input().split())) for _ in range(N)]

ans = [0]*N
for i in reversed(range(N-1)):
def ok():
mx = -float('inf')
mn = float('inf')
for j in range(i,N):
mx = max(mx, ans[j])
mn = min(mn, ans[j])
if mx-mn != difs[i][j-i]:
return False
return True
ans[i] = ans[i+1] + difs[i][1]
if not ok():
ans[i] = ans[i+1] - difs[i][1]
assert ok()

print(" ".join(map(str, ans)))

Solution 2:

Consider the case where every two consecutive elements of $a$ are distinct (that is, $r_{i,i+1}\neq 0$ for all $1\le i<N$). Then given $a_i$, $a_{i+1}$, $r_{i+1,i+2}$ and $r_{i,i+2}$, we can uniquely determine $a_{i,i+2}$. This gives us a solution that runs in linear time after reading in the input: set $a_1=0$, $a_2=r_{1,2}$, and then use the observation above to uniquely determine $a_3,\dots,a_N$. Handling the case where consecutive elements of $a$ can be equal requires a bit more care.

Danny Mittal's code:

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;
import java.util.StringTokenizer;

public class ArrayDifferences {

public static void main(String[] args) throws IOException {
int[][] differences = new int[n][n];
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
differences[j][k] = Integer.parseInt(tokenizer.nextToken());
}
}
List<Integer> distinct = new ArrayList<>();
for (int j = 1; j < n; j++) {
if (differences[j - 1][j] != 0) {
}
}
if (distinct.size() > 1) {
for (int j = 2; j < distinct.size(); j++) {
int a = distinct.get(j - 2);
int b = distinct.get(j - 1);
int c = distinct.get(j);
int sign = differences[a][c] == differences[a][b] + differences[b][c] ? 1 : -1;
}
for (int j = 1; j < n; j++) {
if (differences[j - 1][j] == 0) {