FillInTheDAG

SRM 774 · 2020-01-09 · by lg5293

SRM 774 · 2020-01-09 · by lg5293 · Brute Force, Graph Theory, Greedy

Show categories

Class Name: FillInTheDAG

Return Type: long[]

Method Name: findWay

Arg Types: (int, vector<int>, vector<int>)

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.

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.

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

92
{0, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 0, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 0, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 0, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 0, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0, 13, 14, 15, 16, 17, 18, 19, 20, 0, 7, 8, 9, 10, 11, 12, 0, 3, 4, 5, 6, 0, 1, 2, 16, 71, 27, 6, 9, 6, 29, 51, 35, 4, 0, 16, 38, 22, 36, 39, 11, 20, 43, 9, 12, 46, 65, 51, 54, 5, 59, 16, 52, 59, 7, 44, 31, 61, 37, 10, 44, 20, 72, 3, 28, 12, 4, 21, 8, 20, 1, 8, 5, 32, 10, 0, 27, 22, 39, 6, 38, 56, 32, 64, 1, 24, 24, 64, 26, 67, 5, 5, 42, 30, 57, 18, 43, 24, 45, 16, 61, 30, 29, 8, 11, 42, 47, 29, 44, 35, 33, 20, 9, 11, 1, 38, 78, 65, 31, 20, 56, 27, 63, 20, 6, 10, 35, 39, 22, 51, 86, 9, 5, 19, 16, 46, 42, 34, 28, 0, 14, 19, 28, 44, 4, 26, 13, 26, 47, 32, 9, 2, 29, 4, 4, 31, 10, 19, 57, 40, 28, 2, 56, 67, 7, 7, 27, 45, 19, 49, 26, 20, 6, 12, 22, 50, 18, 59, 35, 4, 38, 33, 3, 60, 47, 49, 6, 34, 49, 17, 5, 29, 17, 8, 21, 6, 4, 75, 31, 0, 16, 37, 19, 38, 0, 37, 24, 5, 50, 5, 41, 37, 32, 59, 47, 13, 13, 22, 3, 76, 3, 15, 1, 2, 13, 2, 35, 6, 0, 26, 11, 19, 54, 34, 12, 36, 59, 11, 1, 34, 15, 23, 1, 29, 53, 19, 0, 51, 52, 38, 31, 39, 9, 22, 8, 81, 30, 28, 48, 34, 48, 63, 39, 39, 5, 38, 31, 72, 7, 51, 42, 18, 48, 16, 1, 48, 39, 4, 13, 65, 15, 7, 25, 39, 30, 25, 51, 41, 48, 7, 66, 0, 57, 13, 24, 34, 2, 75, 4, 26, 26, 20, 35, 61, 50, 14, 0, 10, 49, 15, 6, 41, 27, 8, 0, 29, 52, 35, 0, 33, 47, 47, 0, 10, 28, 24, 5, 40, 36, 32, 14, 46, 23, 10, 61, 3, 30, 49, 36, 28, 40, 33, 53, 11, 45, 43, 12, 3, 3, 63, 22, 6, 42, 25, 3, 26, 68, 37, 46, 29, 13, 23, 39, 8, 11, 8, 25, 25, 40, 31, 65, 13, 18, 35, 72, 71, 20, 10, 32, 62, 8, 57, 10, 86, 61, 47, 72, 50, 40, 20, 56, 31, 25, 28, 2, 31, 22, 9, 8, 66, 72, 31, 22, 14, 24, 49, 33, 21, 36, 5, 68, 1, 36, 26, 73, 8, 24, 14, 22, 59, 66, 38, 35, 64, 30, 16, 45, 24, 3, 24, 30, 45, 8, 75, 42, 38, 3, 32, 33, 76, 82, 1, 7, 11, 10, 26, 90, 60, 50, 6, 49, 16, 13, 59, 23, 34, 31, 33, 1, 24, 9, 40, 28, 27, 52, 43, 31, 3, 6, 1, 6, 58, 9, 62, 40, 50, 51, 77, 21, 72, 75, 63, 10, 39, 26, 7, 0, 32, 3, 41, 26, 27, 26, 55, 6, 62, 9, 9, 18, 38, 52, 11, 25, 40, 34, 20, 58, 85, 41, 18, 42, 66, 45, 31, 17, 15, 38, 70, 22, 52, 18, 11, 18, 20, 49, 1, 10, 7, 68, 31, 30, 51, 19, 31, 23, 12, 51, 11, 55, 20, 41, 10, 38, 27, 54, 31, 58, 33, 17, 25, 11, 23, 55, 38, 15, 12, 31, 35, 67, 23, 36, 14, 10, 16, 5, 4, 26, 71, 56, 8, 20, 36, 26, 39, 66, 12, 26, 31, 32, 5, 68, 51, 19, 8, 19, 48, 6, 14, 2, 28, 72, 19, 29, 52, 10, 7, 30, 7, 41, 10, 5, 62, 50, 2, 36, 67, 13, 3, 52, 0, 41, 39, 35, 66, 22, 40, 53, 43, 38, 70, 2, 16, 2, 15, 12, 11, 17, 5, 18, 14, 11, 17, 61, 24, 50, 2, 11, 52, 11, 7, 21, 2, 15, 22, 25, 40, 3, 56, 27, 39, 19, 9, 29, 10, 29, 54, 56, 68, 0, 0, 14, 27, 63, 82, 8, 32, 59, 17, 8, 30, 29, 62, 30, 2, 15, 4, 16, 40, 10, 12, 8, 70, 49, 23, 83, 21, 21, 31, 45, 3, 56, 24, 13, 20, 60, 22, 8, 16, 24, 14, 3, 39, 9, 13, 16, 25, 35, 26, 17, 42, 22, 38, 19, 7, 9, 2, 1, 38, 24, 86, 32, 33, 62, 35, 17, 35, 59, 6, 5, 67, 8, 47, 2, 62, 60, 17, 2, 2, 50, 1, 46, 75, 67, 12, 6, 34, 6, 61, 12, 57, 40, 54, 40, 79, 26, 7, 59, 11, 26, 5, 58, 23, 33, 18, 46, 9, 13, 44, 23, 25, 10, 64, 23, 11, 39, 60, 7, 34, 2, 31, 30, 72, 67, 31, 64, 2, 13, 27, 32, 49, 28, 59, 47, 6, 58, 29, 24, 28, 45, 21, 17, 60, 59, 21, 55, 4, 50, 14, 25, 17, 22, 13, 25, 15, 79, 36, 54, 35, 32, 68, 50, 24, 7, 11, 0, 15, 31, 58, 82, 54, 57, 3, 64, 84, 5, 17, 57, 11, 5, 22, 29, 34, 27, 64, 44, 4, 65, 60, 23, 15, 23, 31, 34, 1, 35, 77, 64, 23, 4, 72, 27, 19, 33, 87, 27, 29, 22, 11, 50, 17, 46, 33, 42, 0, 31, 53, 39, 37, 8, 3, 31, 16, 64, 42, 26, 33, 40, 4, 23, 38, 10, 37, 27, 27, 10, 17, 47, 0, 41, 9, 22, 18, 1, 5, 6, 18, 3, 46, 63, 50, 42, 79, 1, 38, 13, 52, 7, 33, 23, 46, 18, 49, 32, 2, 19}
{73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 90, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 72, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 56, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 42, 13, 14, 15, 16, 17, 18, 19, 20, 30, 7, 8, 9, 10, 11, 12, 20, 3, 4, 5, 6, 12, 1, 2, 6, 89, 85, 86, 85, 48, 60, 58, 81, 65, 17, 7, 60, 41, 73, 90, 68, 61, 48, 45, 57, 18, 76, 73, 91, 63, 71, 64, 56, 87, 84, 58, 56, 87, 67, 75, 30, 77, 43, 81, 58, 72, 91, 18, 55, 71, 24, 38, 63, 47, 66, 54, 6, 70, 89, 54, 58, 83, 77, 85, 85, 48, 52, 78, 85, 56, 91, 64, 34, 72, 64, 71, 47, 46, 43, 63, 82, 90, 49, 37, 90, 53, 55, 89, 54, 86, 73, 77, 49, 88, 59, 16, 66, 81, 82, 63, 34, 71, 68, 75, 44, 13, 25, 66, 60, 57, 60, 91, 22, 12, 49, 42, 63, 58, 57, 55, 32, 72, 88, 91, 49, 72, 48, 71, 27, 55, 72, 38, 46, 31, 25, 83, 59, 77, 47, 59, 65, 50, 22, 57, 80, 79, 65, 61, 79, 91, 79, 87, 70, 9, 77, 70, 56, 77, 89, 64, 83, 69, 85, 12, 87, 63, 75, 17, 62, 74, 23, 70, 76, 86, 90, 30, 14, 85, 91, 68, 87, 81, 60, 31, 50, 70, 83, 27, 23, 60, 26, 58, 63, 62, 88, 53, 56, 90, 49, 31, 79, 32, 17, 28, 26, 83, 40, 79, 63, 2, 56, 72, 39, 68, 74, 59, 62, 83, 73, 70, 61, 76, 87, 17, 38, 85, 20, 7, 91, 59, 60, 80, 44, 12, 54, 76, 91, 74, 51, 90, 85, 87, 64, 55, 80, 38, 87, 36, 86, 47, 90, 69, 32, 71, 43, 55, 87, 67, 77, 36, 75, 79, 59, 26, 40, 90, 52, 84, 71, 61, 36, 75, 34, 85, 75, 45, 81, 55, 78, 17, 78, 84, 80, 63, 83, 73, 18, 45, 85, 74, 78, 55, 51, 53, 10, 21, 64, 77, 54, 58, 43, 76, 65, 48, 82, 91, 46, 9, 69, 40, 37, 87, 70, 76, 49, 67, 55, 34, 72, 62, 73, 77, 38, 79, 17, 48, 50, 88, 9, 55, 77, 57, 29, 59, 62, 65, 55, 80, 89, 60, 90, 83, 55, 78, 80, 20, 38, 74, 60, 81, 54, 91, 37, 83, 70, 87, 88, 37, 75, 75, 65, 45, 90, 33, 88, 71, 77, 75, 70, 89, 65, 86, 87, 80, 52, 76, 61, 27, 19, 76, 70, 85, 59, 61, 23, 66, 61, 90, 45, 39, 69, 81, 41, 86, 78, 85, 58, 54, 87, 48, 65, 79, 68, 72, 73, 70, 29, 60, 82, 69, 69, 35, 66, 72, 91, 87, 52, 7, 69, 62, 86, 88, 76, 80, 32, 41, 59, 91, 82, 76, 79, 51, 58, 91, 74, 49, 52, 52, 69, 67, 90, 66, 60, 86, 60, 78, 74, 89, 81, 67, 21, 55, 91, 89, 74, 41, 55, 88, 84, 31, 75, 83, 86, 65, 86, 86, 83, 28, 89, 66, 60, 29, 82, 65, 74, 40, 75, 51, 73, 72, 70, 86, 13, 85, 78, 58, 43, 85, 90, 70, 25, 48, 82, 76, 76, 36, 43, 70, 79, 49, 58, 79, 50, 79, 82, 82, 43, 40, 64, 78, 48, 86, 62, 74, 72, 50, 88, 80, 57, 88, 59, 87, 75, 50, 56, 65, 36, 74, 72, 42, 83, 31, 64, 80, 55, 72, 18, 63, 90, 88, 50, 63, 86, 40, 78, 27, 12, 51, 86, 77, 41, 72, 40, 31, 70, 67, 29, 36, 41, 59, 42, 76, 69, 64, 71, 78, 82, 53, 34, 46, 48, 73, 50, 42, 75, 48, 90, 51, 12, 53, 23, 44, 74, 88, 47, 85, 71, 56, 81, 69, 15, 90, 91, 88, 89, 68, 73, 58, 74, 61, 83, 49, 22, 17, 85, 16, 21, 78, 41, 26, 33, 30, 43, 85, 41, 75, 49, 70, 79, 37, 65, 78, 3, 37, 47, 44, 56, 87, 71, 52, 64, 63, 15, 42, 27, 55, 89, 57, 74, 87, 15, 27, 62, 82, 90, 85, 55, 81, 26, 57, 44, 53, 65, 44, 13, 69, 49, 89, 66, 49, 58, 29, 88, 81, 85, 85, 70, 34, 89, 65, 49, 59, 36, 48, 82, 72, 62, 63, 56, 44, 62, 21, 45, 37, 69, 23, 40, 37, 89, 26, 51, 90, 50, 61, 13, 62, 83, 49, 83, 37, 87, 56, 63, 90, 91, 42, 67, 87, 25, 38, 78, 40, 70, 8, 76, 81, 31, 91, 46, 68, 47, 71, 89, 80, 63, 81, 56, 77, 86, 60, 79, 65, 69, 88, 81, 41, 51, 79, 76, 85, 42, 67, 34, 87, 42, 52, 64, 66, 90, 53, 71, 34, 72, 58, 82, 79, 74, 86, 51, 65, 58, 40, 79, 88, 90, 91, 56, 74, 32, 81, 78, 77, 89, 90, 8, 74, 57, 85, 33, 48, 71, 21, 78, 60, 50, 64, 42, 87, 22, 91, 21, 77, 37, 58, 87, 81, 59, 62, 45, 42, 82, 87, 79, 85, 53, 65, 19, 86, 73, 85, 91, 60, 54, 85, 87, 64, 29, 76, 37, 17, 24, 36, 84, 50, 86, 48, 25, 75, 71, 62, 77, 52, 57, 49, 68, 75, 86, 91, 35, 20, 85, 41, 51, 41, 91, 42, 59, 62, 28, 54, 56, 76, 74, 72, 11, 59, 78, 79, 53, 89, 13, 49, 68, 85, 50, 61, 50, 54, 77, 79, 90, 75, 40, 74, 81, 45, 71, 86, 46, 53, 76, 77, 40, 51, 26, 67, 80, 58, 47, 68, 53, 80, 81, 76, 49, 85, 78, 8, 83, 41, 56, 38, 73, 62, 20, 38}
Returns: {0, 1, 1, 81, 2, 81, 1, 27, 4, 81, 5, 81, 2, 27, 5, 81, 7, 81, 8, 81, 1, 9, 10, 81, 4, 27, 11, 81, 4, 27, 13, 81, 14, 81, 5, 27, 16, 81, 17, 81, 2, 9, 16, 81, 17, 81, 2, 9, 19, 81, 20, 81, 7, 27, 22, 81, 23, 81, 8, 27, 26, 81, 25, 81, 26, 81, 1, 3, 28, 81, 29, 81, 10, 27, 31, 81, 32, 81, 11, 27, 137, 324, 71, 162, 49, 108, 61, 162, 34, 81, 35, 81, 4, 9, 37, 81, 38, 81, 13, 27, 40, 81, 41, 81, 14, 27, 43, 81, 44, 81, 5, 9, 46, 81, 47, 81, 16, 27, 49, 81, 50, 81, 17, 27, 52, 81, 53, 81, 2, 3, 55, 81, 56, 81, 19, 27, 58, 81, 59, 81, 20, 27, 61, 81, 62, 81, 7, 9, 64, 81, 65, 81, 22, 27, 67, 81, 68, 81, 23, 27, 70, 81, 71, 81, 8, 9, 73, 81, 74, 81, 25, 27, 76, 81, 77, 81, 26, 27, 79, 81, 80, 81, 1, 1 }

92
{0, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 0, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 0, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 0, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 0, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0, 13, 14, 15, 16, 17, 18, 19, 20, 0, 7, 8, 9, 10, 11, 12, 0, 3, 4, 5, 6, 0, 1, 2}
{73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 90, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 72, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 56, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 42, 13, 14, 15, 16, 17, 18, 19, 20, 30, 7, 8, 9, 10, 11, 12, 20, 3, 4, 5, 6, 12, 1, 2, 6}
Returns: {0, 1, 32768, 230945, 65536, 230945, 24576, 230945, 49152, 230945, 73728, 230945, 98304, 230945, 4096, 46189, 8192, 46189, 12288, 46189, 16384, 46189, 20480, 46189, 24576, 46189, 3584, 46189, 7168, 46189, 10752, 46189, 14336, 46189, 17920, 46189, 21504, 46189, 25088, 46189, 28672, 46189, 16128, 230945, 32256, 230945, 48384, 230945, 64512, 230945, 16128, 46189, 96768, 230945, 112896, 230945, 129024, 230945, 145152, 230945, 32256, 46189, 1344, 20995, 2688, 20995, 4032, 20995, 5376, 20995, 1344, 4199, 8064, 20995, 9408, 20995, 10752, 20995, 12096, 20995, 2688, 4199, 14784, 20995, 16128, 20995, 96, 1615, 192, 1615, 288, 1615, 384, 1615, 96, 323, 576, 1615, 672, 1615, 768, 1615, 864, 1615, 192, 323, 1056, 1615, 1152, 1615, 1248, 1615, 1344, 1615, 18, 323, 36, 323, 54, 323, 72, 323, 90, 323, 108, 323, 126, 323, 144, 323, 162, 323, 180, 323, 198, 323, 216, 323, 234, 323, 252, 323, 270, 323, 288, 323, 1, 19, 2, 19, 3, 19, 4, 19, 5, 19, 6, 19, 7, 19, 8, 19, 9, 19, 10, 19, 11, 19, 12, 19, 13, 19, 14, 19, 15, 19, 16, 19, 17, 19, 18, 19, 1, 1 }

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

Coding Area

Language: C++17 · define a public class FillInTheDAG with a public method vector<long long> findWay(int n, vector<int> f, vector<int> t) · 36 test cases · 2 s / 256 MB per case