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
-~----------~----~----~----~------~----~------~--~---
