SUBNUMS | Prayatna 2019 OLPC | Contest | Help

Can someone tell me how to solve SUBNUMS question?

This can be solved by DIGIT-DP

Let f(x)=count of numbers <=x with 101 substring in its binary representation.
Then answer will be f®-f(l-1)

To find f(x),
First convert x to binary, then going left to right for each bit, place 0 or 1 in current position keeping current number<=x.

Construct dp[pos][prev1][prev2][issmaller][isfound]

pos=current position.

prev1=previous bit wrt pos

prev2=second previous bit wrt pos

issmaller=whether current number has become smaller than x or not(is still equal to x).

isfound=whether 101 has been found in current number or not

If you get prev1==0 and prev2==1 and you are placing current bit as 1, set isfound=1 (since substring 101 is found).

You can count the numbers having 101 as substring using isfound upon reaching the end of current number.

See my code here

1 Like

Your code is really hard to understand. Please try to rewrite the code with proper comments(if you can).