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