FillInTheDAG | Topcoder Archive

Problem Statement

You are given a directed acyclic graph with n nodes and m edges. The edges are given in the int[]s f, t denoting a directed edge from node f[i] to node t[i]. The nodes are given in topological order (so f[i] < t[i] for all i). Node 0 is guaranteed to be the only node with no incoming edges. Node n-1 is guaranteed to be the only node with no outgoing edges.

You want to label nodes with rational numbers such that the following holds.

Let x_v be the value of the v-th node. The node 0 must have value x_0 = 0 and the node n-1 must have value x_{n-1} = 1. All other nodes must satisfy 0 ≤ x_v ≤ 1.

For all non-source and non-sink nodes, x_v must be the average of the smallest value of a node that it can reach and the largest value of a node that can reach it. More formally, let S(v) be the set of nodes reachable from v (not including v), and let T(v) be the set of nodes that can reach v (not including v). Then, x_v must be equal to ((min_(y in S(v)) x_y) + max_(z in T(v)) x_z)) / 2 for all nodes v from 1 to n-2.

Return this as a long[] of nonnegative integers with the following format { p_0,q_0, p_1,q_1, ..., p_{n-1},q_{n-1} }. Here, this represents setting x_i = p_i/q_i (p_i and q_i do not need to be coprime). If there are multiple possible answers, output any of them. If there are no answers, return an empty long[]. It is guaranteed under the current constraints that if there is an answer, then there is one where all results fit in a signed 64-bit integer.

Definition

Class:: FillInTheDAG
Method:: findWay
Parameters:: int, int[], int[]
Returns:: long[]
Method signature:: long[] findWay(int n, int[] f, int[] t)
(be sure your method is public)

Constraints

n will be between 3 and 100.
m will be between 2 and 1,000.
f,t will contain exactly m elements each.
0 <= f[i] < t[i] < n for all valid i.
Node 0 will be the only node with indegree zero.
Node n-1 will be the only node with outdegree zero.

Examples

```
3
```
```
{0,1}
```
```
{1,2}
```
```
Returns: {0, 1, 1, 2, 1, 1 }
```
In this case, the only solution is to assign x_0 = 0, x_1 = 1/2, and x_2 = 1.
```
6
```
```
{0,1,2,4,0,3}
```
```
{1,2,4,5,3,4}
```
```
Returns: {0, 1, 1, 4, 1, 2, 3, 8, 3, 4, 1, 1 }
```
This solution corresponds to setting x_0 = 0, x_1 = 1/4, x_2 = 1/2, x_3 = 3/8, x_4 = 3/4 and x_5 = 1.

{0,0,0,1,1,2}

{1,2,3,2,3,3}

Returns: {0, 1, 1, 3, 2, 3, 1, 1 }

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.