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