A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

Read the rest of this entry →

A pile of nuts is in an oasis, across a desert from a town. The pile contains ‘N’ kg of nuts, and the town is ‘D’ kilometers away from the pile.

The goal of this problem is to write a program that will compute ‘X’, the maximum amount of nuts that can be transported to the town.

The nuts are transported by a horse drawn cart that is initially next to the pile of nuts. The cart can carry at most ‘C’ kilograms of nuts at any one time. The horse uses the nuts that it is carrying as fuel. It consumes ‘F’ kilograms of nuts per kilometer traveled regardless of how much weight it is carrying in the cart. The horse can load and unload the cart without using up any nuts.

Your program should have a function that takes as input 4 real numbers D,N,F,C and returns one real number: ‘X’

Read the rest of this entry →

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string. Read the rest of this entry →

At the arcade, you can play a simple game where a ball is dropped into the top of the game, from a position of your choosing. There are a number of pegs that the ball will bounce off of as it drops through the game. Whenever the ball hits a peg, it will bounce to the left with probability 0.5 and to the right with probability 0.5. The one exception to this is when it hits a peg on the far left or right side, in which case it always bounces towards the middle.

When the game was first made, the pegs where arranged in a regular grid. However, it’s an old game, and now some of the pegs are missing. Your goal in the game is to get the ball to fall out of the bottom of the game in a specific location. Your task is, given the arrangement of the game, to determine the optimal place to drop the ball, such that the probability of getting it to this specific location is maximized.

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
 G

‘x’ indicates a peg, ‘.’ indicates empty space.

Input
You should first read an integer N, the number of test cases. Each of the next N lines will then contain a single test case. Each test case will start with integers R and C, the number of rows and columns (R will be odd). Next, an integer K will specify the target column. Finally, an integer M will be followed by M pairs of integer r_i and c_i, giving the locations of the missing pegs.

Constraints
1 = N = 100
3 = R,C = 100

The top and bottom rows will not have any missing pegs.
Other parameters will all be valid, given R and C

Output
For each test case, you should output an integer, the location to drop the ball into, followed by the probability that the ball will end in columns K, formatted with exactly six digits after the decimal point (round the last digit, don’t truncate).

Notes
The input will be designed such that minor rounding errors will not impact the output (i.e. there will be no ties or near — up to 1E-9 — ties, and the direction of rounding for the output will not be impacted by small errors).

Here is my problem analysis for Facebook Hacker Cup Qualification Round: Peg Game.

Peg Game Problem Analysis:
This is the most confusing problem of the three problems due to the problem description being unnecessary long and ambiguous. You can see how many people are asking clarifications for this problem in the wall posts compared to the other problems (I really think Facebook should create a clarification section to answer people’s questions). Besides, the example they used to illustrate the problem is not included in the sample input, which doesn’t help at all.

It definitely takes me more than few times re-reading the problem description to finally “guess” what they really mean. Anyway, after understanding the problem, it is not that difficult to code the solution using a direct simulation.

However, there are a few places where you need to be careful, and I found that most people fall into this fallacy below:

Why the above approach is incorrect? This is simply because one necessary condition for the above statement to be true is that ways that reaches the bottom must all be equally likely. Unfortunately, this is not necessarily true.

The correct method is to multiply the probabilities as the ball falls in a step-wise fashion. You would also need to determine if the ball is at an edge peg. If it is at an edge peg, then the ball always fall toward the opposite direction of the edge peg with 100% chance. On the other hand, if it is not at an edge peg, then it will fall in either direction with 50-50 chance.

Below is the coded solution for Peg Game.

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3² + 1². Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. Read the rest of this entry →

Facebook decided to launch Hacker Cup, a programming contest to attract the world’s best talents to their HQ. The qualification round started on Friday 4pm (US’s PST timezone) and continues for 72 hours, so go ahead and join now.

Just finished Facebook Hacker Cup Online Qualification Round and thought that I might share some of my thoughts about it.

Just like Google’s CodeJam, this round consisted a total of three problems, and you would need to solve just one of the problem correctly to qualify for the next round.

I admit, I had a lot of fun in this round (which had a lot of hidden surprise in the problems), but the contest’s interface totally suck the hell out of a rhino’s @$$. And seemed like I am not the only one who agrees on this.

The first glitch that really got on my nerves –
As you download the input file, the timer starts to countdown, without you knowing about it. Then, I found a little notice on the corner saying that you would have to refresh the browser after downloading the input file to see the timer. I don’t know why, but this seemed stupid and unacceptable to me.

Second, when you want to submit the answer, it opens up a small text box (by small I mean something like 10×100 pixels), and you are suppose to paste your program’s output to that little text box. What a FAIL — They could have done much better.

Third, after you submitted the answer, there is a message box that mentioned that you would need to wait until the contest is over to find out if your answer is correct. Oh well… On the other hand, the timer just continue on ticking until it says “Time expired”. You get multiple chances to submit your answer, but ONLY within the limited time. I learned the hard way. My advice to you is test your code carefully for edge cases before downloading the input. During the limited time you won’t be able to do much about it if you find that your code has a bug.

Anyway, enough ranting and let’s move on to the fun part, which are the problems itself.

Double Squares:
This is a really fun problem with a little surprise behind it. While you are reading the problem, you would notice a little subtitle under the main title “Facebook Hacker Cup” that says “Too hard for brute force, switching to dp“. It’s there for a purpose. I knew I did not get this correct because of their timer display requires a browser reload…

Peg Game:
You need to read this problem carefully. Don’t worry, you won’t need much from theory of probability. Reminds me of the binomial theorem. If there are no missing pegs, then the probability of each column could be calculated easily using binomial coefficients. This problem is pretty straight forward, but you need to be some what careful.

Studious Student:
This is a fun problem. It is easy to understand the problem statement and it is also easy to fall into a trap. This problem is not as straight forward as you think it might be.

I will post my analysis and solution after the contest is over. Till then have fun solving the problems!

Imagine you have a special keyboard with the following keys:

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. Read the rest of this entry →