×

# Hackeearth Code Monk Dynamic Programming round

 0 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 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; }  asked 08 Apr '17, 12:33 101●4●11 accept rate: 16%

 0 The solutions, editorial and the test cases has been out! Please check out. If problem still persist then comment here. answered 08 Apr '17, 13:03 2.7k●3●15 accept rate: 16% 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 (08 Apr '17, 14:09)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,754
×362
×2

question asked: 08 Apr '17, 12:33

question was seen: 495 times

last updated: 08 Apr '17, 14:09