HittingTime | Topcoder Archive

Problem Statement

Given a graph g, we start at node 0 and perform a random walk. What is the expected number of steps required to reach node target?

The graph will be given as a symmetric String[], where character i of element j is a '1' (one) if there is an undirected edge between nodes i and j, and '0' (zero) otherwise. To perform a random walk, we start at node 0 and then follow edges randomly. For instance, if there were 5 edges incident to node 0, we would select each one with probability 1/5. Imagine that we selected an edge to node 17. We would then move to node 17 and count how many edges were incident to it (including the edge back to node 0). If there were 2 edges from node 17, we would pick randomly between them, following one of them.

Definition

Class:: HittingTime
Method:: hit
Parameters:: String[], int
Returns:: double
Method signature:: double hit(String[] g, int target)
(be sure your method is public)

Constraints

g will represent a simple (no self-loops), connected, undirected graph with between 1 and 30 nodes, inclusive, as described above.
target will be between 0 and the number of elements in g minus one, inclusive.

Examples

```
{"010",
 "101",
 "010"} 
```
```
2
```
```
Returns: 4.0
```
This test represents a chain of 3 nodes: 0----1----2 Starting at node 0, there is only one edge to follow, leading us to node 1. From node 1, we have a 50% chance of going to node 2, and a 50% chance of going back to node 0. Thus, half the time we will reach node 2 in two steps, and half the time we will be back where we started. So, if X is the expected number of steps it will take to get to node 2, we can write: X = 2 + (1/2) * X + (1/2) * 0 Solving for X gives us 4.
```
{"011","101","110"}
```
```
2
```
```
Returns: 2.0
```

{"01100",
 "10010",
 "10011",
 "01101",
 "00110"}

Returns: 4.363636363636341

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.