i am trying to solve this problem but not able to get idea could any body help ?

problem : CodeChef: Practical coding for everyone

It’s a pretty trivial dynamic programming problem ,say dp[i][x][y] represents number of ways to make a string of length i with last entered element is x and second last entered element is y which don’t have 101 as a substring. So the transitions would look like:

if : x=1 and y=0

dp[i][x][y]=dp[i-1][0][0]

else:

dp[i][x][y]=(dp[i-1][y][0]+dp[i-1][y][1])

And it’s trivial to see that final answer would just be:

A =\sum_{x=0}^{1}\sum_{y=0}^1dp[N][x][y]