Facebook Hackercup

Recently Facebook organised a event "Hackercup". Though there was not much of hacking , as it was an algorithmic contest. Problems were kind of easy, as per Qualification round standards.

However , initially there were many confusions. As no one knew about contest page and type of contest (we have to submit code or Output file). And also even after the start of contest , 6 minute
time limit was not known to anyone. So some of friends were unable to submit a problem.

But Nonetheless, the Contest was good, and I hope that Round 1 will be better than this. Though there were three problems, I want to discuss second one "Peg game", You can read the problem statement at
http://www.facebook.com/hackercup/problems.php?round=4
OR
http://pastebin.com/1n8TQePW

Peg game
In this problems , there is given a matrix of pegs , where no two pegs can be horizontally or vertically adjacent. A ball is thrown from the top, and whenever it strikes a peg it has equal probability of falling left or right except when it is at the boundary. Given a final destination column and matrix arrangement , You have to determine the column, from which we should let the ball fall , so that there is a maximum probability of it falling through the destination
column.
Example :-
The image below shows an example of a game with five rows of five columns. Notice that the top row has five pegs, the next row has four pegs, the next five, and so on. With five columns, there are four choices to drop the ball into (indexed from 0). Note that in this example, there are three pegs missing. The top row is row 0, and the leftmost peg is column 0, so the coordinates of the missing pegs are (1,1), (2,1) and (3,2). In this example, the best place to drop the ball is on the far left, in column 0, which gives a 50% chance that it will end in the goal.

x.x.x.x.x
x...x.x
x...x.x.x
x.x...x
x.x.x.x.x
^

A easy solution is to let the ball from each and every column and calculate its probability of reaching the Goal : Complexity O(R*C*C)

Or we can use a bottom up methodology, i.e. we calculate the probability of ball reaching goal if reaches that column, and we calculate this value for all rows beginning from the lowermost.
And in this method for any row "the probablity to reach goal from any column" can be calculated using values which were generated using calculations of previous row.
Complexity : O(R*C)


Here is my code for it :-

Optimized Sieve of Eratosthenes

Sieve of Eratosthenes is a very good and famous method for finding a large number of primes. It is based on a general idea to flag out those numbers which are composite, and thus the numbers which remain are prime.

However, it can be optimized and there are a number of ways to do it.
There are many problems on Spoj, UVa that can be solved using sieve method.
One can extend general notion of sieve to solve other problems related to ETF, LCM, GCD, divisor summation etc.



Here is my code for it :-





The idea behind optimization is to leave those numbers which are divisible by 2 and 3.
It makes the sieve 3 times faster.


Here are some problems that can be tried with optimized sieve:

PRIME1
FINDPRM
CPRIME
TDKPRIME
TDPRIMES

Learning J2ME

Learning mobile programming is quite adventurous as you will find later on.

Mobile programmming can be done in a no. of languages, python looks very easy for this purpose.

However I am using J2ME, JSR 82 for my appication development.

If you are planning to run your application on nokia mobiles you need to know which SDK you will need. for example I have nokia 5130, and for that I use Nokia, series 40 fp1 lite.
you can find this information on http://www.forum.nokia.com/ .

you will have to download the sdk, ( Software development kit ), for your own mobile model.

For samsung mobiles check this ..
http://developer.bada.com/
They are organising samsung bada developer challenge, with total prize money of $2,700,000 . As you can see it is quite attractive.

hi all

This blog I will publish posts related to coding puzzles of UVa , topcoder , spoj.pl , codechef and various other , that I ma come around.

I will also like to post about some languages that I am learning which includes J2ME and python.

so keep coding.


Happy coding