Configuring Ubuntu – Virtual Box (No Lag)

For many virtualbox users even with a decent system configuration, it is often noticed that there is a system lag when you use ubuntu in it. Even after allocating enough amount of RAM, 128 Mb of Video memory you don’t get the performance upto mark. So what to do ?

Here are few things as preliminary steps.
Configuring VirtualBox

Allocate enough amount of RAM in the machine settings. Navigate to display settings of your virtual machine and increase the video memory to 128Mb. Now check Enable 3D Acceleration option.
Configuring Ubuntu

After installing ubuntu simply boot it. Open a terminal and type in this command.

/usr/lib/nux/unity_support_test -p

Now you will notice the following output.

In my all features are yes. But in your pc the one besides software rendered and unity support will be no. So basically the aim is to enable features which are no yet.
So for the virtualbox we need to add some additional options. Type this in terminal
sudo apt-get install virtualbox-guest-additions-iso

Let the command end. Actually this iso can be downloaded from outside.
After this command gets executed navigate to the /usr/share/virtualbox folder from root. 

Mount the iso file and it will prompt you with a run option whether to execute a script or not. Do yes and you are done with installation.

Restart the VM and enjoy speed up with no lag Ubuntu
Install Ubuntu 🙂 Enjoy Coding !  

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 easier problem so as to clear 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.

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 (prev) the number generated is prev*10 + x. Now you can check this number is perfect square or not. If it is then upgrade isvalid as 1.

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.

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 🙂