user3840069 user3840069 - 2 months ago 16
C++ Question

Cut rectangle in minimum number of squares

I'm trying to solve the following problem:


A rectangular paper sheet of M*N is to be cut down into squares such that:


  1. The paper is cut along a line that is parallel to one of the sides of the paper.

  2. The paper is cut such that the resultant dimensions are always integers.



The process stops when the paper can't be cut any further.

What is the minimum number of paper pieces cut such that all are squares?

Limits: 1 <= N <= 100 and 1 <= M <= 100.

Example: Let N=1 and M=2, then answer is 2 as the minimum number of squares that can be cut is 2 (the paper is cut horizontally along the smaller side in the middle).


My code:

cin >> n >> m;

int N = min(n,m);
int M = max(n,m);
int ans = 0;

while (N != M) {
ans++;
int x = M - N;
int y = N;
M = max(x, y);
N = min(x, y);
}

if (N == M && M != 0)
ans++;


But I am not getting what's wrong with this approach as it's giving me a wrong answer.

Answer

I'd write this as a dynamic (recursive) program.

Write a function which tries to split the rectangle at some position. Call the function recursively for both parts. Try all possible splits and take the one with the minimum result.

The base case would be when both sides are equal, i.e. the input is already a square, in which case the result is 1.

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(i, n) + min_squares(m-i, n)  |  i ∈ [1, m/2] }

    return min { min_hor, min_ver }

To improve performance, you can cache the recursive results:

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // check if we already cached this
    if cache contains (m, n):
        return cache(m, n)

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(i, n) + min_squares(m-i, n)  |  i ∈ [1, m/2] }

    // put in cache and return
    result := min { min_hor, min_ver }
    cache(m, n) := result
    return result

In a concrete C++ implementation, you could use int cache[100][100] for the cache data structure since your input size is limited. Put it as a static local variable, so it will automatically be initialized with zeroes. Then interpret 0 as "not cached" (as it can't be the result of any inputs).

Possible C++ implementation: http://ideone.com/HbiFOH