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]