We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Fair Cut
  5. Discussions

Fair Cut

Sort by

recency

|

39 Discussions

|

  • ds1b_1641540100
     + 0 comments

    Python Solution

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# 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
#

def fairCut(k, arr):
    # Write your code here
    n = len(arr)
    if n - k < k:
        k = n - k
    arr.sort()
    is_even_n = n % 2 == 0
    is_even_k = k % 2 == 0
    indices = []
    if (is_even_n and is_even_k) or (not is_even_n and is_even_k):
        x = (n + 1) // 2
        for i in range(k // 2):
            indices.append(x - (2 * i + 1))
            indices.append(x + (2 * i + 1))
    elif (is_even_n and not is_even_k) or (not is_even_n and not is_even_k):
        x = (n + 1) // 2
        indices = [x]
        for i in range(k // 2):
            indices.append(x - (2 * (i + 1)))
            indices.append(x + (2 * (i + 1)))

    s1 = []
    s2 = []
    for i in range(n):
        if i + 1 in indices:
            s1.append(arr[i])
        else:
            s2.append(arr[i])
    total_sum = 0
    for i in s1:
        for j in s2:
            total_sum += abs(i - j)
    return total_sum


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    arr = list(map(int, input().rstrip().split()))

    result = fairCut(k, arr)

    fptr.write(str(result) + '\n')

    fptr.close()

  • ds1b_1641540100
     + 0 comments

    C++ Solution

    #include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    int a[n];
    for(auto i = 0; cin >> a[i]; i++) {
    }
    sort(a, a + n);
    auto result = 0ll;
    for(auto i = 0ll, j = n; i < n / 2; i++) {
        if(k > j - k) {
            result += (a[n - i - 1] - a[i]) * (j - k);
            j -= 2;
            k -= 2;
        } else {
            result += (a[n - i - 1] - a[i]) * k;
            j -= 2;
        }
    }
    cout << result;
    return 0;
}

  • LeftNutz
     + 1 comment

    Here's what worked for me:

    1. Assuming a sorted list, everything revolves around the center of the list
    2. What worked for me was first finding the mid point index of the list
    3. Then define a start point index and an end point index from that mid point.
    4. Then if K is an even number, then the start point index will be midpoint - k + 1 and the end point index will be midpoint + k - 2.
    5. If K is an odd number, then the start point index will be midpoint - k and the end point index will be midpoint + k - 1.
    6. Then while K is greater than 1, I will keep reducing K by 2 and repeat the process.
    7. Since I'm using python I'm going to store the value of the start index , midpoint index and end point index in a tuple for each iteration
    8. Once I have the tuple which will contain 3 elements, I'm only going to grab the value of the start and end point indices from the parent and store those in a separate list.
    9. Then, I'm going to set the value of the start and end point indices to -1 in the parent list.
    10. The midpoint will stay constant through each iteration
    11. If K is odd, then I'm going to store the value of the midpoint index in the list and set that value to -1 on the parent list after the loop ends.
    12. Then I'm going to filter out all the -1 values from the parent list and sort it.
    13. I'm going to sort the list the list containing K elements as well
    14. Finally I'm going to calculate the absolute difference between the two lists and return that value.
    15. If K is 1, then I'm going to store the value of the midpoint in the list and set that value to -1 on the parent list and just go ahead and calculate the absolute difference between the two lists.

  • dehaka
     + 1 comment

    hard tedious question. the I that minimize unfairness is actually fixed, location depends on parity of n and k. proof is very long and tedious

    very fast O(n) method, except for the sort(arr.begin(), arr.end()) which is O(nlog n), the rest of algo is linear time O(n)

    long unfairness(const vector<long>& arr, const vector<bool>& location) {
    long sum = 0;
    pair<long, int> Ipartial = { 0, 0 }, Jpartial = { 0, 0 };
    for (int i = 1; i <= arr.size(); i++) {
        if (location[i]) {
            sum = sum + Jpartial.second * arr[i - 1] - Jpartial.first;
            Ipartial = { Ipartial.first + arr[i - 1], Ipartial.second + 1 };
        }
        else {
            sum = sum + Ipartial.second * arr[i - 1] - Ipartial.first;
            Jpartial = { Jpartial.first + arr[i - 1], Jpartial.second + 1 };
        }
    }
    return sum;
}

long fairCut(int k, vector<long>& arr) {
    if (static_cast<float>(arr.size()) / 2 + 1 <= k) return fairCut(arr.size() - k, arr);
    sort(arr.begin(), arr.end());
    vector<bool> location(arr.size() + 1, false);
    if (k % 2 == 1) {
        int index = ceil(static_cast<float>(arr.size()) / 2);
        location[index] = true;
        for (int i=0; i < k / 2; i++) {
            location[arr.size() / 2 - 1 - 2*i] = true;
            location[index + 2*(i+1)] = true;
        }
        return unfairness(arr, location);
    }
    else if (k % 2 == 0) {
        int index = ceil(static_cast<float>(arr.size()) / 2) + 1;
        for (int i = 0; i < k / 2; i++) {
            location[arr.size() / 2 - 2 * i] = true;
            location[index + 2 * i] = true;
        }
        return unfairness(arr, location);
    }
    return 0;
}

  • yashparihar729
     + 1 comment

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Fair Cut Problem Solution