WITBIT - UNOFFICIAL EDITORIAL

dynamic-programming

#1

PROBLEM LINK
Contest

DIFFICULTY
medium

PROBLEM
Given a range of integers [L, R] and we have to find the count of such integer i where L≤i≤R and binary representation of i contains the pattern “110” as a substring, where L, R can potentially go up to 10^18.

EXPLANATION
As we need to find the information of substring “110”, whether it is present in the given range we need to convert the given numbers into Binary Strings. We can simply do that in C++ using inbuilt function std::string s = std::bitset< 64 >( number ).to_string() :stuck_out_tongue:

We can solve now with Dynamic Programming we require three arguments that are:
pos: current index of the number which we are forming.
cnt: which count if we have counted the substring “110”. If yes then we return 1 way of having a number which has “110” in the given number.
flag: which tell us if the given number is smaller than the given number.

LL go(LL pos, LL cnt, int fl){

// Base Case of Our Function

 if(pos == num.size()){
	if(cnt == 3)	return 1;  //If cnt = 3 that means we got one of substring "110", so we return one 
                                 way.
	return 0;                  //If cnt != 3 we return 0
}

int lmt;                    // Which tells us the limiting or ending value for the current position.
LL &res = DP[pos][cnt][fl]; // If result is already calculated then return it as it was.
if(res != -1)	return res;

res = 0; //If result was not calculated then make dp[pos][cnt][fl] = 0 and calculate it now.

if(fl){
	lmt = 1;         // If fl == 1, it tells us that the number which will be made will be smaller than 
                        given number so we can give its limit 0 to 1 
}else 
    lmt = num[pos];  // if fl == 0, it tells us that the current number is equal to the given number so 
                         we can place the digit at this given position either 0 to num[pos].

for(int i to lmt){
	int nf = fl;
    int ncnt = cnt;
    if(fl == 0 and i < lmt) nf = 1;         // The number is getting smaller at this position
    if(i == 1 and (cnt == 0 || cnt == 1))	 // If the current[index] = 1 and we have cnt = 0,
    ++ncnt                                      means that none of 1 of "110" occured till now 
                                                **or** we have cnt = 1, means one 1 of "110" have 
                                                been occured  

    if(i == 0 and cnt == 2)	                 // If we got two 1 of "110" so we can now needs to search  
    ++cnt                                      for zero to make our search complete.
    
    if(i == 0 and cnt == 1)	                 // If we got zero after the cnt of 1, like this "10...." so
    nct = 0                                     we will be making ncnt = 0 again and we need to search 
                                                string "110" again in the given number

    res += go(pos+1, ncnt, nf);              // We will be moving our current index postion by one step 
                                                forward. 
}

return res;

Link for AC Solution: this