PROBLEM STATEMENT
You have a large rectangular piece of chocolate. As usual, the piece of chocolate is divided into
squares.
The piece you have is W squares wide and H squares tall.
For the purpose of this problem the squares will be numbered from (1,1) in the upper left corner
to (W,H) in the lower right corner of the chocolate.
You can break the chocolate into smaller rectangular pieces. In each step, you can take one of the
pieces you have, select one of the lines between the squares (either a horizontal or a vertical
one) and break the piece into two new pieces along the line.
A few of the cells are special. Their coordinates are given as vector s sx and sy: for each
i, the square at (sx[i],sy[i]) is special.
You want to eat all special squares and no other squares. Before you can do this, you have to
break the chocolate into several pieces in such a way that each piece either consists of special
squares only, or it consists of non-special squares only.
Compute and return the minimum number of steps needed in order to break the chocolate correctly.
DEFINITION
Class:BreakingChocolate
Method:minSteps
Parameters:int, int, vector , vector
Returns:int
Method signature:int minSteps(int W, int H, vector sx, vector sy)
CONSTRAINTS
-W will be between 1 and 1,000,000,000, inclusive.
-H will be between 1 and 1,000,000,000, inclusive.
-sx will have between 1 and 40 elements, inclusive.
-sy will have the same number of elements as sx.
-Each element in sx will be between 1 and W, inclusive.
-Each element in sy will be between 1 and H, inclusive.
-No two squares described by sx and sy will be equal.
EXAMPLES
0)
3
3
{2}
{2}
Returns: 4
You want the middle square of a 3 x 3 piece of chocolate. Clearly you need to break it at least
four times: once for each edge of the square.
1)
2
2
{1,2}
{2,1}
Returns: 3
You want two opposite corners of a 2 x 2 chocolate. To obtain them, break the chocolate in half,
and then break each of the halves in half again.
2)
10
10
{1}
{1}
Returns: 2
If the desired square is in the corner, fewer steps are necessary.
3)
10
10
{3,5,6}
{5,5,5}
Returns: 6
In this case all the squares you want are in the same row. One optimal strategy is to start by
separating this row from the others (in 2 steps) and then to separate the good squares from the
bad ones (in 4 steps).
4)
3
3
{1,1,1,2,2,3,3,3}
{1,2,3,1,3,1,2,3}
Returns: 4
In this example we want all the squares except for the middle one. This situation is solved in the
same way as Example #0.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any
unauthorized use or reproduction of this information without the prior written consent of
TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.