Cut The Paper

Posted: 8 Jan, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given a paper with dimension N * M. Your task is to find the minimum number of squares in which you can cut the given paper.

Note:

1. Square is a quadrilateral whose all four sides are of equal length.
2. If the given paper is already a square then it is possible to cut the whole square in one move.
Input Format:
The first line of the input contains an integer T, denoting the number of test cases.

The first line of each test case consists of two space-separated integers N and M denoting the dimensions of the given paper, in a separate line.
Output Format:
For each test case return, the minimum number of squares in which you can cut the given paper.
Note:
You don't have to print anything, it has already been taken care of. Just Implement the given function.
Constraints:
1<= T <= 50
1<= N, M <= 150

Time Limit: 1 sec.
Approach 1
  • In order to try all possible ways to cut the paper, we make a recursive function that will compute the answer for the given (N, M).
  • The base condition for this function will be when N==M (which means it is already a square), we will return 1 in such a case.
  • In the case where the base condition is not satisfied, we will try out all possible ways to cut the paper horizontally and vertically as follows:
    • For trying all possible horizontal cuts, we will find the answer for paper with dimensions (N-x, M) and (x, M) for x in the range from 1 to N/2(both inclusive) with the help of the same recursive function. And the summation of results from both calls for a given x will give one of the possible solutions.
    • For trying all possible vertical cuts, we will find the answer for paper with dimensions (N, M-x) and (N, x) for x in the range from 1 to M/2(both inclusive) with the help of the same recursive function. And the summation of results from both calls for a given x will give one of the possible solutions.
  • Taking the minimum of all possible solutions for given (N, M) will give the desired solution.
  • One thing to observe here is that we can reach a state more than once for eg. the state (N-2, M-1) can be reached from (N-2, M) and (N-1, M-1).
  • In order to avoid recomputation of solutions for a given state, we can use a 2-Dimensional table to store the results for a state, so that we can use those results for future calls to that state.
  • There is one edge case for paper with dimension 13*11. Our algorithm will give 8 as the answer but since we can cut the paper in 6 squares only as shown in the following picture.

                                

 

Eg. For paper with dimension (2, 3), the algorithm will work as follows:

  • HELPER(2, 3)
    • HELPER(1, 3)
      • HELPER(1,2)
        • HELPER(1,1)
          • Return 1                                          ....(1)
        • HELPER(1,1) // already computed
          • Return 1                                          ....(2)
        • Return 2 (sum of (1) + (2))                        ….(3)
      • HELPER(1,1) // already computed
        • Return 1                                                    ….(4)
      • Return 3 (sum of (3) + (4))                                   ….(5)
    • HELPER(1, 3) // already computed
      • Return 3                                                               ….(6)
    • HELPER(2, 1)
      • HELPER(1,1) // already computed
        • Return 1                                                    ….(7)
      • HELPER(1,1) // already computed
        • Return 1                                                    ….(8)
      • Return 2 (sum of (7) + (8))                                   ….(9)
    • HELPER(2,2)
      • Return 1 // N==M                                                 ….(10)
    • Return 3 // min(sum of (5) + (6), sum of (9,10))
Try Problem