The Programming Blog: 2016

No comments

So, now lets see how to know the Big-oh complexity for a given competitive programming questions.So follow this approach -

1.In all the platforms, you will be given a time limit in seconds according to the language you choose.Some platforms may not give you time limit for your programming language directly ,so calculate it as-

a. Codechef - codechef calculation -So,as said in the article multiply your language multiplier given here with the time limit given in the problem.

Ex- If time limit given in the problem is 2 sec ,then for Java multiplier is 2X,thus

time limit for Java = 4 sec

b. For hackerrank, refer this-Hackerrank Time

Similarly you can see by yourself to get the time limit for your language.We will calculate for C++.Thus for C++,its mostly 2 sec /given in problem (multiplier is 1 ,s no problem).

2.Now you need to calculate the no. of operations your programming language can compute in 1 sec.
So for C/C++ its usually around 10^8 operations per sec.
Similarly you can see for other languages.

3.Once you have got the time limit for your programming language ,now you need to calculate the total no. of operations for the given problem.For ex-

a.If n is test case limit and m is input limit then ,worst case no. of operations performed will be-
m*n.

so if m*n =N

So, for a 1sec time limit, (keeping 10^8 operations per sec in mind)

N>10^8: better than O(N), maybe O(nlogn)
N=10^6-10^7 : O(n) solution is required.
N=10^5 : O(nlogn) solution.
N=10^4 : O(n^1.5 or n(logn)^2) solution.
N=10^3 : O(n^2) solution.
N=10^2 :O(n^3) solution.
N=10:O(n!) and O(2^n) solution.

Above will be valid for java if time limit is 2 sec.But in all platform time limit is given wrt C++.So,just look at the above always.

For ex, let say you want to know above template for java on hackerrank.So,on hackerrank java is 4 sec ,but anyway we will look at C++.For C++, its 2 sec.

which means,template is-
N>2 X 10^8: better than O(N), maybe O(nlogn)
N=2 X 10^6-10^7 : O(n) solution is required.
N=2 X 10^5 : O(nlogn) solution.
N=2 X 10^4 : O(n^1.5 or n(logn)^2) solution.
N=2 X 10^3 : O(n^2) solution.
N=2 X 10^2 :O(n^3) solution.
N=2 X 10:O(n!) and O(2^n) solution.

No comments

DYNAMIC PROGRAMMING PROBLEM(DP)

Dynamic programming problems can be difficult to solve as a beginner.Today's blog will tour us through the important resources available online to start solving dynamic programming problems and then I will share some observations I found while solving some DP problems.

1. I started DP by understanding the basics through Algorithms by Das Gupta.It has explained DP in a very good and interactive manner and would be the best place to start.Though Algorithms by Cormen is equally good (actually better) but I find it somewhat boring and thus switched to Das Gupta.If you still have your basics loose, you can do a free course on Algorithms-part 2 by Stanford University which is available on Coursera.(It will be good to complete the whole course which is in two parts to strengthen the basics).

2.After this you can go to GeeksforGeeks.org and visit their algorithm section.You will get lot of content on DP and that will be the best place to get a idea of scope of DP problems.

3.After this you can move to Topcoder Algorithm tutorial which is the best available tutorials online (designed by Topcoder veterans).

SOME PROBLEMS I SOLVED

Here are some problems with which I have started my practice in DP.It is recommended to first try the problem yourself and then see my approach.As a beginner,it is normal if you are not able to solve first few problems.

A)See Problem

Like any other DP question one must figure out that -

1)"how to store it"

2)"what is needed to be stored" and

3)"how to manipulate it".

For example -

In this question, I used Hash map to store whatever i needed to store.

Now any key in our hash-map have value as a pair - counts= "MIN no. of steps to reach from current key value to input (i.e Integer K given by user) and soln="If M are min no. of steps to reach from current key to K,then how many different paths are there to reach from cur to K with exactly M steps".

Now the last step is to manipulate it -In form of recursion or iterative manner.

Observations I got from this question!!

1.Always read the question properly.Take your time.In my case I interpreted the question in wrong manner.I thought that the question has asked for total no. of possible solutions but actually it asked for no. of solutions possible corresponding to minimum no. of steps.Also it's important to not miss some small things asked in question like taking %1000000007 of your answer(no. of solutions) as asked in this problem.

2.Before coding down the problem,you should must think about your approach.In my case I used recursion technique of DP.I landed into error because I didn't even cared about input size which was 10 pow 9.It should have been obvious (had i considered this) ,that recursion technique would give a STACK OVERFLOW ERROR.Thus It could have saved me a lot of time had I started from iterative approach in the first place.

3.There were some tricky things to catch in this problem.(Read if you have attempted the problem already.)

So the first thing to notice was that if a no. contains '0' as one of its digits then it will call

"no. + 0" which is no. itself .Thus it will become a infinite recursion running in loops around this no.

Second catch to this problem was -No. of solutions corresponding to minimum steps were obtained as-

For ex- if no. is 16 then no. of solutions with no. of steps equal to min steps(let min steps to reach from 16 to 100 be M) will be as-

no. of solutions (all having steps to reach from 16 to 100 equal to M)=no. of solutions for 17(i.e no. of solutions to reach from 17 to 100 with exactly M-1 step )+ no. of solutions for 22 (i.e no. of solutions to reach from 22 to 100 with exactly M-1 step).

Now if a no. contains 2 digits with same value like 22 then it will add solution for 22+2=24 twice for each of 2's in 22.Thus it will lead to much higher answer than actual answer.

4.Even after all this I was getting 3 as no. of solutions for input 100 though answer should have been 2.I tried to figure the problem using debugger but it was a total disaster with so many recursion calls.So I used something basic to figure the problem in my answer.I inserted the print statement to print the no. of solution for every no. thus i figured out that the problem was with no. like 22 having same digits.

5.Since question demanded two things i.e. steps and solutions,I needed to return both of them.I could have done this by returning an array but it would have consumed a lot memory so I rather made a PAIR class within same java file and returned the pair.(NOTE:If u need to have 2 classes in same .java file just remove "public" from them.

6.Other noticeable thing is that its always better to use Hash map over array in DP.Not just for DP but also whenever you need to find if no. have occurred earlier or not (like i used for finding if no. contains duplicate digits or not).Some other observations are - initialize variable with INTEGER.MAX/MIN whenever finding max or minimum.

PROBLEM-2-SEE PROB HERE

OBSERVATIONS-

1.In this question I used Hashmap to store.Now,each hashmap entry will have key representing sum and Value of hashmap denoting no. of ways that sum can be achieved.Thus we can manipulate that -

Ways for Required sum=ways(ReqSum - arr[0]) + ways(ReqSum - arr[1]) +....ways(ReqSum - arr[n])

if arr is the list of coins available given to us

Now,answer will be very high than the actual answer.The mistake we were doing is -

Let ReqSum be 10, and array be 1,2,3,4

A1..10(-4)=10(-4)=10(-1)=10(-1)=0 ........4,4,1,1

A2..10(-1)=10(-1)=10(-4)=10(-4)=0......1,1,4,4

These two calls were counted as different ways but we can see that they are actually same combination(Just the order is different).In terms of DP, we can say that it is classical problem in which we are to choose paths which are totally different to each other (not same even when permuted) and also the paths can have repeated values as well.

Solution to this problem is that we can restrict calls such that path calls in decreasing order i.e.

A1 will be counted while A2 won't be counted.To implement this we can take value which was considered in last call and current value that is to be taken must be smaller/equal to that value.

PROBLEM 3-STOCK MAXIMIZE

Link-https://www.hackerrank.com/challenges/stockmax

So,this problem was wrongly tagged in DP section but still i will add its solution here-

The problem can be solved by asking a question-"How is profit generated ??"..since our aim is to maximize the profit.The answer to this question is --

For any share, you buy it and then sell it at maximum available price you can.In other words, it can be interpreted as -

If ( share price on a current day < maximum (prices of shares on subsequent days)

/////*meaning that if you buy share on current day ,there exist some day at which you can sell this share at higher price */////

then,

buy it ///since we will be in profit

else

////meaning that there is no greater value than today's share in coming days...which means we have to sell it in loss if we buy it...hence in this case,

sell all shares you have bought till now

(This is done because we know that current day share value is maximum of all coming days which means that we won't get better chance to sell our shares.)

Some Observations -

1.Here I was getting answer as negative for some large sample input which was because of int overflow and thus i used long instead...But again one of the answer was coming negative....After a lot of thinking I finally solved this problem by observing that -

money+= stockprice[n-1]*stocks;

Since money is of type long but right side will be integer (which will be overflowed before converting to long and hence negative and thus I rectified it as)-

money+=((long) stockprice[n-1])*stocks;

I will be adding more problems soon.......

No comments

Installing Cloudera Hadoop

1.For installing Hadoop,we can use virtual box or VMware workstation or any other virtual machine.I prefer VirtualBox from Oracle which can be downloaded from- https://www.virtualbox.org/wiki/Downloads

2.Once we have installed VirtualBox we can now download the Cloudera Hadoop VM environment which is the best option to start for hadoop. It can be downloaded from -https://downloads.cloudera.com/demo_vm/virtualbox/cloudera-quickstart-vm-5.4.2-0-virtualbox.zip . (Since file size is 4.004 GB,we need to have a good internet connection or download it using some IDM).

3.Once we have downloaded the above Zip File we will extract the zip file.

4. a)Now open the virtual machine installed in Step 1.Go to ->File->Import Appliance.

b)Click the browse icon and open the extracted Cloudera folder.We will find a ".ovf" cloudera file.Select and click import.

c).Once importing is done we can see the cloudera virtual machine on left tray.Select it and click START on top of window.It can take a while for virtual machine to start and might give low performance initially.

5.Common Errors -

a).In case you encounter a following message-"this kernel requires an x86-64 CPU, but only detects an i686 CPU"

To be able to run a 64-bit OS in Virtual Box we have to make sure

the virtual machine's architecture is set to 64-bit too.

Choose Ubuntu 64-bit in General -> Basic settings on creation of your VM
In addition, for running 64-bit guests it is recommended to enable the Input/Output APIC in theSystem -> Motherboard settings for your virtual machine:
In the System -> Acceleration tab we may want to enable the hardware virtualization features VT-x/AMD-V of your CPU.

b).In case ,we are not able to find our current Operating system in given versions list above (i.e.we might find only OS with 32 bits as options),we need to go in to BIOS and enable Virtualization (in
configuration tab). Exit the BIOS, making sure you save
changes.

Select current operating system and now problem should be resolved.

Now, we should see all the 64 bit options in the Version dropdown box.

No comments

The Programming Blog

DYNAMIC PROGRAMMING PROBLEM(DP)

SOME PROBLEMS I SOLVED

PROBLEM-2-SEE PROB HERE

PROBLEM 3-STOCK MAXIMIZE

I will be adding more problems soon.......

Installing Cloudera Hadoop

About me

Categories

Blog Archive