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

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