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 :-
