Indian Computing Olympiad

Dynamic Programming→Phidias (IOI 2004)

Phidias is a sculptor who has a large rectangular slab of marble of size W×L (1 ≤ W,L ≤ 600). He wants to cut out rectangular tiles of specific sizes (a1,b1), (a2,b2) … (ak,bk). He is willing to take as many of each type as are available. The marble slab has a pattern and so tiles cannot be rotated. This means that it is not acceptable to produce a tile of (bi,ai) instead of (ai,bi).

To cut a slab of marble, he can can make a full horizontal or vertical cut across the slab at an integer point.

After making a sequence of cuts, Phidias will arrive at some pieces of marble that are wasted — they cannot be cut down to any of the desired tiles.

Find a sequence of cuts that will minimize the wastage.

Let Wastage(x,y) denote minimum wastage for x by y marble piece.

           ----------------
          |                |
        x |                |
          |                |
           ----------------
                   y
      

If we cut vertically at yi, we get

• Wastage(x,y) = Wastage(x,yi) + Wastage(x,y-yi).

Similarly, if we cut horizontally at xj, we get

• Wastage(x,y) = Wastage(xj,y) + Wastage(x-xj,y).

The choices available to us are to cut vertically at yi for 1 ≤ yi < y or horizontally at xj for 1 ≤ xj < x. We check all of these and choose the minimum.

Initially:

• Wastage(x,y) = 0, if (x,y) matches some (ai,bi)
                        = x*y, otherwise (this will be updated later)

Update:

• Wastage(x,y) = min {
• Wastage(x,y), /* Currently computed quantity */
• min_{0<j<x} Wastage(j,y) + Wastage(x-j,y), /* Horizontal cut at j */
• min_{0<i<y} Wastage(i,y) + Wastage(x-i,y), /* Vertical cut at i */

}

Alternatives:

Initialize only

• Wastage(x,y) = 0, if (x,y) matches some (ai,bi)
• Wastage(1,1) = 1

If (x,y) is completely wasted, all cuts will eventually create a collection of (1,1) rectangles which add up to x*y.

Can optimize a bit by adding

• Wastage[x,y] = x*y whenever no tile fits, that is (x < min xi) or (y < min yj)