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.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; 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 { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); int[][] differences = new int[n][n]; for (int j = 0; j < n; j++) { StringTokenizer tokenizer = new StringTokenizer(in.readLine()); for (int k = j; k < n; k++) { differences[j][k] = Integer.parseInt(tokenizer.nextToken()); } } List<Integer> distinct = new ArrayList<>(); distinct.add(0); for (int j = 1; j < n; j++) { if (differences[j - 1][j] != 0) { distinct.add(j); } } int[] answer = new int[n]; if (distinct.size() > 1) { answer[distinct.get(1)] = differences[0][distinct.get(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; answer[c] = answer[b] + (sign * Integer.signum(answer[b] - answer[a]) * differences[b][c]); } for (int j = 1; j < n; j++) { if (differences[j - 1][j] == 0) { answer[j] = answer[j - 1]; } } } StringJoiner joiner = new StringJoiner(" "); for (int j = 0; j < n; j++) { joiner.add("" + answer[j]); } System.out.println(joiner); } }