Here is the logic that I tried to use but failed to solve the problem: array P is array of prison cells numbered from 0..N-1 array Q is array of prisoners to be released in order given in input (sorted order)
First find out the the element in Q that is nearest to center of N. for example if there are 10 prison cells (index 0..9) and Q contains [3,6,9] then 6 is nearest to center of P (at index 5) release prisoner 6 first that means we need to bribe 4 prisoners in left side + 5 prisoners in right side. there is now an empty cell at index 5. So we now have two subproblmes P1=0..4 and P2=6..9 with Q=[3,9] solve two subproblems recursively return 4+5+answer(P1,Q) + answer(P2,Q) But this logic returned 36 for the second test case instead of 35. I couldn't figure out the problem in time. I need to know if the logic is worth investigating more. Regards, KeJo On Sep 15, 2:31 am, Luke Pebody <[email protected]> wrote: > Here's my solution in Pascal: > > program hello; > const > coder = 'bozzball'; > > var > N,i,j,P,Q,d,k : integer; > a : array[0..101] of LongInt; > b : array[0..101,0..101] of LongInt; > > begin > readln(N); > for i := 1 to N do > begin > readln(P,Q); > for j := 1 to Q do > read(a[j]); > a[0] := 0; > a[Q+1] := P+1; > for j := 0 to Q do > b[j][j+1] := 0; > for d := 2 to Q+1 do > for j := 0 to (Q+1-d) do > begin > b[j][j+d] := b[j][j+1] + b[j+1][j+d]; > for k := j+2 to j+d-1 do > if (b[j][j+d] > (b[j][k] + b[k][j+d])) then > b[j][j+d] := b[j][k] + b[k][j+d]; > b[j][j+d] := b[j][j+d] + (a[j+d]-(a[j]+2)); > end; > writeln('Case #', i, ': ', b[0][Q+1]); > end; > end. > > On Mon, Sep 14, 2009 at 10:29 PM, Luke Pebody <[email protected]> wrote: > > To solve the small case, you can simply try every possible ordering of > > the at most 5 prisoner numbers. For any input case there are at most > > 120 attempts to try. > > > While I was coding this, I noticed that after any particular prisoner > > is released, the prisoners with a lower number and the prisoners with > > a higher number cannot affect each other. Therefore, each > > step breaks the problem down into *smaller subproblems* - the clear > > sign that a problem could be handled by Dynamic Programming. > > > To that end, suppose that (as in the question), there are P prisoners, > > and there are Q prisoners to be released, 0 < A_1 < ... < A_Q <= P. > > > To simplify the arguments, set A_0=0 and A_{Q+1}=P+1. (Suppose there > > were prisoners on either side of the original P prisoners that have > > already been released). > > > Then for 0 <= i < j <= Q+1, define ans_{i,j} to be the minimum > > possible total bribe to release prisoners A_{i+1}, ..., A_{j-1} given > > that prisoners A_i and A_j have been released. > > > Then the answer we are looking for is ans_{0,Q+1}. > > > To come up with an expression for ans_{i,j}, suppose that you first > > release prisoner A_k where i < k < j. This release costs (A_j-A_i)-2 > > in bribes. After this release, cell A_k is empty. > > Therefore, when you release any prisoners with numbers less than A_k, > > you will not have to bribe any prisoners whose cell number is more > > than A_k or vice versa. > > Thus, (and this is the vital point), the releases of prisoners less > > than A_k have no effect on the cost of the releases of prisoners more > > than A_k or vice versa. > > > Thus, the minimum possible cost to release all of the prisoners > > A_{i+1}, ..., A_{j-1}, given that you start with A_k is: > > * (A_j-A_i)-2 (the cost in bribes of releasing prisoner A_k) > > * ans_{i,k} (the cost to release the prisoners between A_i and A_k > > exclusive) > > * ans_{k,j} (the cost to release the prisoners between A_i and A_k > > exclusive). > > > To summarise: if i + 2 <= j, ans_{i,j} = (A_j-A_i)-2 + min(i < k < j) > > ans_{i,k}+ans_{k,j}. If j = i+1, ans_{i,j} = 0 (there are no prisoners > > between A_i and A_j to release). > > > The algorithm goes as follows: > > Let ans be a 2-dimensional array of size Q+2 by Q+2, initially filled with > > 0's. > > For di in the range 2 to Q+1 (inclusive): > > For i in the range 0 to Q+1-di (inclusive): > > Set j = di+i > > Set ans[i][j] = ans[i][i+1] + ans[i+1][j] > > For k in the range i+2 to j-1 (inclusive): > > If ans[i][j] > ans[i][k] + ans[k][j]: > > Set ans[i][j] = ans[i][k] + ans[k][j] > > (Now ans[i][j] = min(ans[i][k]+ans[k][j] for i < k < j)) > > Increment ans[i][j] by (A_j-A_i)-2 (where A_0=0, A_{Q+1}=P+1 and > > A_1, ..., A_Q are the numbers entered) > > The answer is Ans_{0,Q+1}. > > > In particular, for case #2: where P = 20, Q = 3 and A_1 = 3, A_2 = 6, > > A_3 = 14 (so A_0 = 0 and A_4 = A_{Q+1} = P+1 = 21). > > > ans_{0,1} = 0 > > ans_{1,2} = 0 > > ans_{2,3} = 0 > > ans_{3,4} = 0 > > ans_{0,2} = (A_2-A_0)-2+min([ans_{0,1}+ans_{1,2}]) = 4 > > ans_{1,3} = (A_3-A_1)-2+min([ans_{1,2}+ans_{2,3}]) = 9 > > ans_{2,4} = (A_4-A_2)-2+min([ans_{2,3}+ans_{3,4}]) = 13 > > ans_{0,3} = (A_3-A_0)-2+min([ans_{0,1}+ans_{1,3},ans_{0,2}+ans_{2,3}]) > > = 12 + min(9,4) = 16 > > ans_{1,4} = (A_4-A_1)-2+min([ans_{1,2}+ans_{2,4},ans_{1,3}+ans_{3,4}]) > > = 16 + min(13,9) = 25 > > ans_{0,4} = > > (A_4-A_0)-2+min([ans_{0,1}+ans_{1,4},ans_{0,2}+ans_{2,4},ans_{0,3}+ans_{3,4}]) > > = 19 + min(25,17,16) = 35, > > giving the answer 35 as stated in the problem. > > > On Mon, Sep 14, 2009 at 9:57 PM, Nikhil Mahajan <[email protected]> wrote: > > >> How did you solve this question? Can someone please explain an > >> algorithm that could be used? > > >> Thanks. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
