Setter : Ekansh Saxena
Tester: Ayush Srivastava
Editorial: Adarsh Kumar Shrivastav
Difficulty:
Medium
Prerequisite:
dynamic-programming, , implementation
Explanation & Algorithm:
As we have to do two things in this problem. First, to maximize the length of selected subsequence and second to minimize the value of xor of G and H.
To maximize len(G), we have to use the principle of dynamic programming to find longest common subsequence of two binary strings.
Time complexity: O(N*M)
Space complexity: O(N*M)
Solution:
Setter's Code
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int helper(int i, int j, string &s, string &t, vector<vector> &dp){
// Base Case.
if (i == -1 || j == -1){
return 0;
}
// Check if the current subproblem has already been solved.
if (dp[i][j] != -1){
return dp[i][j];
}
// Check if 'ith' character in 's' is same as 'jth' character in 't'.
if (s[i] == t[j]){
return dp[i][j] = 1 + helper(i - 1, j - 1, s, t, dp);
}
return dp[i][j] = max(helper(i - 1, j, s, t, dp), helper(i, j - 1, s, t, dp));
}
int maxFXII(string &s, string &t, int n, int m){
// Create ‘DP’ table.
vector<vector> dp(n + 1, vector(m + 1, -1));
return 2 * helper(n - 1, m - 1, s, t, dp);
}
int main() {
ll t;
cin>>t;
while(t–){
ll n,m;
string s,t;
cin>>n>>m;
cin>>s>>t;
cout<<maxFXII(s,t,n,m)<<endl;
}
return 0;
}
Tester's Code
#include
using namespace std;
int main(){
int t;
cin >> t;
while (t–){
int n, m;
cin >> n >> m;
string s1, s2;
cin >> s1 >> s2;
int maxLen[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= n; i++){
for (int j = 0; j <= m; j++)
if (i == 0 or j == 0)
maxLen[i][j] = 0;
else{
if (s1[i - 1] == s2[j - 1])
maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
else
maxLen[i][j] = max(maxLen[i - 1][j], maxLen[i][j - 1]);
}
}
cout << 2 * maxLen[n][m] << “\n”;
}
return 0;
}