(Analysis by Benjamin Qi)

Partial credit (inputs 1-7):

For an index $i$, the answer for that index is equal to the minimum absolute difference between all subarrays that include $a_i$ and all subarrays that don't include $a_i$. This gives us the following solution: for each $i$, sort all subarrays that don't include $a_i$ and all those that include $a_i$ by sum, and then use two pointers to compute the answer. This takes $O(N^2\log N)$ time for each $i$, giving $O(N^3\log N)$ time overall.

import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class EqualSumSubarraysSlow {

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long[] sums = new long[n + 1];
for (int k = 1; k <= n; k++) {
sums[k] = in.nextLong();
sums[k] += sums[k - 1];
}

StringBuilder out = new StringBuilder();
for (int k = 1; k <= n; k++) {
List<Subarray> subarrays = new ArrayList<>();
for (int r = 1; r <= n; r++) {
for (int l = 1; l <= r; l++) {
subarrays.add(new Subarray(l, r, sums[r] - sums[l - 1]));
}
}
subarrays.sort(Comparator.comparingLong(subarray -> subarray.sum));
for (int j = 1; j < subarrays.size(); j++) {
Subarray left = subarrays.get(j - 1);
Subarray right = subarrays.get(j);
if (left.contains(k) != right.contains(k)) {
}
}
}
System.out.print(out);
}

static class Subarray {
final int from;
final int to;
final long sum;

public Subarray(int from, int to, long sum) {
this.from = from;
this.to = to;
this.sum = sum;
}

boolean contains(int index) {
return from <= index && index <= to;
}
}
}


There are other ways to pass the first seven inputs. For example, we could iterate over all $O(N^4)$ pairs of disjoint subarrays, and for each pair, update the answers for all indices in exactly one of the subarrays in $O(1)$ time, similarly as the bonus solution below.

Full credit:

To optimize the solution above, observe that we only need to sort the subarrays by sum once. Then for an index $i$, the answer for that index is equal to the minimum absolute difference between two consecutive subarrays in the sorted order where one subarray contains $i$ and the other doesn't, which we can compute in $O(N^2)$ time for each $i$. This takes $O(N^3)$ time overall.

Danny Mittal's code:

import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class EqualSumSubarrays {

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long[] sums = new long[n + 1];
for (int k = 1; k <= n; k++) {
sums[k] = in.nextLong();
sums[k] += sums[k - 1];
}

List<Subarray> subarrays = new ArrayList<>();
for (int k = 1; k <= n; k++) {
for (int j = 1; j <= k; j++) {
subarrays.add(new Subarray(j, k, sums[k] - sums[j - 1]));
}
}
subarrays.sort(Comparator.comparingLong(subarray -> subarray.sum));

StringBuilder out = new StringBuilder();
for (int k = 1; k <= n; k++) {
for (int j = 1; j < subarrays.size(); j++) {
Subarray left = subarrays.get(j - 1);
Subarray right = subarrays.get(j);
if (left.contains(k) != right.contains(k)) {
}
}
}
System.out.print(out);
}

static class Subarray {
final int from;
final int to;
final long sum;

public Subarray(int from, int to, long sum) {
this.from = from;
this.to = to;
this.sum = sum;
}

boolean contains(int index) {
return from <= index && index <= to;
}
}
}


Bonus:

It is easy to optimize the solution above to $O(N^2\log N)$ time by looking at every two consecutive subarrays in the sorted order and updating the answer for all indices $i$ contained in exactly one of the subarrays in $O(1)$ time. However, this was not necessary for full credit, and it is not much faster under the given constraints.

Danny Mittal's code:

import java.util.*;

public class EqualSumSubarraysFast {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long[] sums = new long[n + 1];
for (int k = 1; k <= n; k++) {
sums[k] = in.nextLong();
sums[k] += sums[k - 1];
}

List<Subarray> subarrays = new ArrayList<>();
for (int k = 1; k <= n; k++) {
for (int j = 1; j <= k; j++) {
subarrays.add(new Subarray(j, k, sums[k] - sums[j - 1]));
}
}
subarrays.sort(Comparator.comparingLong(subarray -> subarray.sum));

long[][] answers = new long[n + 1][n + 1];
for (int l = 1; l <= n; l++) {
}

for (int j = 1; j < subarrays.size(); j++) {
Subarray left = subarrays.get(j - 1);
Subarray right = subarrays.get(j);
long difference = right.sum - left.sum;

int l = Math.min(left.from, right.from);
int r = Math.min(Math.min(left.to, right.to), Math.max(left.from, right.from) - 1);
if (l <= r) {
}

r = Math.max(left.to, right.to);
l = Math.max(Math.max(left.from, right.from), Math.min(left.to, right.to) + 1);
if (l <= r) {
}
}

for (int l = 1; l <= n; l++) {
for (int r = n; r > l; r--) {
}
}

StringBuilder out = new StringBuilder();
for (int k = 1; k <= n; k++) {
}
System.out.print(out);
}

static class Subarray {
final int from;
final int to;
final long sum;

public Subarray(int from, int to, long sum) {
this.from = from;
this.to = to;
this.sum = sum;
}
}
}