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 integerN, the number of test cases. Each of the nextNlines will then contain a single test case. Each test case will start with integersRandC, the number of rows and columns (Rwill be odd). Next, an integerKwill specify the target column. Finally, an integerMwill be followed byMpairs of integerrand_{i}c, giving the locations of the missing pegs._{i}

Constraints

1 =N= 100

3 =R,C= 100The top and bottom rows will not have any missing pegs.

Other parameters will all be valid, givenRandC

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 columnsK, 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**.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
char pegs[2000][2000]; void initPegs(int R, int C) { int c, CLim, k; for (int r = 0; r < R; r++) { if (r%2==0) {CLim = C-1; k = 0;} else {CLim = C-2; k = 1; pegs[r][0] = '#';} for (c = 0; c < CLim; c++) { pegs[r][2*c+k] = 'x'; pegs[r][2*c+1+k] = '.'; } pegs[r][2*c+k] = 'x'; pegs[r][2*c+1+k] = '#'; } } void setMissingPeg(int r, int c) { if (r % 2 == 0) { pegs[r][2*c] = '.'; } else { pegs[r][2*c+1] = '.'; } } double ways[2000][2000]; double putBall(int colK, int targetCol, int R, int C) { for (int i = 0; i < 2000; i++) for (int j = 0; j < 2000; j++) ways[i][j] = 0.0; ways[0][2*colK+1] = 1.0; for (int i = 1; i < R; i++) { for (int j = 0; j < 2*C-1; j++) { if (pegs[i][j] == '.') { if (pegs[i][j-1] == 'x') { if (i%2 == 1 && j == 2) ways[i][j] += ways[i-1][j-1]; else ways[i][j] += .5 * ways[i-1][j-1]; } if (pegs[i][j+1] == 'x') { if (i%2 == 1 && j == 2*C-4) ways[i][j] += ways[i-1][j+1]; else ways[i][j] += .5 * ways[i-1][j+1]; } if (pegs[i-1][j] == '.') { ways[i][j] += ways[i-1][j]; } } } } return ways[R-1][1+2*targetCol]; } int main() { int N, R, C, K, M, r, c; cin >> N; for (int i = 0; i < N; i++) { cin >> R >> C; initPegs(R, C); cin >> K; cin >> M; for (int j = 0; j < M; j++) { cin >> r >> c; setMissingPeg(r, c); } int maxCol = 0; double maxP = 0.0; for (int j = 0; j < C-1; j++) { double p = putBall(j, K, R, C); if (p > maxP) { maxP = p; maxCol = j; } } printf("%d %.6f\n", maxCol, maxP); } } |

I was using recursion in my solution that worked for the test suites, but failed to scale up for the input file.

0Thanks for posting your code. But can you please also upload the code which can be readily used to generate an output file.

0@Anonymous,see you many times on glassdoor,careercup,see you here again…

0what about from bottom to up?

If the ball is to fall into the spot K, then find the upper position from which it is possible for the ball to fall into K. Go up from layer to layer. The position on the top with max possibility is the one.

Use a queue, first put {2, 1} into queue, where 1 describe the possibility.

x.x.x.x.x

x…x.x

x…x.x.x

x.x…x

x.x.x.x.x

Then pop out (2,1}, add{2,1} on level 5;

Pop out (2,1}, add{3,0.5} on level 4;

Pop out {3,1} , add{2,1/8} {3,1/4},{4,1/8} on level 3;

Pop out all, and add {3,1/4}{4,1/4}{5,1/16} on level 2;

Pop out all, and add {2,1/8} {4, 1/4} {6, 1/32}

So the answer is 4.

Is this idea right?

0actually I think you don’t have to initialize the “game”. I use back tracking to solve this problem. And it can be optimized by remembering previous probability of (r, c), so the final running time will be o(n), here n is the input size.

00I don’t know why I cannot put complete code. Last try:

typedef struct misspair{

int r;

int c;

}M_PAIR;

M_PAIR mpair[3] = {{1,3}, {2, 2}, {3,5}};

bool isMissing(int r, int c){

for(int i=0; ipr ? pl : pr; //and store its probability

}

}

}

double solvePegGame(int R, int C, int K){

double maxP = 0;

for(int i=0; ipr ? pl : pr;

}

if(maxP < p)

maxP = p;

}

return maxP;

}

0