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 ai and all subarrays that don't include ai. This gives us the following solution: for each i, sort all subarrays that don't include ai and all those that include ai by sum, and then use two pointers to compute the answer. This takes O(N2logN) time for each i, giving O(N3logN) 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(N4) 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(N2) time for each i. This takes O(N3) 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(N2logN) 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; } } }