BOB AND SQUARES

Author: @somashekhar001
Tester: @somashekhar001
Editorialist: @somashekhar001

DIFFICULTY:

MEDIUM

PREREQUISITES:

DYNAMIC-PROGRAMMING

PROBLEM:

you have to cut a rectangle shaped glass to square shaped glasses till no rectangle shaped glass will left in minimum cuts.

EXPLANATION:

consider a rectangle a × b if a=b then it is a square no need to cut ( 0 cuts ) else we need to make cut either horizontally or vertically .assume we make it horizontally ,then we can cut at any position 1,2,…,b-1.if we cut at position k ,we left with 2 pieces a × k and a × b-k then we can look up the number of moves to reduce these squares in the dp array we loop over all possibilities k and take the best one .similarly for vertical cuts.

The complexity is O(a^2 * b + a * b^2).

SOLUTIONS:

 #include<bits/stdc++.h>

 using namespace std;


 int solve(int a,int b)
    
 {

    // creation of dp array for saving minimum number of cuts.

     int dp[a+1][b+1]; 

    for(int i=0;i<=a;i++) {
    for(int j=0;j<=b;j++){
   // if condition is for squares with 0 cuts.   
   
    if(i==j) {
          dp[i][j]=0;
      }
    else{

      dp[i][j]=1e4;
 // traversing the all possibilities of horizontal cuts and saving which is optimal.
      for(int k=1;k<i;k++){
          dp[i][j]=min(dp[i][j],1+dp[i-k][j]+dp[k][j]);
      }
 // traversing the all possibilities  of vertical cuts and saving which is optimal. 
      for(int k=1;k<j;k++){
          dp[i][j]=min(dp[i][j],1+dp[i][j-k]+dp[i][k]);
      }

  }
  
 }
}
// returning  the optimal cuts needed to cut rectangle a × b.
 return dp[a][b];
}
int main()
{
 int a,b,t,ans;cin>>t;
  while(t--){
 cin>>a>>b;
 ans=solve(a,b);
 cout<<ans<<endl;
}
return 0;
}