I have been working on the Calvin’s Game (CodeChef: Practical coding for everyone) for 8 hours. I have tried a lot, got close many a times but could not reach to the correct solution. Please help. Any well commented solution, explanation of the approach using dynamic programming, or using recursion is highly appreciated (and highly needed).
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long int n,k,ans=-10000000;
cin>>n>>k;
long long int phase1[n];
long long int phase2[n];
int seq[n];
for(int i=0;i<n;i++){
cin >> seq[i];
}
//phase1[i] is the score if we go forward till i.
//phase2[i] is the score if we reverse from i
phase1[k-1]=0;
//It is 0 where we start.
phase1[k]=seq[k];//there is only one way to go here
for(int i=k+1;i<n;i++){
phase1[i]=max(phase1[i-2]+seq[i],phase1[i-1]+seq[i]);
//dp, either come from i-1 or i-2
}
phase2[0]=seq[0];//We don't actually need to go backwards
//The dp relation is the same
//if 5->3->2->1 is valid, then 1->2->3->5 is valid
phase2[1]=seq[0]+seq[1];//only one way
for(int i=2;i<n;i++){
phase2[i]=max(phase2[i-1]+seq[i],phase2[i-2]+seq[i]);
//compare coming from i-1 or i-2
}
for(int i=k-1;i<n;i++){
long long int thisans=phase1[i]+phase2[i]-seq[i];
//The thing is we are adding seq[i] twice
//so we subtract it once
//to get the actual score of stopping here
//like 3->4->5
//and 1->2->4->5
//so seq[5] is added twice
//if you remember how we structured our
//phase2 dp
ans=max(ans,thisans);
//just take max of stopping at all positions
}
/* for(int i=0;i<n;i++){
cout<<phase1[i]<<" ";
}
cout <<"\n";
for(int i=0;i<n;i++){
cout<<phase2[i]<<" ";
}
cout <<"\n";
*/
cout <<ans<<"\n";
}
2 Likes
Thank you so much ! 
If you want to check how well you’ve understood it, Try doing it in only 1 loop.
Even I had come up with the DP relation, DP[i] = seq[i] + max(DP[i-1], DP[i-2]), but the thing is that I couldn’t satisfy myself that it really works and how it works, my mind kept questioning its own idea. And then finally when I did decide to just go with this relation, I committed implementation errors.
I think the major problem is my poor (very poor) understanding of DP and recursion. Do you have any suggestions regarding how can I improve upon these? Any good problems to practice, or write-ups to read?
If you are questioning yourself, you don’t understand the mindset to prove a dp relation. The reasoning is that given the correct answer for all smaller cases, can you find the answer for this case.
What happens is that when I try to prove the correctness using this logic I simply get into a recursive trap, I start thinking what if the sub-problem is not what I am thinking and something else, are my DP states correct or am I just fooling myself.
Just solve Atcoder dp contest
Link
You’ll realise that whatever feels correct is usually correct.
1 Like
Thanks 
Another solution you can check to reinforce your understanding.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INFL=1E18;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n,k;cin>>n>>k;
vector<int> a(n+5); // define more than n elements to don't worry about out of bounds
for(int i=1;i<=n;++i) cin>>a[i];
vector<ll> dp(n+5,-INFL);
dp[k]=0;
for(int i=k+1;i<=n;++i) {// forward phase
dp[i] = max(dp[i - 1], dp[i - 2]) + a[i];
}
for(int i=n-1;i>=1;--i) {// backward phase
dp[i] = max(dp[i], max(dp[i + 1], dp[i + 2]) + a[i]);
}
cout << dp[1];
}
1 Like
Thanks 