Hi,
(solution spoilers ahead)
I recently solved the problem "Estimation" from the Chicago Invitational 2012 with a relatively straightforward O(kn2 + n2logn) DP solution. However, it seems that it may be possible to solve this faster, because it's possible to find the median of an arbitrary subarray in close to O(logn) and there are only O(kn) states in the DP. Does anyone have any ideas (maybe Knuth optimisation)?
The problem statement is as follows (from http://serjudging.vanb.org/wp-content/uploads/UC-2012-Problem-Set.pdf):
You have an array A of numbers.
You will partition it into k contiguous sections, which won’t necessarily be of the same size. Then, you’ll use a single number to estimate an entire section. In other words, for your array A of size n, you want to create another array B of size n, which has k contiguous sections. If i and j are in the same section, then B[i]=B[j]. You want to minimize the error, expressed as the sum of the absolute values of the differences (∑|A[i]-B[i]|).
