Connection Status:
Competition Arena > PlacingPieces

PlacingPieces

SRM 316 · 2006-08-19 · by _efer_

SRM 316 · 2006-08-19 · by _efer_ · Dynamic Programming, Search
Class Name: PlacingPieces
Return Type: int
Method Name: optimalPlacement
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

You have received a new puzzle as a gift. It consists of a board and several pieces of various lengths. Each piece has the same width as the board. The goal of the game is to place the least number of pieces on the board such that no other unused piece can be added legally. Pieces must not hang over the edge of the board or be twisted at an angle. Each piece must be oriented so that its width is parallel to the width of the board. Pieces must not overlap, but their edges may touch. Keep in mind that distances between pieces or the distances between pieces and the edges of the board are not necessarily integer numbers. See the examples for further clarification.

You will be given an int L, the length of the board, and a int[] pieces containing the lengths of the pieces. Create a method optimalPlacement that returns the number of pieces placed on the board that allows you to solve the puzzle.

Constraints

  • L will be between 1 and 1000, inclusive.
  • pieces will contain between 1 and 30 elements, inclusive.
  • Each element of pieces will be between 1 and 100, inclusive.
Examples
0)
9
{1, 8}
Returns: 1

You can place both pieces on the board and leave no space on it. However, there is a better solution as depicted below. Place only the second piece on the board, and leave a little space between it and the left and right edges of the board, so that the first piece can't fit:

1)
36
{1, 1, 5, 5, 5}
Returns: 4

If we place all three pieces with length 5 on the board, we will have no choice but to also place the smallest two pieces. However, if you place only two of them and the two smallest pieces, you can leave spaces on the board that are smaller than the length of the remaining piece.

2)
37
{1, 1, 5, 5, 5}
Returns: 5

You cannot leave any piece out here.

3)
18
{2, 2, 2, 9, 9, 10}
Returns: 2

Sometimes it is better to not place the piece with the highest length.

4)
1
{2, 3, 4}
Returns: 0

No piece fits on this board.

Submissions are judged against all 137 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PlacingPieces with a public method int optimalPlacement(int L, vector<int> pieces) · 137 test cases · 2 s / 256 MB per case

Submitting as anonymous