Bye Bye 2014 Welcome 2015

I'll say that the year 2014 was one of the most happening year of my life. I learnt a lot in this year and by the end of this year I am a much more learned person. I got deviated from my ultimate goal but now I am back with full support from my loved ones. In one word I would say that year 2014 was "fantastic".I had a lot of ups and downs and a lot of failures and they taught me how to move on.

I have some goals ready for 2015 I want to complete them as fast as possible.

At present I'll be focusing on Machine Learning because I think it solves the deep desire in me to do something of the type I used to imagine when I was a kid.I wanted to be a scientist and I can make it true if I study data science. Its difficult to follow that path but lets see how much motivated I remain throughout this quest.May be one day I'll be able to call myself a data scientist. 

Wishing everyone a very happy and prosperous new year !

Introduction to Machine Learning

Wishing everyone merry Christmas !

These days I am learning about Machine Learning. The thing that excites me the most about this field is that its like teaching computers how to think like a real human. The computer can develop the ability to do something by learning from the simulation or from the data provided which may be so much difficult if we go through the normal programming.

Machine Learning Algorithms are broadly classified into these two categories -

1. Supervised Learning -
 
                      In this type of learning the computer is given the data with results like right and wrong or classification based results and it is made to learn from it what is correct and what is incorrect or how to classify the result.
       
               It can be further divided into two types -
             
              1. Regression - It is like predicting the continuous value of the asked object like price,quantity,etc,. Ex - Prediction of the stock price from previous month performance of the stock and the market status , estimating the value of the land purchased based on the given data.
 
              2. Classification - It is like predicting a type of outcome out of some finite possible outcomes like predicting the outcome of a football match between Real Madrid and Barcelona whether it will be a draw or Messi's magic will prevail or Ronaldo will seal the victory. In this example no. of possible outcomes are 3. Win,loss and draw

2. Unsupervised Learning - 
      
                  In this type of learning the computer is provided with the data and it is asked to provide some structure in the data provided.Ex - finding the set of people who are having more than say 10 mutual friends on a social networking site or like finding patterns in the genetic structure of two individuals.

There is a famous problem in which the goal is to separate out different type of voices from the recording given. This problem is known as cocktail party problem. There is an algorithm derived for this problem and it took a lot of research to derive it. Surprisingly, now it can be implemented in Octave (A Machine Learning Programming tool) by just a single line of code.

This is what I've learnt.I used to surprise that how photo tagging feature on facebook works.Its accuracy of identifying individuals in the photo is quite good. Now I've the answer. Its ML magic.

Thanks for reading and once again merry Christmas !  

Finally !

After spending a lot of time trying out different things I got a very interesting area to invest my time.
Its Machine Learning ! With a lot of real world applications this is like a dream come true for me . It's just what I needed.

I tried out with android,game development,gui development,etc. I was not that much interested with those things but this is so much interesting that I am taking its course on coursera even at 3 o' clock(night). I don't know whether I'll be able to master it or not but its worth learning it.

Lets see I drive through this part of my journey. One thing is for sure its gonna be interesting damn interesting!!!

Lost in the unknown world

So, after letting go algorithmic questions, these days I am focusing on creating something. I tried learning html then I switched to android application development and then open source development and then python.

Honestly speaking I don't know what am I doing these days but I want to build something like some small application. I just can't live without it. Life is not easy and I too.

Next semester is going to be awesome because for the first time most of the courses are related to Computer Science department and are of my interest. I was waiting for this semester for past 18 months.

It feels like riding a roller coaster and I love it !

ACM ICPC Kharagpur Onsite 2015

What should I say about this ?
It was a complete blunder . A BIG blunder . Everything was ok, we solved 3 out of 10 questions too still it was a blunder.

We got Disqualified. We 3 people were taking lunch after the contest and I got a phone call that please come in the computer lab . I asked the person on call, what is the reason for this? what happened ? He told that its very urgent so please come fast. The news was that we got disqualified and the reason was that as we had already participated in 2 regionals this year . We were not eligible to appear for this one but due to delay by baylor officials they couldn't inform us earlier .

Whole story -

We applied to all the regionals Amritapuri,Kanpur,Kharagpur .We made Demand Draft for Amritapuri and sent it . We participated in the online round we got selected for it but we didn't go for onsite .
For Kanpur, due to our mid semester examinations and some other problems we didn't even send D.D. for it.
Lastly, we filled for Kharagpur and we sent the D.D.

The reason which the Kharagpur officials gave for disqualification was that we had already participated in 2 regionals in the current year so, we were not allowed for further participation. We tried to make them clear that for Kanpur we didn't even send D.D. so they shouldn't count it as a participation but they said they got a mail from baylor that we have been disqualified based on strict rules so nothing can be changed and this decision is final.

Aftermath -

Its december again. Just one year back I started my programming journey and I learned a lot by doing competitive programming. Right now I am not feeling good or you can say not in a mood to continue competitive programming. I am in search of something else. Something like software development or application development.

So, is this the end of my competitive programming career?
Yes ?

Is this the end of my programming career ?
Definitely Not

Will I be able to become a good programmer ?
Only time will tell.

In past 4 months I learned a lot about myself and what all things I like and dislike. I do things which I truly like and I don't like being captured in a stereotypical image.
Breaking it for me and myself .

The journey is still on !

Freedom !

Its difficult for me to do something which I don't like but finally my examinations are over now and its time for programming. I hope we will do our best in our first ever ICPC regional on 7th Dec. Lets see what is there for us in Kharagpur.

I am free !

Time for a break

This week I participated in codeforces round and got a rank of 1030. I did a simple mistake and got wrong answer in the system testing.The mistake was that I initialized the variables in a wrong way. Rest everything was ok.  It was really very annoying when I got AC after re-initializing the variables just after the contest.

As end semester examinations are near I will be completely focusing on my studies now. Hard to leave programming but this is the need of the hour. After the exams a sudden burst of algorithmic coding will be coming in the form of ACM ICPC.Without wasting any day we need to practice as much as we can in the week just after our exams. Very much excited to see what happens in the on- site contest.

ICPC Drama

This time it was better.A lot better than before . I am talking about ICPC Kharagpur regionals.

We missed the original contest which was scheduled on Oct 18 due to our negligence but god gave us another chance and we took it .

We were having our lab during the contest hours and we decided to leave the lab 1 hour before to participate in the contest. Everything went well and we reached our hostel well before time.

I was having headache that day but still I wanted to help my team every possible way. I decided to give my 100%.

I went to Sudharsan's room around 10 minutes before the starting of the contest . He was having butterfly in his stomach . He was waiting for this contest desperately.

The clock ticked 6 and contest started. I opened a problem and found out that it was very easy.Without wasting time I started coding it meanwhile my friends opened different problems by the time I was debugging my code Sudharsan asked me if he should code my problem I said yes to him but I didn't stop coding and made the program before him . Then I called him to give some test cases and then submit . He gave around 15-20 test cases and it was working fine and we decided to submit it but there was a problem . I was logged out due to some reason and we were getting error "Access denied" it was so much frustrating.

Then I coded the same solution on his laptop to submit. I got compilation error due to mishandling the variable names (I used the same names I used in my original program :P ) This whole process costed us 10 more minutes but we got AC without any penalty. 

By this time we were 2nd in our college as the other team submitted the solution just 20 seconds before us.

Meanwhile Prajval (cool dude) came up with a solution to the second problem. We were so happy but I saw a basic flaw in the program I made a test case where his code was failing.We concluded that this problem is based on graphs . Sudharsan was practicing graphs specifically so he took the responsibility to code it . Meanwhile I was making test cases where our code may fail. After 50 minutes we were ready for our second submission. 

We got AC in our first go and that sealed our way to the Kharagpur regional.
We were ranked 126/440 teams and 43 out of 100 teams they have selected for the onsite.

We are now planning to go for Kharagpur regional . The onsite contest is on Dec 7 . Lets see what happens in the real arena. 

Something Unimaginable !

Though I'm late but still I won't stop myself.Wishing everyone a very happy and prosperous diwali .

This is the first time I was participating in ACM ICPC regionals and we got selected for one but the sad part is that we got selected just because of the rules of the competition .

According to the rules of the competition - Firstly, those teams will be selected which have solved at least 1 question and are first from their college,if slots are left then teams will be selected from the rank list according to the merit.

As you can see that it may happen that from a college where many good programmers are participating a highly potential team may not get entry to the regional while a not so good team may get it easily.

Let me show you an example - Suppose there are two colleges X,Y

X is a very big and renowned college and has around 50 good programmers .

Y is not so big college and doesn't have programmers at par with X .Lets say somehow, Y comes up with 1 team.

In the contest around 7 teams from X solve 2/5 problems , 8 teams solve 3/5 problems and 2 teams solve 4/5 problems .

On the other hand team from Y manage to solve 1/5 'the easiest of all problem' and gets rank 1 in their college.

So, according to the rules it may happen that the teams which solved 3/5 problems don't get selected as they are not the best in their college but as Y's team was the best in their college it will get entry to the regional. Sounds unfair right ?!

That's what happens every year in the Olympics of programming ACM ICPC .

 Nevertheless , we got selected and we should try our best to prove our selection right. 

We missed Kharagpur online contest.It was scheduled at 2 to 5 PM and due to our negligence we thought that it is at 6 to 9 PM because for Amritapuri regional it was from 6 to 9 PM .

I came to know about this at around 5:45 and we were dumbstruck. This was one of the biggest mistake we would have ever done but I told my teammates not to worry about anything we still have Amritapuri and we will give our best there.

Surprisingly on Diwali day I got a surprise that due to some reasons they are re conducting the contest on Oct 30 and luckily, very luckily we got another chance for the contest. This time we won't make any mistake .

This week I solved problems from SPOJ and participated in codeforces round also . After a very long time I again participated in the online contest on codeforces and stood 1285 from around 2000 contestants . 

Question: Is it time to change the selection procedure ICPC regionals ? Leave your comments below .

ACM !

So, its official now . My team got selected for ICPC onsite regional of Amritapuri !

Though, our performance was very bad but we got selected as we were the best team in our college.
We would like to make a mark in our first ever regional . Lets see what happens in the coding arena .

These days I'm learning and coding as much as I can . Expanding my armory with new techniques ranging from geometry to DP ,from bits to graphs.

After a long time I participated in a timed contest on codechef and stood 852 out of around 2500 contestants . Not one of my best but still good enough for a start after a very long time .

Yesterday I solved a question based on breadth first search and it felt so great after solving that as it was my first bfs problem . I was waiting for this for a long time .

Thanks for reading and keep coding !

Decrypting RSA cryptosystem

This week I was busy in making my Computer Science presentation . I chose prime numbers as the topic of my presentation .

Here are some of the highlights from my presentation .

We all know what are prime numbers right ? ok let me remind you again . Prime numbers are those natural numbers which are greater than 1 and doesn't have any positive divisors other than 1 and the number itself ,

Then I presented a very simple way to generate prime numbers Sieve of Eratosthenes if you don't know what is it you can check Sieve of Eratosthenes for more details .

You must be thinking that ok prime numbers are difficult to find but what are their real world applications ? How are they useful to a layman ?

Interestingly, a layman and you too might be using prime numbers that too almost daily! How ?

We all have accounts on google,facebook,twitter,etc,. and we do online shopping also from websites like amazon,ebay,flipkart,etc,.

To keep our personal data secure these sites use some form of cryptosystem to secure our invaluable data such as messages,passwords,credit card numbers,etc,.

They use some form of RSA cryptosystem for this .

RSA algorithm is one of the most widely used algorithm in today's world . Our cyber safety relies on this method . Let's have a look how this algorithm protects us from the hackers.

Working of RSA cryptosystem -

STEP 1 - Key generation

    Public key -
    Host sites randomly generate two very large prime numbers P,Q and multiply them to get N

    For ex lets say P=53 & Q=59
    N = P*Q = 3127
    N is the first part of the public key.
    second part of the key e is selected according to the constraints that e should be 1<e<phi(N) and         gcd(e,phi(N))=1 , where phi() is Euler Totient Function.
    Click here for algorithm for gcd()
   for simplicity lets say e = 3 in our example.
   Public key is made public .That means everyone has access to numbers e and N.

  Private key -    

  This is the secret key which is not made public and is only available to host .
 
  Representing it by d it is calculating by solving d*e mod phi(N) =1 (euler's theorem is used for    calculation).

Now, you must be thinking that anyone can calculate d as everyone know N and e .This is where beauty of prime numbers lie :) .

RSA works on the principle that  Prime factorization of a number is a fundamentally hard problem . It take a lot of time to factorise a big number .It can take 1000s of years to break a very big number even with network of supercomputers with the current level of technology!

remember phi() function ? to calculate phi(N) we need to have factorisation of N known to us .

If calculation of phi is so much hard how host does it ? :) Its because host knows the factorisation of N which is P*Q and phi(Prime no.) = Prime no. - 1 and phi also obeys multiplicative property so phi(P*Q)=phi(P)*phi(Q)

STEP 2 - Encryption

Suppose user is sending a message "HI"
This message is converted to a number m by a generalised padding scheme . For simplicity lets convert alphabets to numbers according to their order i.e, A-1,B-2,C-3 and so forth.
so in our example HI gets converted to 89 H->8 I->9

Then by applying N and e on m our web browser encrypts m to c like this m^e mod N = c
Then it sends c to the host.

STEP 3 - Decryption

Host receives c and applies its secret private key d on it to get m like this c^d mod N = m
Then by reverse applying padding scheme on obtained m host gets "HI" .

This is how our data is secured. Thanks to prime numbers.

Some interesting facts -

Till now the biggest key broken is a 768 bit key . It took a team of 11 cryptographers to break it and that too in 2 years!

With present level of prime factorization technique and computational ability it is estimated that a 1024 bit key can be broken within some years.

As 1024 keys are vulnerable now, google upgraded its SSL key from 1024 bit to 2048 just 1 year back. Twitter also uses 2048 bit keys.

It is estimated that by 2030 even 2048 bit keys will be vulnerable to attacks.    

If you can break a 1024 bit key you can become famous ! and till now nobody has done that.

So,now whenever you are making an online transaction stay relaxed for security reasons as prime numbers are there to keep your data secure .

I hope you enjoyed this write up on application of prime numbers .If you want to ask or correct my mistakes do comment in the comment box .

If you liked my post subscribe to my blog for more such exciting posts . Thank You 

Triangle Triangle everywhere not a point to think

Suppose we have 3 points which are making a triangle and we need to find whether a given point P is in the triangle or not .

There are many ways to do this problem but a very simple method is -

Lets say the triangle is made by three vertices A,B,C and the coordinates of the points are (x1,y1) , (x2,y2) , (x3,y3) and lets say point P is (a,b) so we just need to check whether the sum of the area of the triangle formed by the points A,B,C taken 2 at a time and P is equal to the area of the triangle ABC or not . Not getting it right ? No need to worry at all :)

Let ar(ABC) denotes the area of the triangle ABC. So, we just need to check whether

ar(ABC) = ar(ABP) + ar(BCP) + ar(CAP)

we can calculate the area of the triangle by the formula -
area = abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0)

If it is equal then the given point P is in the triangle ABC .

To understand it better lets look at the figures below -

When P lies inside the triangle ABC

In this figure P is inside the triangle ABC and this can be easily seen that ar(ABP) + ar(BCP) + ar(CAP) = ar(ABC)

so we conclude that P lies inside ABC .

When P lies outside the triangle ABC

 In this figure P is outside the triangle ABC so the ar(ABP) + ar(BCP) + ar(CAP) is not equal to ar(ABC) as they include additional area of triangles BDP and DCP . 

TIP :  This observation can be applied to find whether a given point lies inside a given n-polygon or not by taking the area of triangles and equating it to the total area of the polygon . 

I hope you would've found this post informative and useful . For any suggestions just post a comment below. 

Have a good day . 

Gaining the momentum

This week I was revising my previously learned algorithms/theorems . This includes sieve of Eratosthenes,Game theory,modular exponentiation,etc,.

Its time to increase my knowledge base . These days instead of participating in online contests(other than ACM related) I'll be only learning new things and posting about them in detail in my coming posts . So, stay tuned for some amazing stuff coming shortly ;)

I was also trying my hands on application development . I am learning to make a simple calculator using C++ .

Thanks for reading .
 

Back in Action !

"Sometimes a break is all you need" . My mid semester exams are over and now, I am totally free as I  have holidays . I am not going to my home . Instead I've planned to add new data structures and algorithms in my arsenal . These 15 days will going to be a lot more exciting and adventurous as for past 14 odd days I wasn't coding .

After the break I am back and ready to give my 100% .

Let the code begin ! 

Ups and downs again .

This week was not very good but still I learned a lot . Not very good because I didn't rise up in terms of ratings and scores but good as I still learned may new things , things which can only be learnt through failures after all a monotonously increasing graph is really 'monotonous' .

1. I couldn't solve a single question in the Codechef's long contest .(I just can't believe it,I think I didn't try much harder).
2. My last 2 matches on codeforces were not so good as my rating decreased heavily .
But at the end of the week.
My team got selected for Codesprint contest (National contest) and we solved all the questions given and in that I played a major role in solving 2 toughest questions(only 1 was a little bit trickier the other was easy).

Life is so much funny, sometimes you fall down sometimes you rise like anything.

I care less for results and more for actual learning because results are the outputs and if you don't give some input how will you get output ?

My mid semester Examinations are coming next week . So, I'll be taking a short break from programming because academics are also necessary .

Thanks for reading . Keep learning . Keep coding . 

Another amazing week !

These days I am learning concepts related to number theory . As said by C.F. Gauss "Mathematics is the queen of sciences and number theory is the queen of mathematics" I learned a lot this week some of the things which I learned includes Fermat's Primality Test,Goldbach's conjecture, finding primitive root of a prime,etc,.

This week I participated in Topcoder SRM also and solved 2 problems out of three . In the beginning of the contest I was messing with the 250 pt problems and I took a lot of time to get it correct I was at the 18 or 19 th position in my room of around 25-30 contestants but I solved the 2nd problem slightly fast and ended up with 7th position and added some positive points in my rating :) .

Thanks for reading . 

One more great week !

This week was very good in terms of my ratings in the various online contests. 

For the first time I solved 3 Div 2 problems in a codeforces round and now I am at my all time highest rating of 1457 . I solved a question in SRM also and now my rating is above my past 4 months record . 

We solved 1 question in TCS codevita too .  

Today I solved a problem in Codechef's Lunchtime too.

This weekend I was developing a GUI in python using tkinter . I made a simple quiz with some options as buttons on it .Clicking on the buttons displays comment(Label) on your selection in a funny manner . I'll add some more features to it in the coming weeks .  

We are planning to take part in ICPC online rounds as the first team from our college . Lets see what we'll be able to do . 

Thanks for reading . 

In love with codes

These days I am truly enjoying programming . Learning new & exciting techniques/algorithms .

Now,I've started challenging  my friends to see who is better at competitive programming . This week I participated in codeforces Div2 round and solved 1 problem but I lost to my friend Sudharsan who got it correct in first go and that too within 14 minutes , that's very impressive start but I don't like to lose much and I'll come back strong .

These days I am solving problems on codeforces .

Surprisingly we(me & Sudharsan) got selected for round 2 of TCS coding contest and will try to best in the second round as we couldn't do well in our first round .

Last night I was solving a problem which required factors of a no. to be calculated first . I was thinking of searching the method on the net but then I decided that I'll try it out myself first . I came with an idea and it worked

Suppose we want to calculate factors of N (including 1 & N itself)
for(i=1;i<=sqrt(N);i++)
{
     if(i*(N/i)==N)
    {  
        printf("%d",i);
        if(i!=N/i)
        printf("%d",i);
     }
}
This will print all the factors of N . If statement is included to avoid repetition of 1 if we write N = 1.

Today I've challenged my friends in Codechef's Cook off . Lets see who wins . Waiting for the round to commence .

Thanks for reading and keep coding .

Nice week

This week was very informative and a good one as I learned a lot .
I participated in TCS's Codevita contest with my friend and we solved 2/7 questions . We should have solved at least 4 but somehow due to lack of coordination among us(this was our first ever team contest) we could solve just 2 .

I solved 2 question in Codeforces weekly contest and now I am again a 'specialist' after a long time .(I know I am not :P )

I successfully solved Div 2 250 for 212 points in this week's SRM on TC and now my rating is 480 in 10 contests . I know its not good but still better than before .

This week I learned the implementation of Longest Common Subsequence and Longest Increasing Subsequence .

Thanks for reading and keep coding ! 

Exciting week !

This week was full of ups and downs (I like it ;) ). I started practicing div 2 500 problems on TopCoder but after 2 days I was having loads of academic work pending and unfortunatley I had to give up my idea of solving 3 problems a day . But I didn't stop coding . Everyday I was learning new & exciting stuffs . I started learning python and C++ (OOPS part) I fell ill also(Now I am fit) .

One of my batch mate  asked me about the working of the square root function I told him that it should behave like a standard function with some iteration by which it outputs the answer to a particular level of precision and then while learning python I came across Newton Raphson method to calculate square root of a given number . I was very excited to see such method .Its like -

suppose we want to calculate the sqrt of N -
1. Take a rough approximation of lets say x = N/2 (It can be taken anything but it is advised to make it close to the square root of N)
2.  Iterate -
                 y = (x + N/x)/2
                 x = y
3. stop iterating when you reach to a particular level of precision lets say 0.00001

 sqrt(N)
{
     x = N/2
     while(1)
    {  y = (x+N/x)/2
        if(abs(y-x)<0.00001)break
        x = y
    }
   return x
}
Wondering whether if this is the method behind the built in function sqrt ... Gonna search for it .

Yesterday, I gave an online contest on Codechef which was conducted by IIIT Delhi's programming club and got 362nd rank .. All questions were easy but I could solve only 2/5 due to lack of Algorithmic knowledge .

Thanks for reading and keep coding !

Practice Session

So, once again I am shifting to TopCoder to hone my programming skills .This time I am doing Div 2 500 problems . I am forming a team to apply for ICPC regionals . First ,we need to qualify for the onsite regional contest and if we are able to do that it will be great as we are just in our 2nd year and with very less experience in programming . Lets see what happens.

This week I was doing random problems and participated in Codechef's Long contest which is still going on . I've already done 2 problems in the contest .I am participating in Codevita also which will be conducted on Aug. 12.

I've written a C++ program for BFS and will try to apply it on some graph problems .  

Thanks for reading . 

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.

SPOJ Fever

ACM ICPC 2014-This year problems were hard as many good teams could solve only 3-4 problems. This time IIT Indore (A new IIT) secured the first place among Indian Colleges beating big colleges like IIIT Hyd,IIT Bombay,IIT Madras,IIT Roorkee . Congratulations to all the teams after all going for ICPC World Finals is in itself a big achievement .

This week I was a little busy in answering the queries of some curious souls who just now cleared JEE and about to join the premier institutes of the country, it always feels good to guide someone who is asking for your opinion.I always advise people to opt for that stream/branch in which they have interest .

 I took a break from my Topcoder practice and started SPOJ problems . For the first time I successfully applied a top down Dynamic Programming approach in 1 question . I was waiting for this moment for past 2/3 months . It feels very good after seeing a problem solved after so many unsuccessful attempts .

Sieve of Eratosthenes - 

I learnt how to apply Sieve of Eratosthenes. This method is very fast(for numbers of the order of some millions) to find whether a  given no. is prime or not . The approach is simple, suppose we have a no. N we want to find whether this no. is prime or not we just need to look at all the primes <=Square root(N) lets say we want to know whether 431 is prime or not so we need
  Sqrt(431) ~20.7 we just need to check whether primes <20 i.e. 2,3,5,7,11,13,17,19 can divide this no. or not .
So, 431 is an odd no. so not div by 2
sum of digits is 8 so not div by 3
end digit is 1 so not div by 5
431%7!=0 , 431%11!=0,431%13!=0,431%17!=0 and 431%19!=0 . Ohh! I took a random no. and it was a prime! I need to find the probability of finding a prime no. randomly from the set of natural no. :P Just kidding :D . Recently, I found out that this probability is inversely proportional to the logarithm of the chosen number N .

So this is how Sieve works and if you know all the prime less than sqrt(N) then this method is very fast .

Thanks for reading and keep coding .

Time for some Maths...

We lost humblefool this week in a car accident , he was a great coder(The first Indian who became red on Topcoder) he was excellent at coding and a nice person as well .It hurts a lot when a great person dies may God rest his soul in peace.

This week I was increasing my mathematical knowledge . Learnt many concepts regarding game theory especially Nim game after going through the rules of the game I came up with my own style to solve the game for ex - this game is played between two players A & B . On each turn the person will subtract a number given in the set lets say S = {1,4,5} from a given number N until we get a Zero the person which will not be able to subtract from the no. he gets will be the loser . N will be our starting number from which we will subtract 1,4 or 5 so that the player subtracting will win. Like every other player both A & B will try thier best to win this game so they will play optimally .'Optimally' in the sense that they will try some maths in their head to come up with the best solution i,e. to subtract which no. so they will win .

I came up with an idea like lets create a function for this game

 P(N)
 {
     if (N =1 or N=4 or N=5) return 1(denoting win with 1)
    else if(N=0 or N=2) return 0 (denoting loss with 0)
    else return ( P(N-1) or P(N-4) or P(N-5) )
 }

As we can clearly see if a person gets 1,4 or 5 he can directly subtract 1,4 or 5 from the no. he gets to arrive at zero and thus the other player won't be able to subtract any no. from a zero.
so in first if statement 1,4 and 5 are returning a WIN

for N=0 the first player won't be able to subtract any number so he will lose .For N=2 we can see that the person will be left with only one choice i.e. to subtract 1 from it so the 2nd player will arrive at N-1=1 so he will also subtract 1 from it thus arriving at Zero so that will be a loss for the first player so we return LOSS on 0 and 2

For rest no. I am taking OR from all the possibilities of subtracting 1,4,5 because if we get a 1 from any of these possibilities this will mean that the player will choose the winning move (Well that is the meaning of playing optimally).

So this function will give us the right result for this game.
We can optimize our function by memoizing our results using an array like we do in top up approach of Dynamic Programming ... that will save us a lot of time ..

Today morning I understood how to implement the Sieve of Erastonethes.That was amazing algorithm .
It was efficient O(NloglogN) as well as simple by logic Enjoyed implementing it.
I'll be increasing my maths knowledge as maths skills are very handy while programming.They can simplify one's code to a very large extent thus one just can't ignore maths while coding.

Thanks for reading. 

Couldn't stop to participate

Earlier I was thinking that I will not participate in any kind of competitions but I couldn't stop myself ....

Participated in the SRM 624 and guess what ? I submitted 2 div2 problems successfully a 250 & a 500 finishing at 8th place in my room 'my current best' previous best was 10th . Got 246 odd pts from the 250 pointer I think this is my best till now. 

The problems were very easy in this SRM that's why I could solve them(This is the truth).

I participated in Codechef's June Long contest also and solved 2 problems for the first time in a long contest.

So, definitely I am improving day by day I should not give practicing because practice is the key to get better at almost everything and coding competitions are no different. 

Learning how to climb

I am still practicing Div2 250 problems and when I get tired or frustated (when I stuck at some prob. for long) I start doing problems from other online judges like SPOJ,Codechef.

On Topcoder I am stuck at string problems like how to extract integer values from the given string
In some questions we are given string vectors and we need to manipulate the integer values like summing all the integers or some calculations involving them . I've found a way to deal with them . I am using c_str() and sscanf() functions but I am in a search of better technique to deal with them .

By the way, My college is at 11th page of institutions rankings on SPOJ currently ranked at 1042 . I want it to be in top 100 at least and for that to happen I need help from all my fellow batch mates and juniors. I hope one day we will be in top 100 . Currently I am ranked at 9903 worldwide on SPOJ .

Still practicing more and more problems ... A long way to go from now.... The journey has just begun ;)

Learning the hard way

So, now I've decided to push my coding skills to a new level. This week I was solving Div 2 250 problems on Topcoder . On an average I am doing 3-4 problems on it spending around 30-60 minutes on each of them trying to understand them and coding them.If I get stuck at something I am reading the editorials of the problem to further check my solution or to get new ways to do the same problem.This not only improves my coding skills but gives me a different approach to do the same question also.As of now I am not participating in SRMs and Codeforces contests  because I want to first sharpen my axe for a good amount of time and then cut the tree smoothly rather than cutting the tree with the blunt axe .

I am learning C++ these days.Its good to go with C++ when you have C basics with you.

Also this week I participated in Codechef's short contest and  managed to solve 2 problems . This was the first time when I could solve more than 1 problem on their contests and now I am ranked 1226 worldwide and 721 in my country in short contests.

I am certainly improving day by day . I can see that improvement as now I can think much more faster on how to solve a particular solution and I will continue to practice more and more..

A week full of algorithmic coding

Last sunday I participated in the round 1C of Google Code Jam 2014 and secured 4128 position after solving one small input problem ,that means I am out of my first ever GCJ participation . I am quite happy as well as satisfied with my performance in the competition as I am still in the early stages of learning phase I think my performance was good .

My performance in GCJ 14 at a glance -

Qualification Round - ranked 15128(Solved 3 problems)

Round 1A - 3624(without solving a single problem :P )

Round 1B - 6209(solved 1 ques)

Round 1C - 4128(solved 1 ques)

It may not look good but after knowing the fact that this performance was given by a person who learnt his first programming language just 5 months back!! it certainly looks good isn't it ?

I look forward to improve my algorithmic skills and I will make sure that I'll improve my performance in the next GCJ . 

Today my semester result got announced and I scored an 'Ex' 10/10 points in lab section of programming course and 9/10 'A' in Theory course .Good to see those letter grades in the grade sheet. :)

I was practicing binary search and top down approach(Dynamic Programming) these days .

I was amazed to see the power of simple algorithm of binary search thanks to the Topcoder tutorials. 

Algorithmic Coding Rocks!!!

Starting of summer vacation 2014

This week I was very busy in my end semester exams but I still participated in the round 1A of GCJ 2014 its a different story that I couldn't solve a single question but still I was trying for the whole 150 minutes to solve problems.Got a world rank of 3624 I think the problems were of good level that's why even after not solving a single question I landed up with this kind of rank.
 After a long time around 4 months I am again in my hometown ,it feels very nice to be in your home :) .

Participated in round 1B this sunday and I managed to solve 1 small input set problem but rest of them were not in my range(at this point of time).Secured a world rank of 6209.

Google Code Jam 14

I was new to programming and I recently started coding in december 2013. I started my coding life with C as it was there in my coming semester in the college and I was told by some friends that it is one of the best programming language when it comes to speed and overall performance.

I recently started doing competitive programming and I got to know about this famous coding competition conducted yearly by the most awesome company Google. At first I thought that I am not good at competitive programming right now so, I will participate next year but then I registered for it as it was free and nothing was going in just registering for it. Then I kept practicing on the Online Judges and other sites like SPOJ,Codechef,Codeforces,Topcoder. In just about a month I was growing rapidly . I started doing some easy problems and as time passed on I also leveled up :) about a week before the Qualification Round is about to begun I started thinking that why wait for next year? I should give it a try. I took it very lightly like I will just participate and see what happens there in the contest.

Then the contest day came 11 April 2014. The contest started at 4:30 AM and I was awake till 5:00 AM just to see the level of the problems and after seeing them I slept and woke up at 10:30 AM . Just after waking up I jumped over my chair , started my laptop and began my day with some fresh coding problems prepared by Google. I started with the easiest one "The Magic Trick".Firstly, I was thinking that I won't be able to do this problem but then I took some time to figure out that it was a simple problem. I coded it and then I got stuck :( when I was submitting my solution I found out that they have an entirely different way to judge my solution as compared to the coding sites I mentioned above . I was a little depressed after seeing that but then I googled it out as to how to submit solution after spending some time I got the method, all what was needed is to use File Handling and after figuring it out I was feeling excited as this concept was used in my previous programming class in my college (I didn't get it during the lecture though :P ) but then I again did some search on how to use file handling and BINGO!!! within minutes I came with the working idea and submitted my solution successfully . I was on cloud 9 that time . At first I just couldn't believe on my eyes that my solution got accepted and I scored my first points I just can't describe that moment . After that I started thinking of submitting some more solutions and surprisingly I managed to solve the problem B also and scored the needed 25 points to place myself in the next round ROUND 1 . Woah!!! I cleared the qualification round that too in my first attempt . This was one of the happiest day of my life. I was ranked 15121 among 49066 people who registered for the contest from over 165 countries and 2929 in my country .Later that day I called up my parents to tell them about this achievement and they were also happy to hear such a great news.

My friends also congratulated me and encouraged me to do well in the next round as well .

 I know that next round will not be an easy one. I practiced almost daily for the round 1A and see the round is just about to begun in an hour. I will give my best shot at this and see what happen there in the coding arena . 

Open Source Software - A beginning

These days I am learning how to contribute to open source software .It is fun as well as challenging task as you get to know the source code of some exciting projects and in order to understand them you need to dive into the great pool of code snippet . Its really exciting(I am very much excited just to think of contributing to an existing project) when you use your programming skills to understand or find a bug in the project. I am learning how to use git and github so that I can also contribute towards the success of a project that I like.
I just can't wait to show my coding skills and increase the quality of the projects. So just stay tuned and see a great software developer rising ;)