Here is my approach for the question 2005C - Lazy Narek
I have made my 2 DP Functions and Memoized both of them
I have used 0/1 Knapsack approach in both DPs (Please Tell Me about the Error in the Logic Guys)
#include <bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int, char> narek = {{0, 'n'}, {1, 'a'}, {2, 'r'}, {3, 'e'}, {4, 'k'}};
map<pair<int, int>, int> memo_dp1;
map<tuple<int, int, int>, int> memo_dp2;
int dp1(vector<string>& a, int i, int found, int n, int m);
int dp2(string& word, int j, int found, int m, vector<string>& a, int i, int n);
void solve();
int32_t main()
{
int t;
cin >> t;
while (t--)
{
memo_dp1.clear();
memo_dp2.clear();
solve();
}
}
void solve()
{
int n, m;
cin >> n >> m;
vector<string> a(n);
for(string& s: a) cin >> s;
cout << dp1(a, 0, 0, n, m) << "\n";
}
int dp1(vector<string>& a, int i, int found, int n, int m)
{
if(i >= n) return -found;
auto key = make_pair(i, found);
if(memo_dp1.find(key) != memo_dp1.end()) return memo_dp1[key];
int exclude = dp1(a, i + 1, found, n, m);
int include = dp2(a[i], 0, found % 5, m, a, i, n);
return memo_dp1[key] = max(include, exclude);
}
int dp2(string& word, int j, int found, int m, vector<string>& a, int i, int n)
{
if(j >= m)
{
return dp1(a, i + 1, found, n, m);
}
auto key = make_tuple(i, j, found);
if(memo_dp2.find(key) != memo_dp2.end()) return memo_dp2[key];
int include = 0;
int exclude = dp2(word, j + 1, found, m, a, i, n);
if(word[j] == 'n' || word[j] == 'a' || word[j] == 'r' || word[j] == 'e' || word[j] == 'k')
{
if(narek[found % 5] == word[j])
{
if((found + 1) % 5 == 0) include = 5;
include += dp2(word, j + 1, (found + 1) % 5, m, a, i, n);
}
exclude -= 1;
}
return memo_dp2[key] = max(include, exclude);
}
It's not knapsack. Take a look at the editorial.
I think his approach works but it just needs a little bit fixing That’s All See Narek Has 2 Options Per String In This Question: Two Select A String Or Not And Per Selected String Also Narek Has Two Options: Two Select A Character in ‘narek’, If it is the character he wants, he could select it or exclude it, exclusion accounts for ChatGPTs score thus the guy has done -1 in his code
please consider that a question can have multiple solutions
why do all the problems these days take 100+ lines
123gjweq2 Bro u are an expert you should have a typing speed on atleast 40 words per minutes, minimum. You’ll take just 2.5 minutes to write 100 lines of code