# Codeforces problem Java code optimization

The problem says:

You are given an array a of length 2n. Consider a partition of array a into two subsequences p and q of length n each (each element of array a should be in exactly one subsequence: either in p or in q).
Let's sort p in non-decreasing order, and q in non-increasing order, we can denote the sorted versions by x and y, respectively. Then the cost of a partition is defined as f(p,q)=∑i=1ⁿ|xi−yi|.
Find the sum of f(p,q) over all correct partitions of array a. Since the answer might be too big, print its remainder modulo 998244353.

Input:
The first line contains a single integer n (1≤n≤150000). The second line contains 2n integers a1,a2,…,a2n (1≤ai≤10^9) — elements of array a.

Output:
Print one integer — the answer to the problem, modulo 998244353.

My solution generates all combinations of size n from a, then goes through each pair of combinations that complement each other, sorts them, and finally calculates the cost. Here is the code:

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

public static void main(String []args)
{
Scanner in = new Scanner(System.in);

int k = in.nextInt();
int[] input = new int[2 * k];
for (int i = 0; i < 2 * k; i++) {
input[i] = in.nextInt();
}

List<int[]> combinations = new ArrayList();
int[] indices = new int[k];

//generates all valid combinations of size k, choosing k
for(int i = 0; (indices[i] = i) < k - 1; i++);
for (;;) {
int i;
for (i = k - 1; i >= 0 && indices[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
indices[i]++;
for (++i; i < k; i++) {
indices[i] = indices[i - 1] + 1;
}
}
//for depugging
//combinations.forEach(e -> System.out.println(Arrays.toString(e)));
//int[] temp1, temp2;

//goes through all pairs that complement each other and calculates the cost for each
int theSum = 0;
for (int i = 0, j = combinations.size() - 1; i < combinations.size() && j >= 0; i++, j--) {
//  temp1 = combinations.get(i);
//  temp2 = combinations.get(j);
Arrays.sort(combinations.get(i));
Arrays.sort(combinations.get(j));
reverse(combinations.get(j));
//for debugging
//System.out.println(Arrays.toString(temp1) + ", " + Arrays.toString(temp2));
theSum += cost(combinations.get(i), combinations.get(j));
}
System.out.println(theSum % 998244353);
}
public static int[] getCombination(int[] input, int[] indices) {
int[] result = new int[indices.length];
for (int i = 0; i < indices.length; i++)
result[i] = input[indices[i]];
return result;
}
public static int cost(int[] x, int[] y) {
int sum = 0;
for (int i = 0; i < x.length; i++) {
sum += Math.abs(x[i] - y[i]);
}
return sum;
}
public static void reverse(int[] array) {
for(int i = 0; i < array.length / 2; i++) {
int temp = array[i];
array[i] = array[array.length - i - 1];
array[array.length - i - 1] = temp;
}
}
}


The memory usage exceeded 512 MB and I don't know if I should change the data structures, or the algorithms, or both. I would appreciate any suggestions.

• Hint. Sort the array. Prove (or at least convince yourself) that no matter what the partition is, the guys from the top half do not compete against each other. They always contribute with as +, and the guys from the bottom half alway contribute with -. I hope it is enough to come up with the fast solution.
– vnp
Commented Nov 28, 2020 at 20:54
• Welcome to CodeReview@SE. Code indentation still is weird. You present fors controlling empty statements (for(int i = 0; (indices[i] = i) < k - 1; i++);, for (i = k - 1; i >= 0 && indices[i] == input.length - k + i; i--);) - most likely not what you intend. Commented Nov 30, 2020 at 7:13
• To the best of your knowledge: Does the code presented work as intended? How did you establish confidence in it? Commented Nov 30, 2020 at 7:14