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

|

36 Discussions

|

  • dehaka
     + 0 comments

    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

  • 2020A7PS0152G
     + 0 comments

    Can someone explain why this code is not clearing all test cases: https://p.ip.fi/0EaF

  • 2020A7PS0152G
     + 0 comments

    Can someone explain why this code is not clearing all test cases:

    include

    define ll long long int

    using namespace std;

    ll fairCut(int k, vector arr) { int n = arr.size(); vector> dp(n+1, vector (k+1, LLONG_MAX));

    sort(arr.begin(), arr.end());

dp[0][0]=0;

for(int i=1; i<=n; i++){
    for(int j=0; j<=k; j++){
        if(i<j) continue;

        ll inc = dp[i-1][j-1];
        ll exc = dp[i-1][j];

        if(inc!=LLONG_MAX) inc+=arr[i-1]*(2*(i-j)-(n-k));
        if(exc!=LLONG_MAX) exc+=arr[i-1]*(2*j-k);

        dp[i][j]=min(inc, exc);
    }
}

return dp[n][k];

    }

    signed main() { int n, k;

    cin>>n>>k;

vector<ll> arr(n);

for (int i = 0; i < n; i++) {
    cin>>arr[i];
}

ll result = fairCut(k, arr);

cout << result << "\n";

return 0;

    }

  • mineman1012221
     + 0 comments

    Here is the solution of Fair Cut Click Here