VisitEdges
SRM 844 · 2023-01-19 · by misof
Problem Statement
Time limit: 4 seconds.
The infinite grid graph is a graph whose vertices are all pairs of integers, and two vertices (x1,y1) and (x2,y2) are connected by an edge if and only if abs(x1-x2) + abs(y1-y2) = 1.
We can visualize such a graph as follows: Vertices are points in a horizontal plane with integer coordinates. We can draw two lines through each point, each of them parallel to one of the coordinate axes. For each of these lines, each pair of consecutive vertices on the line is connected by an edge.
You start a random walk in the vertex (0, 0).
In each step of the walk you traverse one of the four edges that lead from your current vertex.
These four edges point north (y increases), south (y decreases), east (x increases), and west (x decreases).
You are given the
Your walk terminates as soon as you traverse the M-th distinct edge.
Calculate and return the expected number of steps in your random walk.
Notes
- The meaning of "relative probabilities" is as follows: the probability of moving north in any step is N / (N + S + E + V).
- Return values with an absolute or a relative error at most 1e-9 will be accepted.
Constraints
- M will be between 1 and 7, inclusive.
- N, S, E, and W will each be between 0 and 10, inclusive.
- At least one of N, S, E, and W will be positive.
3 1 0 0 0 Returns: 3.0
In each step we go north. In three steps we are guaranteed to traverse three distinct edges.
3 1 1 0 0 Returns: 6.0
In each step we flip a fair coin whether we go north or south. In this setting visiting three distinct edges might take longer, as, for example, we can start by going north, south, and north again. We just performed three steps but we are still not done: we have still only traversed one edge (three times).
3 1 1 1 1 Returns: 3.761904761904762
Perhaps paradoxically, adding even more possible directions now somewhat decreases the expected number of steps.
1 4 5 6 7 Returns: 1.0
Regardless of the probabilities, in the first step we are guaranteed to traverse a new edge.
4 4 5 6 7 Returns: 5.276493355280059
Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class VisitEdges with a public method double solve(int M, int N, int S, int E, int W) · 41 test cases · 2 s / 256 MB per case