# Hackeearth Code Monk Dynamic Programming round

The Question in the link below was asked in the Code Monk Round at hackerearth
https://www.hackerearth.com/problem/algorithm/vaishu-and-best-friends/

I decoded it and found that the answer should be

(all possible combination - All subsequences with alernating 0s and 1s)

So the Problem narrows down to finding the number of possible subsequences with alternating 0s and 1s

here is my approach of finding all possible subsequences with alternating 0s and 1s

``````dp[1][1] = 1;
dp[0][1] = 0;
for(int i = 2; i <= 1000000; i++){
if(i % 2 == 1){
dp[1][i] = (dp[0][i-1] + dp[1][i-1] + 2)%M;
dp[0][i] = (dp[0][i-1]%M);
}else{
dp[0][i] = (dp[1][i-1] + dp[0][i-1] + 1)%M;
dp[1][i] = (dp[1][i-1]%M);
}
}
``````

Here dp[0][i] indicates all the subsequences till now ending at a 0

and dp[1][i] indicates all the subsequences till now ending at a 1

The sum of dp[0][n] + dp[1][n] will tell all alternating subsequences

But i am getting a wrong answer.
Please Point out what is wrong

Here is the Full code

``````#include <bits/stdc++.h>
using namespace std;
#define M 1000000007

long long dp[2][1000005];
long long power[1000005];

void precompute(){

power[0] = 1;
power[1] = 2;
dp[1][1] = 1;
dp[0][1] = 0;
for(int i = 2; i <= 1000000; i++){
power[i] = power[i-1]*2;
power[i] %= M;
if(i&1){
dp[1][i] = (dp[0][i-1] + dp[1][i-1] + 2)%M;
dp[0][i] = (dp[0][i-1]%M);
}else{
dp[0][i] = (dp[1][i-1] + dp[0][i-1] + 1)%M;
dp[1][i] = (dp[1][i-1]%M);
}
}

}

int main()
{
ios_base::sync_with_stdio(false);
precompute();
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("&d", &n);
long long ans = ((M + ((power[n] - dp[0][n-1] + M) % M) - dp[1][n-1]))%M ;
ans += M;
ans %= M;
printf("%d\n", ans);
}
return 0;
}``````

The solutions, editorial and the test cases has been out! Please check out. If problem still persist then comment here.

I have checked the editorial But my problem is that i am not able to figure out what is wrong with my approach
Also i am not able to understand the Authors Solution, (how he formulated the dp states for calculating the alternating subsequences) if you can elaborate on this too , it would be really helpful

//