You are not logged in. Please login at www.codechef.com to post your questions!

×

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;
}

asked 08 Apr '17, 12:33

ravidelcj's gravatar image

4★ravidelcj
101411
accept rate: 16%


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

link

answered 08 Apr '17, 13:03

bansal1232's gravatar image

5★bansal1232
2.8k1418
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) ravidelcj4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×2,033
×385
×2

question asked: 08 Apr '17, 12:33

question was seen: 569 times

last updated: 08 Apr '17, 14:09