HackerRank Fair Cut Problem Solution

Yashwant Parihar,

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
HackerRank Fair Cut Problem Solution
HackerRank Fair Cut Problem Solution

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])
c C# C++ HackerRank Solutions java javascript python