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.

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

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

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

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;

}