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])
```

{"mode":"full","isActive":false}

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)

List<Integer> a = new ArrayList<>();
List<Integer> b = new ArrayList<>();

for (int i = 0; i < n; i++) {
if (aIdx.contains(i))
else
}

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();
}
}
```

{"mode":"full","isActive":false}

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;
}
```

{"mode":"full","isActive":false}

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("%lld\n", bestscore);

return 0;
}
```

{"mode":"full","isActive":false}