HackerRank Fair Cut problem solution

In this HackerRank Fair Cut problem solution, Li and Lu have n integers that they want to divide fairly between the two of them. They decide that if Li gets integers with indices I = {i1, i2,…,ik} (which implies that Lu gets integers with indices J = {1,….,n} I), then the measure of the unfairness of this division is equal to the summation of |ai – aj|

Problem solution in Python.

n, k = map(int, input().split())

if 2*k > n:
    k = n - k

a = sorted(map(int, input().split()))

# create dp

dp = [[float('inf') for i in range(0, n + 1)] for j in range(0, n + 1)]

dp[0][0] = 0

for i in range(0, n):
    for j in range(0, i + 1):
        if i > k and i-j > n-k:
            continue
        to_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
        to_lu = dp[i][j] + a[i] * (j - (k - j))
        # to Li
        if dp[i+1][j+1] > to_li:
            dp[i+1][j+1] = to_li
        
        # to Lu
        if dp[i+1][j] > to_lu:
            dp[i+1][j] = to_lu

print(dp[n][k])

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static long fairCut(int k, int[] arr) {
        
        Arrays.sort(arr);
        
        int n = arr.length;
        
        if (k * 2 > n)
            k = n - k;
        
        long res = 0;
        
        if ((n - 2 * k) % 2 ==0) {
            res = helper(arr, (n - 2 * k) / 2 + 1, k);
        } else {
            res = Math.min(helper(arr, (n - 2 * k) / 2, k), helper(arr, (n - 2 * k) / 2 + 1, k));
        }
        
        return res;
    }
    
    static long helper(int[] arr, int start, int k) {
        int n = arr.length;
        Set<Integer> aIdx = new HashSet<>();
        for (int i = start, j = 0; j < k; j++, i += 2)
            aIdx.add(i);
        
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (aIdx.contains(i))
                a.add(arr[i]);
            else
                b.add(arr[i]);
        }
        
        return calc(a, b);

    }
    
    static long calc(List<Integer> a, List<Integer> b) {
        long res = 0;
        
        for (int aa : a) {
            for (int bb : b) {
                res += Math.abs(aa - bb);
            }
        }
        
        return res;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nk = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nk[0].trim());

        int k = Integer.parseInt(nk[1].trim());

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");

        for (int arrItr = 0; arrItr < n; arrItr++) {
            int arrItem = Integer.parseInt(arrItems[arrItr].trim());
            arr[arrItr] = arrItem;
        }

        long result = fairCut(k, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
using namespace std;


int main() {
    // input
    int cnt; cin >> cnt;
    int k; cin >> k;
    deque<long long> a(cnt);
    copy_n(istream_iterator<long long>(cin), cnt, a.begin());
    
    // sort and organize in lines. O(n*log(n))
    sort(a.begin(), a.end());
    deque<long long> lens;
    while (!a.empty())
    {
        // right end of the line
        auto r = a.back(); a.pop_back();
        if (a.empty())
        {
            // no points left for new line - insert line with 0 length
            lens.push_back(0);
        }
        else
        {
            auto l = a.front();a.pop_front();
            lens.push_back(r - l);
        }
    }
    
    long long t = 0;
    // calculate sum(every number to every number using lines). O(n)
    for (int i = 0; i < lens.size(); i ++)
    {
        t += lens[i] * (cnt - 2*i - 1);
    }
    
    // check if we should split the smallest line of two with 0-length
    if (k % 2 == 1)
    {
        if (cnt % 2 == 0)
        {
            lens[lens.size() - 1] = 0;
            lens.push_back(0);
        }
    }
    
    int s = k; // number to select
    vector<long long> sl; // selected lines
    int r = cnt - k; // numbers to remain 
    vector<long long> rl; // non-selected lines
    // greedy approach to place line in required group O(n)
    while (s > 0 || r > 0)
    {
        if (s > r)
        {
            sl.push_back(lens.front());
            s -= 2;
        }
        else
        {
            rl.push_back(lens.front());
            r -= 2;
        }
        lens.pop_front();
    }
    
    // result -= sum(selected to selected) O(n)
    for (int i = 0; i < sl.size(); i ++)
        t -= sl[i] * (k - 2*i - 1);
    // result -= sum(non-selected to non-selected) O(n)
    for (int i = 0; i < rl.size(); i ++)
        t -= rl[i] * ((cnt-k) - 2*i - 1);
    cout << t;
    return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n;
int k;
int a[3001];
long long listcost[3001];
long long allcost[3001];

int main() {
  int i;
  int j;
  int besti;
  long long bestscore;
  long long allscore;
  long long tmp;

  scanf("%d %d", &n, &k);
  if (k > n - k) {
    k = n - k;
  }
  for (i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  for (i = 1; i < n; ++i) {
    tmp = a[i];
    j = i;
    while (j) {
      if (tmp > a[j - 1]) {
        break;
      }
      a[j] = a[j - 1];
      j -= 1;
    }
    a[j] = tmp;
  }
  for (i = 0; i < n; ++i) {
    listcost[i] = 0;
    allcost[i] = 0;
  }
  for (i = 0; i < n; ++i) {
    for (j = 0; j < n; ++j) {
      if (a[i] > a[j]) {
        allcost[i] += a[i] - a[j];
      } else {
        allcost[i] += a[j] - a[i];
      }
    }
  }
  allscore = 0;
  bestscore = 0;
  for (i = 0; i < k; ++i) {
    allscore = bestscore;
    besti = 0;
    bestscore = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
    for (j = 0; j < n; ++j) {
      tmp = allcost[j];
      tmp -= listcost[j];
      tmp -= listcost[j];
      tmp += allscore;
      if (tmp < bestscore) {
        bestscore = tmp;
        besti = j;
      }
      if (tmp == bestscore) {
        if (listcost[j] > listcost[besti]) {
          besti = j;
        }
      }
    }
    tmp = allcost[besti];
    allcost[besti] = allcost[n - 1];
    allcost[n - 1] = tmp;
    tmp = listcost[besti];
    listcost[besti] = listcost[n - 1];
    listcost[n - 1] = tmp;
    tmp = a[besti];
    a[besti] = a[n - 1];
    a[n - 1] = (int)tmp;
    n -= 1;
    j = besti;
    while (j < n - 1) {
      if (a[j] < a[j + 1]) {
        break;
      }
      tmp = allcost[j];
      allcost[j] = allcost[j + 1];
      allcost[j + 1] = tmp;
      tmp = listcost[j];
      listcost[j] = listcost[j + 1];
      listcost[j + 1] = tmp;
      tmp = a[j];
      a[j] = a[j + 1];
      a[j + 1] = (int)tmp;
      j += 1;
    }
    // update listcost
    for (j = 0; j < n; ++j) {
      if (a[j] > a[n]) {
        listcost[j] += a[j] - a[n];
      } else {
        listcost[j] += a[n] - a[j];
      }
    }
  }
  printf("%lldn", bestscore);

  return 0;
}