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 .

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 ;)