Check this out.
vector<vector<int>> dp(n+1,vector<int>(K+1));
for(int i=1;i<=n;i++){
for(int k=0;k<=K;k++){
int mx = 0;
for(int j=1;j<i;j++){
if(a[i-1] == a[j-1])
mx = max(mx,dp[j][k]);
else if(k > 0)
mx = max(mx,dp[j][k-1]);
}
dp[i][k] = 1 + mx;
}
}
I tried recursive + memo but was unable to reduce the states to avoid tle 
Can someone tell me why this code is giving wrong answer
I have tried similar approach in editorial
it is passing the sample cases and some other cases.
int main(){
int t;
cin>>t;
while(tâ){
int n,k;
cin>>n>>k;
int a[n];
unordered_map<int,int>lastseen;
for(int i=0;i<n;i++){
cin>>a[i];
lastseen[a[i]]=-1;
}
int dp[n][k+1];
//dp states are index and adjacent difference
//dp[index][difference] represents max length possible till this index
//dp[1][2] means till index 1 the adjacent difference of 2 are 1,2,3 or 1,2,1
for(int i=0;i<n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=-1;
}
}
dp[0][0]=1;
lastseen[a[0]]=0;
for(int i=1;i<n;i++){
for(int j=0;j<=k;j++){
if(j>i){
break;
}
if(j==0){
if(lastseen[a[i]]==-1){
dp[i][j]=dp[i-1][j];
}
else{
int idx=lastseen[a[i]];
dp[i][j]=max({dp[i-1][j],dp[idx][j]+1});
}
}
else if(lastseen[a[i]]==-1){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+1);
}
else{
int idx=lastseen[a[i]];
dp[i][j]=max({dp[i-1][j],dp[idx][j]+1,dp[i-1][j-1]+1});
}
}
lastseen[a[i]]=i;
}
int ans=0;
for(int j=0;j<=k;j++){
ans=max(ans,dp[n-1][j]);
}
//Remove this comment to print dp
// for(int i=0;i<n;i++){
// for(int j=0;j<=k;j++){
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
cout<<ans<<endl;
}
}
Why canât codechef provide the testcases where solution giving wrong answer after contest over.
I am kind of a newbie to this field. Can you please tell or share the chart, if there is any, how it is decided that how many test cases should take how much time?
When it would give TLE and when it wouldnât.
Thankyou.
10^7 operations can be executed in 1 sec. More than this will give TLE.
but here 10^8 is accepted because of weak test cases.
Why codechef editorials are harder than its problem statements itself?
When will the video editorial of this problem be available?
Can anyone explain me slow solution here, I am unable to understand it
I made arrays global and it got accepted ,i donât understand why it happens only on codechef ,that you think you did something wrong and waste time on it but at the end you realize it was not wrong.
Has anyone solved it using memoization ? if yes, then can you please share your approach/solution ?
I too was thinking of some O(N) approach initially.
CodeChef: Practical coding for everyone (basic idea)
CodeChef: Practical coding for everyone(with some changes)
Can anyone tell what is wrong in the approach ? I am following notion of standard LIS not exactly but kind of⌠I am maintaining length[] array for length of subsequence and distinct[] array for number of different adjacent elementsâŚ
Why do we need pref_max(i,k)? Why donât we just keep the longest k-beautiful subsequence until i position in f( i, k). We can get it by f(i , k)=max( f(i-1, k-1) , f(last( i ), k ) ) +1.
How are Leetcode editorials better? Keep in mind that Codechef has much harder problems.
Please donât talk nonsense about the weak tests and bad constraints. Solutions that compute up to 4 \cdot 10^8 operations can easily pass in one second, so 10^8 is nowhere near tight with a problem of these constraints. O(N \log N) passes for N \leq 10^7 easily in c++, giving issues in java/python, so itâs not weird at all why a TNK passes.
excuse me bro if you understand the editorial can you please explain it with a simple example
especially reducing the transitions part containing the two bullet points
thank you 
why not video tutorial is not out yet?? Eagerly waiting. I have tried with recursion and memo but tle
occurred.