The key to solving this problem is observing that we can split a sorted array containing positions of the clumps into three parts, considering the start position to contain a clump for coding simplicity:
Logically, Bessie will always be just after 1st part or just before 2nd part. This leads us to a Dynamic Programming solution using a state (SubProblem) of position of two points that divides the array to 3 parts and where is Bessie (just after 1st part or just before 2nd part).We try in each state to go to eat the first one to left or first one to the right.
Thus the algorithm has memory and complexity O(N^2) or more precisly N*N*2. Below is my memoised recursive solution:
#include<cstdio> using namespace std; FILE *in = fopen ("ontherun.in","r"); FILE *out = fopen ("ontherun.out","w"); int best[1009][1009][2]; int arr[1009]; int n,l; int solve (int p1,int p2,int d) { int &ret=best[p1][p2][d]; if(p1==0 && p2==n) return 0; if(ret!=-1) return ret; ret=1<<30; int u,p; if(d==0) p=p1; else p=p2; if(p1!=0) { u=solve (p1-1,p2,0)+abs(arr[p]-arr[p1-1])*(p1+(n-p2-1)); if (u<ret) ret=u; } if(p2!=n) { u=solve(p1,p2+1,1)+abs(arr[p]-arr[p2+1])*(p1+(n-p2-1)); if(u<ret)ret=u; } return ret; } int main() { int i, j, k, p1, p2, ans; memset (best,-1,sizeof(best)); fscanf (in, "%d %d", &n, &l); for(i=0;i<n;i++) fscanf(in,"%d",&arr[i]); arr[n]=l; n++; sort(arr,arr+n); for(i=0;i<n;i++) if(arr[i]==l) { p1 = p2=i; break; } ans = solve (p1,p2,0); fprintf (out,"%d\n",ans); return 0; }
Topcode and IOI champ Tomek Czajka contributed this very helpful analysis:
For simplicity, we can add Bessie's initial position to the set of clumps of grass. Sort the clump location, including the starting position.
This problem can be solved using Dynamic Programming (or equivalently, memoization). The trick is to define a recursive function on a small range of arguments. Our function is: for each contiguous subsegment of clumps containing the initial position, compute the minimum total staleness that Bessie can achieve for that segment, ending on the leftmost or rightmost clump respectively (call it L(a,b) and R(a,b)). Now we can give a recursive formula - to eat the segment (a,b) and finish on the left end, we have to eat all the clumps (a+1,b) first:
Similarly for R(a,b). There are O(n^2) values to compute, and the final answer is min(L(1,n),R(1,n)). We can use dynamic programming to compute all these values, or we can implement the recursion directly, memoizing the computed values. Both approaches will give an O(n^2) solution.