Connection Status:
Competition Arena > ProbabilisticAlice

ProbabilisticAlice

2018 TCO Argentina Fun · 2018-04-20 · by wittyceaser

2018 TCO Argentina Fun · 2018-04-20 · by wittyceaser · Dynamic Programming, Math
Class Name: ProbabilisticAlice
Return Type: double
Method Name: computeExpectation
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

The city of Gridland can be seen as a matrix of cells with R rows and C columns. The rows and columns are numbered starting from 0. Some cells are empty, others contain teleporters. Each teleporter transports people from its cell to the cell (0, 0).

You are given the map of the city in the String[] grid. The character 'T' represents a teleporter, the character '.' an empty cell.

Alice is a tourist who just visited Gridland. She is currently in the cell (0, 0) and she wants to reach the cell (R-1, C-1). While moving around the city, Alice follows a simple set of rules:

  • Whenever she moves, she moves to a cell that is adjacent to her current cell and closer to her goal. Thus, in general, from the cell (i, j) she will move either to (i+1, j) or to (i, j+1).
  • If Alice only has one valid move, she makes it.
  • If Alice has two valid moves, she flips a biased coin to choose one of them.

You are given the ints pnum and pden. Let p = pnum / pden. Whenever Alice is in some cell (i, j) and she has two valid ways to move, she moves to the cell (i+1, j) with probability p and to the cell (i, j+1) with probability 1-p.

Compute and return the expected number of times Alice will get teleported back to (0, 0) before she reaches the cell (R-1, C-1). If Alice cannot reach her target cell at all, return -1 instead.

Notes

  • Your answer will be accepted if it has an absolute or a relative error at most 1e-9.

Constraints

  • R and C will each be between 2 and 20, inclusive.
  • grid will contain R elements.
  • Each element of grid will contain C characters.
  • Each character in grid will be either 'T' or '.'.
  • grid[0][0] will be '.'.
  • grid[R-1][C-1] will be '.'.
  • pden will be between 2 and 1000, inclusive.
  • pnum will be between 1 and pden-1, inclusive.
Examples
0)
{"..",
 ".."}
1
2
Returns: 0.0

There are no teleporters. Alice will reach her goal without getting teleported.

1)
{".T",
 ".."}
1
2
Returns: 1.0

When standing in the cell (0, 0). Alice always flips a fair coin to choose where to go next. With probability 1/2 she moves down, and from there she will reach her goal. With probability 1/2 she moves to the right, steps into the teleporter, and gets teleported back to where she started. One possible path Alice can take: Step right, get teleported back, step right, get teleported back, step down, and step right to reach the goal. She will take this particular path with probability 1/8. One way of computing the expected number of times she will be teleported is as follows: She will be teleported 0 times with probability 1/2. She will be teleported 1 times with probability 1/4. She will be teleported 2 times with probability 1/8. ... Thus, the expected number of times she will be teleported is 0 * (1/2) + 1 * (1/4) + 2 * (1/8) + ... = 1.

2)
{".T",
 ".."}
46
47
Returns: 0.021739130434782705

The map is the same but now Alice almost always moves downwards. Thus, the expected number of times she hits the teleporter is now much lower.

3)
{".....T.",
 "....T..",
 "T..T..."}
2
3
Returns: -1.0

In this city Alice will never reach her goal.

4)
{"....T.",
 "...TT.",
 ".T....",
 "...T..",
 "......"}
3
7
Returns: 5.417334860633832

One of these teleporters is in a place Alice will never reach.

Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ProbabilisticAlice with a public method double computeExpectation(vector<string> grid, int pnum, int pden) · 85 test cases · 2 s / 256 MB per case

Submitting as anonymous