hackerrank fair cut stuff

Man, it is unfair how good I am!

Scout, TF2

man, usaco is this week
i hope i get to plat

anyways, this problem!
it's absolute cancer, and the crap editorials i've found don't help either
so i'm writing this to help others suffer less

too lazy to describe the problem, just read the actual thing lol
but the dp relation is seemingly obvious, right?
just a lil

``` dp[i][t] = min unfairness given that we only consider first i elements & take t of those ```

and then we're done, right?
right?

well the thing is, since all the elements depend on each other for the sum, we can't just consider each element independently and go from there

the key is in this expression for the example input given at the bottom of the statement: \[ |a_2-a_1|+|a_2-a_3|+|a_4-a_1|+|a_4-a_3|=1+2+2+1=6 \]

if we sort the example array to be `[1, 2, 3, 4]` (reorganizing the indices as needed), note that the expression becomes: \[ (a_4-a_3)+(a_3-a_1)+(a_4-a_2)+(a_3-a_2)=2a_4+a_3-2a_2-a_1 \] i feel like just evaluating this expression is much easier than just having some arbitrary definition of unfairness, no?

---

so instead of directly considering the minimum unfairness, let's just add how much each index contributes to that expression- that should be much easier than actually knowing what numbers we have to get the distance to or whatever crap

ok so let's do two things:

1. sort our array so we don't have to worry about abs values (will explain later)
2. redefine our dp as something actually calculable:

``` dp[i][t] = min VALUE OF THAT EXPRESSION THING ABOVE given that we only consider the first i elements, taking t so far ```

---

now, when we actually fill out our array and we're at `i` and `t`, we have two choices:

1. add the element to our set

in this case, we know that we're going to add `i - t` and subtract `(size - i) - (take_num - t)` of the current value
the first is because there's `i - t` non-selected elements in the left part of the array, and we know the current element is bigger than the entire left half so
the second part is similar, it's because that's how many elements won't be selected in the later half

2. or we don't lmao

analogous to the first part
we add `t` and subtract `take_num - t` of the current element
that's because there's `t` selected elements to the left and `take_num - t` elements to the right

alright, we're done! the code naturally follows:

```py size, take_num = [int(i) for i in input().split()] arr = sorted(int(i) for i in input().split()) best_unfairness = [[float('inf')] * (take_num + 1) for _ in range(size + 1)] # set our base case best_unfairness[0][0] = 0 for i in range(1, size + 1): n = arr[i - 1] # just a shorthand # we can only take at most i elements, so yeah for t in range(min(i, take_num) + 1): # case 1: we include the number in our set include = float('inf') if t > 0: include = ( best_unfairness[i - 1][t - 1] + n * (i - t) - n * ((size - i) - (take_num - t)) ) # case 2: we just don't dont = float('inf') if best_unfairness[i - 1][t] != float('inf'): dont = ( best_unfairness[i - 1][t] + n * t - n * (take_num - t) ) best_unfairness[i][t] = min(include, dont) print(best_unfairness[size][take_num]) ```