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;
}