PROBLEM LINK:
Author: Swaraj Shelavale
Tester: Ram Agrawal
Editorialist: Yogesh Deolalkar
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, Math
PROBLEM:
Chef was bored at home due to lockdown. So he watched the ”SQUID GAME” web series with his friend. After watching web series they decided to play a game. Chef’s friend gave a task to chef. If chef is unable to complete
the task, he will be eliminated.
The game rules are as follows:
Chef is given a cookie with a string S written on it. Chef has to cut some letters from that cookie such that the cookie will convert into Good Cookie.
A good cookie is a cookie that has a palindromic string.
Chef can delete at most K letters from cookie such that cookie will be converted into Good Cookie.
If chef fails to convert the cookie into a good cookie within at most K deletions then Chef will be eliminated.
Your task is to check whether chef will be eliminated or not?
EXPLANATION:
This question is a DP problem which is basically a variation of Edit Distance problem.
The idea is to find the longest palindromic subsequence of the given string. If the difference between longest palindromic subsequence and the original string is less than equal to k, then the string is k-palindrome else it is not k-palindrome.
Longest palindromic subsequence of a string can easily be found using LCS. Following is the two step solution for finding longest palindromic subsequence that uses LCS.
1.Reverse the given sequence and store the reverse in another array say rev[0…n-1]
2.LCS of the given sequence and rev[] will be the longest palindromic sequence.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
int LCS(string X,string Y){
int n=X.size(), m=Y.size();
int t[n+1][m+1];
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++){
if(i==0||j==0)
t[i][j]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(X[i-1]==Y[j-1])
t[i][j]= 1+t[i-1][j-1];
else
t[i][j]= max(t[i-1][j],t[i][j-1]);
}
return t[n][m];
}
void solve()
{
string s;
cin>>s;
int k;
cin>>k;
string t = s;
reverse(t.begin(),t.end());
int ans = LCS(s,t);
// cout<<ans<<endl;
if(s.size()-ans <= k)cout<<“NO\n”;
else cout<<“YES\n”;
}
signed main(){
fast;
int t;
cin>>t;
while(t–){
solve();
}
return 0;
}