RandomNetwork | Topcoder Archive

Problem Statement

You are a given a String[] network, describing a network. Character j of element i of network is either 'Y' or 'N', indicating whether or not there is a direct path from node i to node j. The number of nodes in the network is equal to the number of elements in network.

A packet begins at node 0. In every step, it travels from its current node to a randomly selected connected node. All random selections are made with equal probability. Return a double[], where the i-th element is the probability that the packet is at node i after taking exactly steps steps.

Definition

Class:: RandomNetwork
Method:: probableLocation
Parameters:: String[], int
Returns:: double[]
Method signature:: double[] probableLocation(String[] network, int steps)
(be sure your method is public)

Notes

Each element of the return value must be within 1e-9 absolute or relative error of the actual answer.
The network is a directed graph, so a path from i to j does not necessarily mean there is a path from j to i.

Constraints

network will contain between 2 and 50 elements, inclusive.
Each element of network will contain N characters, where N is the number of elements in network.
Each character of each element of network will be either 'Y' or 'N'.
The i-th character of the i-th element of network will be 'N'.
Each element of network will contain at least one 'Y'.
steps will be between 0 and 100, inclusive.

Examples

```
{"NYYY", "YNYY", "YYNY", "YYYN"}
```
```
0
```
```
Returns: {1.0, 0.0, 0.0, 0.0 }
```
A tetrahedron, with all six edges bidirectional. We start at node 0, and make a single move, equally likely to any of the three other nodes.
```
{"NYYY", "YNYY", "YYNY", "YYYN"}
```
```
2
```
```
Returns: {0.3333333333333333, 0.2222222222222222, 0.2222222222222222, 0.2222222222222222 }
```
After 1 move, we have a 1/3 chance of being at any of the other 3 nodes. Each of them carries a 1/3 chance of returning to node 0, for a total of 1/3 * 1/3 + 1/3 * 1/3 + 1/3 * 1/3 = 3/9 = 1/3 chance. There is a 2/3 chance that the packet did not go back to node 0, thus a 2/9 chance of being at any of nodes 1, 2, or 3.
```
{"NYY", "NNY", "NYN"}
```
```
5
```
```
Returns: {0.0, 0.5, 0.5 }
```
After the first step, we're equally likely to be at node 1 or node 2. After that, each step just bounces the packet back and forth between nodes 1 and 2.

{"NYYNN", "NNYYN", "NNNYY", "YNNNY", "YYNNN"}

Returns: {0.375, 0.125, 0.0, 0.125, 0.375 }

{"NYYY", "NNYY", "NNNY", "YNNN"}

Returns: {0.5, 0.1111111111111111, 0.1111111111111111, 0.2777777777777778 }

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.