but somehow it feels like selecting the middle one should be correct. I dont know why. but thats what occurred to me when I solved it!!
On Sep 15, 1:38 pm, Brats <[email protected]> wrote: > Releasing the prisoner nearest to the center may not always be best > solution. For example, consider 100 prisoners with Q as [49,50,51] > > lets consider the prisoners to the left of 49 as set A and the ones on > the right of 51 as set B. > If you release 50 first, you will have to pay bribe to both A and B .. > and then once again to each for releasing 49 and 51 ... hence paying > bribe twice to both A and B. > > But, if you release 50 last, you see that one of these 2 sets needs to > be bribed only once hence drastically reducing the required bribe > amount. > > On Sep 15, 1:24 pm, 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 -~----------~----~----~----~------~----~------~--~---
