Digit Dynamic Programming - Digit DP : Part-2

In the last post i discussed few basics required for DP on digits. Now i am going to explain you a  problem so as to relate to what that post meant. 

Problem : Given a range $[L,R]$ , how many numbers are there such that its two adjacent digits form a number which is a perfect square.

Solution: Problem asks us to count numbers like $125$ as $25$ is a prefect square, $198$ is not valid as there are no two adjacent digits for which the number is a perfect square. 

First of all let us discuss some state variables. 

• $pos$ : $pos$ tells us that you are going to place any digit on this position
• $isequal$ : Discussed already in previous post, this tells us whether the number formed till now is equal to the prefix of the limiting number starting from $1$ to $pos-1$. For example let us count numbers less than $1269$ then for the status $126 __$ , $isequal$ will be $1$.
• $started$ : This tells us whether number formation is started or not. In simpler words whether number formed till now is having any nonzero digit or not
• $last$: last is the digit used in the place $pos-1$
• $isvalid$ : This tells if the number formed till now contains any perfect square formed using adjacent digits or not.

Below is a recursive implementation of the following question which will for granted exceed the time and memory limits for even little larger ranges. But to be conceptually clear its the best way. Next solution is the memoized recursion one which is much much faster than this one.

	int dp[10][2][2][10][2]; // -1 initially
	vector<int> v;//contains the number broken into digits
	int process(int pos, bool isequal, bool started,int last,int isvalid) {
	if(pos > v.size()) {
	if(isvalid == 1)
	return 1;
	else
	return 0;
	}
	int ans = 0, num = 0;
	if(dp[pos][isequal][started][last][isvalid] != -1)
	return dp[pos][isequal][started][last][isvalid];
	if(isequal == 0) {
	for(int i = 0; i <= 9; i++) {
	num = last * 10 + i;
	if(num > 10 && is_square(num) == 1)
	ans = ans + process(pos + 1, i == v[pos - 1], started | (i != 0), i, 1);
	else
	ans = ans + process(pos + 1, 0, started | (i != 0), i, isvalid);
	}
	}
	else {
	for(int i = 0; i <= v[pos - 1]; i++) {
	num = last * 10 + i;
	if(num > 10 && is_square(num) == 1)
	ans = ans + process(pos + 1, i == v[pos - 1], started | (i != 0), i, 1);
	else
	ans = ans + process(pos + 1, i == v[pos - 1], started | (i != 0), i, isvalid);
	}
	}
	return dp[pos][isequal][started][last][isvalid] = ans;
	}

view raw DigitDp2_1.cpp hosted with ❤ by GitHub

In this code $v$ is a vector of digits containing all the digits in the upper limit of the number to be formed. Here upper limits will be $L-1$ and $R$. For both we need to call the process function separately. 

Explanation : Suppose you are putting digit $x$ at place $pos$ from left so with the knowledge of the previous digit i.e. $prev$, the number generated is $prev \times 10 + x$. Now you can check this number is perfect square or not. If it is then upgrade $isvalid$ as $1$.

Some problems to practice:

• Total Palindromic Numbers (Codechef)
• Open the Locks (HackerEarth)
• Digits and Fun (HackerEarth)
• Codeforces has it all :) (Codeforces)