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.

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 –

https://github.com/Apptica/Programming/blob/master/sparse.cpp

Practice –

https://www.codechef.com/problems/FRMQ

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

i
#include
…..

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.