HackerRank Fair Cut Problem Solution
In this post, we will solve HackerRank Fair Cut Problem Solution.
Li and Lu have n integers, a1, a2,…, an, that they want to divide fairly between the two of them. They decide that if Li gets integers with indices I = {1, 2,…,i} (which implies that Lu gets integers with indices J = {1,…, n} \ I), then the measure of unfairness of this division is:
f(1) – ΣΣ – = iel jeJ aj
Find the minimum measure of unfairness that can be obtained with some division of the set of integers where Li gets exactly & integers.
Note A B means Set complement
Input Format
The first line contains two space-separated integers denoting the respective values of n (the number of integers Li and Lu have) and k (the number of integers Li wants). The second line contains n space-separated integers describing the respective values of
a1, a2,…, an
Output Format
Print a single integer denoting the minimum measure of unfairness of some division where Li gets K integers.
Sample Input 0
4 2
4 3 1 2
Sample Output 0
6
Sample Input 1
4 1
3 3 3 1
Sample Output 1
2
Fair Cut C Solution
#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;
}
Fair Cut C++ Solution
#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;
}Fair Cut C Sharp Solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace HackerRanksCMD
{
class fairCuttttt
{
public static Int64 fairCut(int n, int k, List<int> arr)
{
arr.Sort();
if (2 * k > n) k = n - k;
var s = (n - 2 * k) >> 1;
var e = s + 2 * k;
Int64 ans = 0;
Int64 sum1 = 0, cnt1 = 0;
Int64 sum2 = 0, cnt2 = 0;
for (int i = 0; i < n; ++i)
{
Int64 x = arr[i];
var bitwiseAND = (i & 1);
if (s <= i && i < e && bitwiseAND == 1)
{
sum1 += x;
cnt1 += 1;
ans += cnt2 * x - sum2;
}
else
{
sum2 += x;
cnt2 += 1;
ans += cnt1 * x - sum1;
}
}
return ans;
}
public static void Main(string[] args)
{
string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
int n = Convert.ToInt32(firstMultipleInput[0]);
int k = Convert.ToInt32(firstMultipleInput[1]);
List<int> arr = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(arrTemp => Convert.ToInt32(arrTemp)).ToList();
Int64 result = fairCut(n, k, arr);
Console.WriteLine(result);
Console.Read();
}
}
}Fair Cut Java Solution
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();
}
}Fair Cut JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'fairCut' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER k
* 2. INTEGER_ARRAY arr
*/
function fairCut(n, k, arr) {
arr.sort((a, b) => a - b);
if (2 * k > n) k = n - k;
const s = (n - 2 * k) >> 1;
const e = s + 2 * k;
let ans = 0;
let sum1 = 0, cnt1 = 0;
let sum2 = 0, cnt2 = 0;
for (let i = 0; i < n; ++i) {
const x = arr[i];
if (s <= i && i < e && (i & 1)) {
sum1 += x;
cnt1 += 1;
ans += cnt2 * x - sum2;
} else {
sum2 += x;
cnt2 += 1;
ans += cnt1 * x - sum1;
}
}
return ans;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const n = parseInt(firstMultipleInput[0], 10);
const k = parseInt(firstMultipleInput[1], 10);
const arr = readLine().replace(/\s+$/g, '').split(' ').map(arrTemp => parseInt(arrTemp, 10));
const result = fairCut(n, k, arr);
ws.write(result + '\n');
ws.end();
}Fair Cut Python Solution
n, k = map(int, input().split())
if k > n // 2:
k = n - k
# sort the array, so that when processing ith number in a, we know a[i] is
# larger than or equal to previously processed numbers, so calculating abs
# is easier
a = sorted(map(int, input().split()))
# dp[i][j] is the value when ith number in a has already processed, and j of
# those numbers assigned to li, initialize all value to maximum number
dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
# When i==0, j==0, no number assigned, the value is zero
dp[0][0] = 0
for i in range(0, n): # iter through a
# iter through the possiblities of sizes in li when a[i] needs to be
# assigned
for j in range(0, i + 1):
# We ignore the cases when the number of li or lu larger than required
if j > k or i - j > n - k:
continue
# There are two possiblities: (1)assign a[i] to li (2) or to lu
# Possiblity (1) assign to li:
# If a[i] would be assigned to li:
# all the numbers in lu needs to be substracted from a[i],
# so we add (i -j)* a[i] to d[i][j].
# Note: substraction of all lu has been done in prevous steps
# (see below, 3 lines later)
# (i-j) is the current number in lu.
#
# a[i] WILL be substracted from all future a[x] assigned to lu,
# so we substract (n - k - (i - j))*a[i] from d[i][j]
# (n-k): size of lu in the final step,
# (i-j): current number in lu
# (n-k -(i-j)): size of remaining numbers to be assigned to lu
temp_li = dp[i][j] + a[i] * (i - j - (n - k - (i - j)))
# Possiblity (2) assign to lu:
# If a[i] would be assigned to lu:
# all the numbers in li needs to be substracted from a[i],
# so we add j* a[i] to d[i][j]
# Note: substraction of all lu has been done in prevous steps
# (see below, 2 lines later)
#
# a[i] WILL be substracted from all future a[x] assigned to li,
# so we substract (k-j)*a[i] from d[i][j]
# (k-j) is the size of remaining numbers to be assigned to li
temp_lu = dp[i][j] + a[i] * (j - (k - j))
# Possiblity (1), both sizes of assigned numbers and li increment by 1
if dp[i + 1][j + 1] > temp_li:
dp[i + 1][j + 1] = temp_li
# Possiblity (2), size of assigned numbers increment by 1, size of li
# remains the same
if dp[i + 1][j] > temp_lu:
dp[i + 1][j] = temp_lu
print(dp[n][k])
