Author: Abhishek Dhanraj
Tester: Ajinkya Kharosekar
Editorialist: Ajinkya Kharosekar
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
DP, Recursion.
PROBLEM:
Here we have to empty the shelf by either removing k columns or rows from current m rows and n columns, where k is GCD of m and n. We have to find minimum possible steps required.
QUICK EXPLANATION:
Stuck at a particular moment which to remove - rows or columns ?? Try both my friends…
EXPLANATION:
Clearly, this problem can be solved by DP or Recursion with memoization technique. Here, we can either remove k columns from n columns or k rows from m rows. i.e. after each step -
n = n - k or m = m - k . (k is GCD of m,n)
For minimum possible steps, we will check out both the possibilities and take minimum of those two. We will also store the values in 2x2 matrix DP such that the DP[i][j] will store the minimum steps required to remove i rows and j columns.
Time Complexity:
Worst case - O(m*n)
Solutions:
Setter's Solution
#include <bits/stdc++.h>
#include <algorithm>
#define ll long long
#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
int const N=1001;
using namespace std;
int dp[N][N];
int main(){
fast_io;
int t;
cin >> t;
while(t--){
int n,m;
cin>>n >> m;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int common= __gcd(i,j);
if(common == i || common == j)
dp[i][j]=1;
else{
dp[i][j]=min(dp[i-common][j],dp[i][j-common]) + 1;
}
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#include <algorithm>
#define ll long long
#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
int const N=1001;
using namespace std;
int dp[N][N];
int main(){
fast_io;
int t;
cin >> t;
while(t--){
int n,m;
cin>>n >> m;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int common= __gcd(i,j);
if(common == i || common == j)
dp[i][j]=1;
else{
dp[i][j]=min(dp[i-common][j],dp[i][j-common]) + 1;
}
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}