Lucky Start in new semester

I reached hostel on 20th July afternoon. After taking rest for sometime I was ready for the Codechef's Cook Off contest . I started off well by submitting the first problem in the 7th minute . That was a very simple problem,  after that I attempted one more easy problem but made a very simple mistake and got penalized for that . Penalty was 20 extra minutes in my actual time . It was very frustrating that in an easy problem I missed one small condition and straight away I was penalized heavily for that but after one wrong attempt I submitted it successfully . Luckily I completed all the problems that were within my reach in time as just after submitting the second problem current went off .
I got 454th rank overall in the contest.

This week I was doing problems randomly as I was busy getting prepared to attend the classes and adjusting in a new room .
I did a problem on floating numbers and got a tip from a senior while doing it from a senior that if we enter a floating no. from the user like 0.02 it gets stored in the memory as 0.0199999999...(you can't see it as while printing the no. it shows 0.02 only ) while converting the decimal parts in binary the precision is not infinite so these things happen and thus a bug may easily enter our 'bug free looking' program .So,its advisable to use string to take the no. from the user and then manipulate it accordingly .
 
I've made a time table for myself I hope it will help me to manage my time properly . I know that managing programming and studies will going to be a challenging task for me but I'll try my best.

Thanks for reading and keep coding. 

New semester new story.

My 3rd semester is just about to start within a day from now.I'll try my best to make full use of time and the resources I have in this semester.
Just last night I participated in Codechef's Cook Off and did 2/5 problems . These two problems were very easy the other three were somewhat difficult out of those 3 two were touching the concepts of graph theory.
I made a wrong submission that costed me a penalty of 20 mins. otherwise I would have been in under 300 for sure but still I got 453 rank.

I got a method to calculate both LCM and HCF and that too very fast O(LogN). Yes,if you know it already I am talking about Euclid's GCD theorem.

Its like this -
Lets say we want to calculate GCD(Greatest Common Divisor or Highest Common Factor) of two given numbers lets say A,B .

So, pseudo code of the algorithm looks like this -
START-
GCD(A,B):
    if B>A return GCD(B,A)
    else:
        if A%B==0 return B
        else return GCD(B,A%B)
END
For example lets say A=12,B=18
calling GCD(12,18)
so as B>A it returns GCD(18,12)
then as 18%12=6 which is not equal to 0 it returns GCD(12,6)
but now as 12%6=0 it finally returns 6 . So, 6 is the GCD of 12,18

This method is very old yet very effective method to calculate the Highest Common Factor of given two numbers.

Now to calculate LCM all we need to do is just multiplay the no. A & B and divide the product with the GCD of A & B.
For example lets say A=12,B=18
So, LCM of 12,18 will be 12*18/GCD(12,18) = 12*18/6 = 36
Time Complexity of this algorithm is also O(LogN) as multiplication is O(1) and GCD is O(LogN)
So,Now we have two very effective algorithms to calculate HCF,LCM of two numbers .

Thanks for reading and Happy Coding :) .

A Busy Week..

This week I was very busy . I went to my Guru ji's(Spiritual Teacher) town to celebrate Guru Poornima with my family . Its an Indian festival dedicated to teachers. Word 'guru' is made of two sanskrit words 'gu' which means darkness and 'ru' which means remover.Whatever little I've achieved in my life is due to the teachings and blessings of my teachers .

I was trying to learn Breadth First Search this week . Now, I know the basic idea of Breadth First Search but don't know how to code it properly .I would like to add this graph searching technique in my armory ASAP .

My summer vacation is coming to an end .On 20th July I'll be moving out of my hometown for another amazing semester. This time I'll meet a whole new array of freshers . Really getting excited to search for good programmers out their .

The journey has just begun .


Thanks for reading and keep coding .  

Going Greedy ...

This week I was doing previous challenge problems on codechef . I saw a problem which was based on greedy technique .

 Suppose you are very busy but greedy as well ;) , you have some equally valuable tasks assigned to you and you want to complete as much as you can(see here comes your greed) but tasks are not available at the start of the day you receive them after some predefined time and some tasks take longer time to complete , so what approach you should follow to complete max. no. of tasks ?

Here it is - 

1. Write down all the tasks in this manner -> end time/start time

2. Now sort them in increasing order .

3. Make a counter for no. of tasks completed and give it a value = 1 and save a variable lets say T = end[1].

3. Compare first task's end time with the start time of the next task and if ( T<=start[2] ) add 1 to the counter variable and update T  = end[2]

4. Do step 3 for all activities from 1 to N (Supposing you have a total no. of N activities).

For ex - we have these activities(start time/end time) 

1. 3 5

2. 2 6

3. 1 9

4. 7 9

5. 3 4

after writing these in end time/start time manner we have 

1. 5 3

2. 6 2

3. 9 1

4. 9 7

5. 4 3

Now after sorting them(first compare end time and if end time is equal compare start time) 

1. 4 3

2. 5 3

3. 6 2

4. 9 1

5. 9 7

Now take a variable lets say B = 1(for total no. of completed activities) and T = 4(end time of first activity)

Now look for start time which is >= T . In this example it looks like we don't have any other option other than completing first and fifth task(or third and fifth task) as time of all other activities doesn't fit properly so the answer is 2 in this case.

These kind of questions are called Maximum Activity Selection Problems. I hope you liked it.

Thanks for reading.