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));
long answer = Long.MAX_VALUE;
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)) {
answer = Math.min(answer, right.sum - left.sum);
}
}
out.append(answer).append('\n');
}
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++) {
long answer = Long.MAX_VALUE;
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)) {
answer = Math.min(answer, right.sum - left.sum);
}
}
out.append(answer).append('\n');
}
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++) {
Arrays.fill(answers[l], Long.MAX_VALUE);
}
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) {
answers[l][r] = Math.min(answers[l][r], difference);
}
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) {
answers[l][r] = Math.min(answers[l][r], difference);
}
}
for (int l = 1; l <= n; l++) {
for (int r = n; r > l; r--) {
answers[l + 1][r] = Math.min(answers[l + 1][r], answers[l][r]);
answers[l][r - 1] = Math.min(answers[l][r - 1], answers[l][r]);
}
}
StringBuilder out = new StringBuilder();
for (int k = 1; k <= n; k++) {
out.append(answers[k][k]).append('\n');
}
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;
}
}
}