In the notes they say why it is 35 and not 36, you have to release prisoner 14 first, and not 6. I don't have a proof, but I don't think it can be solved with a greedy algorithm. And as a general rule, I don't recommend going for greedy unless you have some proof(at least an informal one) that it works or if the greedy algorithm is your last hope and didn't find anything else. And as Luke said, if you realized each step was giving you two smaller sub-problems, chances are you should try to find a dynamic programming solution for the problem. Specially when the limits are small enough (100 for Q in this case).
Carlos Guía On Tue, Sep 15, 2009 at 3:54 AM, KeJo <[email protected]> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
