Digit Dynamic Programming – Digit DP : Part-1

DP is one of the most important trick used in programming. This article discusses about a variant that can be used to solve problems like how many numbers are there between a and b such that they contain a digit x. Now since this one may be easy and you can think of some formula but DP can be used as a very nice approach here.

Suppose you have been given a number 1608 and you want to enumerate all the numbers which are lesser than or equal to it. This can be done easily using the following process.

Let us assume we have four blanks ___ ___ ___ ___ . Now what can be the first digit from left it can be either 1 or 0. i.e.

0 ___ ___ ___ and 1 ___ ___ ___ . Now if we have placed 0 in the beginning it is a clear observation that we have not made any 4 digit number so the second digit can take values 0 to 9, but if we have placed 1 there then the next digit will be always 0 to 6 or else number will be greater than the required number.

In digit DP whenever we form all numbers smaller than or equal to any number we start formation with the most significant bit. Then Suppose total digits in the number is to be atmost 4 (like here) then we try to place each digit 0-9 in all the 4 places but keeping in mind that the number formed is always lesser than or equal to the limiting number.

I prefer recursion to be the best way to solve it and we can easily memoize it.

In recursion we always record with us the following things —

1) If number formation is started or not (This can be a boolean variable). Number formation start means that we have atleast one non zero digit in the number formed till now.

2) If number formed till now is less than or equal (greater is not required) to the number using the k digits from the left. Again this can be a boolean variable. To be more clear here if we have formed a number 160 ___ with only one place left then if we are placing any value on the
4th blank then we should know that 160 is equal to the number that can be formed by three digits from left. This decreases the total possible values. Here you can only place values 0 to 7.

3)Third information is how many digit number you have formed or it can be like which position are you going to think of now.

Read the above points carefully to understand the recursion properly.

To understand we can take solve some problems in difficulty order.

Problem – 1 : Count  3 digit numbers containing digit 7

Solution –    : You can start enumerating numbers. For explanation i will use the code below.

For the first digit from right you have 9 choices 1 to 9. For second 10 choices and for third 10 choices. Suppose you are making a choice of second digit then if the first digit from whose recursion you jumped into this one is already 7 then value of contains will be true  or else if you have not placed 7 till now then contains will be false and will become true when you will call function count by placing digit as 7.

When recursive programs are called then there has to be some condition where we have to stop them. According to me the best way is to recurse until you reach a length greater than maxlength.

Its clear that this recursion with itself stores information as position and contains.Now suppose you reach the end condition with contains as true, its like :

1 7 9 contains digit 7 so return 1 because this number contains 7 so you must have changed value of contains earlier

1 9 5 does not contains 7 from beginning to end so the value of contains will be 0 always.

Trace this program from beginning, just for binary numbers that have digits 0,1 or just make your own digit system with digits 0,1,2,3 so it will be easier to understand the code.

Now here is the dp code or memoized recursion.

Sparse Tables Range Query

Range query problems are generally solved by either Binary Indexed Tree or Segment Tree. But sometimes when total queries are very large then you need some another data structure such that query time is almost constant and prefetching or pre-processing time is N log (N). The data structure is Sparse Tables.

Assume a range query problem where 10^7 questions will be asked.

For example: an array of size 10^5 and questions of type – Find minimum of all numbers in range L – R then segment tree will fail so we need sparse tables.
In sparse table we use concept of dynamic programming (if you don’t know then also its ok, it’s just traversing an array intelligently).

The concept is to break down the complete linear array in chunks of powers of 2. For example – let array indexes be 0,1,2,3,4 then break the array in chunks of powers of two as below —-
Row 0 —– >0 – 0,0 – 1,0 – 3
Row 1 —– >1 – 1,1 – 2,1 – 4
Row 2 —– >2 – 2,2 – 3
Row 3 —– >3 – 3,3 – 4
Row 4 —– >4 – 4

These ranges denote that we will be calculating the answer for only these ranges only and the answer for any other range can be calculated from these many ranges only.
The main thing is how to break into these ranges and calculate the data efficiently for this and store.

To store values we will use a 2 Dimensional array where A[i][j] means the answer for range
i to i + 2j- 1

Simulate the above formula and you will get the values which are given above.
We already know the value for A[i][0] because i + 2

0 – 1 = i itself it means we are asking the a[i] element as our answer.

We will be calculating answer in column major which means A[0][0] then A[1][0] then A[2][0]….and so on. Then after that A[0][1] A[1][1] A[2][1] etc. and similarly for all other values.
So when you are going to calculate A[i][j] you already will be knowing answer for A[i][j-1]. So I will break the asked range L to R in the form of two ranges for which I would have calculated answers in my table.

Suppose the query is find minimum element of array in range L to R. Let there exist two numbers a and b  with following conditions —–
L + 2


R – 2


Also R-2

Basically these conditions mean that the given range is broken into two ranges such that for both the ranges I have calculated answer in my table. For example let the range is 7  to 19 . Then a and b  can be 3 and 3 so that the range 7 to 19 is broken into ——
7 to 7+8-1 i.e. 7 to 14

19-8+1 to 19 i.e. 12 to 19
We are doing this to ensure that both the ranges are overlapping to each other and also cover entirely the asked range 7 to 19. Here a = b and this condition always holds. (Why ? this you need to think. Comment for help). Say a = b = 2 then the range would have been 7 to 10 and 16 to 19 so what about the numbers of range 11 to 15 . Thus dividing the range is a crucial step.

IMPLEMENTATION and Few Formulas –

The implementation is very easy once you understand its concept. The answer for A[i][0] is very clear as explained above. If you are calculating A[i][j] in column major order then you are always ensured that before calculating answer for range i to j i.e. A[i][j] you will have answer for A[i][j-1] and also answer for A[i+2

j-1][j-1] because columns are one less than j and in calculating column wise we have already visited them.

Thus for calculating A[i][j]
A[I][J] = MIN(A[I][J-1],A[I+2

(J-1)][j-1] which in simple language can be decoded as

Answer for range i to i+2

j-1 is calculated from answer for i to i+2(j-1)-1 and i+2(j-1) to i+2(j-1)+2(j-1) (which is equal to i + 2j)

Remember MIN can be replaced by any range function as per your problems.

For breaking ranges into chunks of two I am leaving this as a thinking and brain application for Reader. You can get help in comments or from my code.

Code for Sparse table –


Practice –


Importing your templates in Vim

How does it feels making copy of your coding templates before any coding competition ? Isn’t there any method such that if you are making a new c++ file or c file and your template is automatically loaded. It is not a very tough task to just copy your code from github or just make copies of a template file but still here i am going to discuss a one time method so that you don’t need to prepare anything before writing your code . An auto command such that your template is automatically imported whenever you make a new file is just awsome.

Before we proceed i would like to say that every software or program you use certain events are associated with it. For Vim or any editor opening a file when it does not exist , opening a pre existing file etc. are different events. We need an autocommand for the former one.

Vim contains a configuration file which can be edited from the home direcory as gedit .vimrc or vim .vimrc . You have to edit this file to make it perfect for coding. I recommend the following steps —

1. Go to the home directory and open your .vimrc file for editing. Actually .vimrc is its name.

2. Edit the contents of the file as follows —

set ai
set tabstop=4
autocmd bufnewfile *.cpp so template.txt

3. Save the file and in the home folder and copy your template.txt to the home folder.

4. In the template.txt file in the first line add i and press enter. It should look like


Now Enjoy writing codes with pre define templates🙂

Appendix —

1. bufnewfile tells vim about the event that a new file which does not exist is created or else you would have written the template in already written files too.
2. set ai is for autoindentation and set tabstop is for making tabspace length 4 from 8 (default)
3. i is added to the file because vim recognizes each step as a command given to it using the colon part. So i enables the editing feature. Remove i from the file and see what happens. You may understand the whole logic🙂

Wifi Button Fade- Cant Switch Wifi On / Off in Windows 8.1/8 or any platform

Wifi Button sometimes fades out and we are not able to click it. We are also not able to even switch to and fro the airplane mode even using our wireless push button does not works.
FIX:At the boot time when the system starts open your bios settings and go to exit options. Select Reset to defaults and save and exit…..Your problem gets fixed.
If this does not help simply uninstall your drivers of wifi and reinstall them.
If this also does not work, last try is use a registry cleaner to remove unwanted registry key entries which may have made an obsolete entries to your registry hives.

Windows App Contract Not specified error fix

One of the popular and unsolvable error in windows 8.1 is seen “App contract not specified”. The tile apps stop working or even may not function. Various fix include typing unhelpful command lines, resetting windows store etc. What I did is i think the best amongst them.

1. Back  up your data of my documents folder.
2. Now create a new user account.
3. Delete the current user account and sign in with the new user account.
4. All problems will be fixed.

Though there will be loss of apps and their updates but besides everything it comes out to be a very n
ice method to fix it. Good luck!!

Windows 10 Technical Preview

Microsoft has already launched its preview of Windows 10.Try and report what you liked and what you didn’t liked. They need our feedback to improve.

Changes I observed—->

1. Change from the tiled to classic+tiled view of start menu
2. Change in icons of My Computer and other’s too.
3. UI changes little bit

Post your feedback at www.facebook.com/apptica

Download Here x64 Eng Version for more goto microsoft.com