Description
P1) Given the following graph with 2n vertices. Design a dynamic program that runs in polynomial
time and outputs the number of independent sets of this graph. For example, if n = 2 you
n
should output 7. See below for all these 7x independent sets when n = 2,
P2) You have just learned wall climbing. The wall that you are practicing on is n + 1 squares tall
and k +1 squares wide. The bottom left square is at (0, 0) and the top right is at (k, n). There
are two ladders on this wall one is from (z1, 0) all the way to (z1, n) and the other from (z2, 0)
all the way to (z2, n). You can assume 0 ≤ z1 < z2 ≤ k.
Your friend has hanged two coins in every row of this wall; say the coins at row i are located
at (xi,i),(yi,i) where 0 ≤ xi < yi ≤ k for all i. You start at (0, 0) and you want to collect
all coins as fast as possible. In each step, you either go left, go right, or if you are on the
ladder you can go up, but if you go up you cannot come back down; each of these moves take 1
time-step. Design an algorithm that runs in time polynomial in n, k and outputs the smallest
number of time-steps you need to collect all coins.
P3) You are given a tree T where every node i has weight wi ≥ 0. Design a polynomial time
algorithm to find the weight of the smallest vertex cover in T. For example, suppose in the
following picture wa = 3, wb = 1, wc = 4, wd = 3, we = 6. Then, the minimum cost vertex
cover has nodes a, b with weight 3 + 1 = 4.
a
b c
d e
P4) Suppose we have received a large rectangular marble slab of size W × H and we want to cut
the slab to obtain rectangular marble plates of sizes W1 × H1, W2 × H2, . . . , Wn × Hn. Any
6-1
piece of marble (the slab or the plates cut from it) can be cut either horizontally or vertically
into two rectangular plates with integral widths and heights, cutting completely through that
piece. This is the only way to cut pieces and pieces cannot be joined together.
Task Description Day-2
IOI 2004
Athens Version 1.1
Greece phidias
21.09.04 Page 1 of 2 phidias
Phidias
PROBLEM
Famous ancient Greek sculptor Phidias is making preparations to build another marvelous
monument. For this purpose he needs rectangular marble plates of sizes W1 × H1, W2 ×
H2, …, WN × HN.
Recently, Phidias has received a large rectangular marble slab. He wants to cut the slab to
obtain plates of the desired sizes. Any piece of marble (the slab or the plates cut from it) can
be cut either horizontally or vertically into two rectangular plates with integral widths and
heights, cutting completely through that piece. This is the only way to cut pieces and pieces
cannot be joined together. Since the marble has a pattern on it, the plates cannot be rotated:
if Phidias cuts a plate of size A × B then it cannot be used as a plate of size B × A unless A =
B. He can make zero or more plates of each desired size. A marble plate is wasted if it is
not of any of the desired sizes after all cuts are completed. Phidias wonders how to cut the
initial slab so that as little of it as possible will be wasted.
As an example, assume that in the figure below the width of the original slab is 21 and the
height of the original slab is 11, and the desired plate sizes are 10 × 4, 6 × 2, 7 × 5, and 15 ×
10. The minimum possible area wasted is 10, and the figure shows one sequence of cuts
with total waste area of size 10.
Your task is to write a program that, given the size of the original slab and the desired plate
sizes, calculates the minimum total area of the original slab that must be wasted.
INPUT
The input file name is phidias.in. The first line of input contains two integers: first W,
the width of the original slab, and then H, the height of the original slab. The second line
contains one integer N: the number of desired plate sizes. The following N lines contain the
desired plate sizes. Each of these lines contains two integers: first the width Wi and then the
height Hi of that desired plate size (1 ≤ i ≤ N).
OUTPUT
The output file name is phidias.out. The file is to contain one line with a single integer:
the minimum total area of the original slab that must be wasted.
10 4 10 4
6 2 6 2 6 2
7 5 7 5 7 5
Since the marble has a pattern on it, the plates cannot be rotated: if a plate of size A × B
is cut, then it cannot be used as a plate of size B × A unless A = B. We can make zero or
more plates of each desired size. A marble plate is wasted if it is not of any of the desired sizes
after all cuts are completed. The question is how to cut the initial slab so that as little of it
as possible will be wasted.
As an example, assume that original slab is 21 × 11 and the desired plate sizes are 10 × 4, 6 ×
2, 7 × 5, and 15 × 10. The minimum possible area wasted is 10, and the figure (below) shows
one sequence of cuts with total waste area of size 10. Design an algorithm that runs in time
polynomial in n, W, H that outputs the minimum possible waste area.
P5) Extra Credit: Given a sequence of positive numbers x1, . . . , xn and an integer k, design a
polynomial time algorithm that outputs
�
S∈(
n
k)
�
i∈S
xi,
where the sum is over all subsets of size k.
6-2
