Connection Status:
Competition Arena > UnknownTree

UnknownTree

SRM 565 · 2012-06-05 · by lyrically

SRM 565 · 2012-06-05 · by lyrically · Graph Theory
Class Name: UnknownTree
Return Type: int
Method Name: getCount
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given three int[]s: distancesA, distancesB, and distancesC. Each of these int[]s has exactly N elements.

We are interested in trees that satisfy the following conditions:
  • The tree has exactly N + 3 vertices.
  • Each vertex has a different label. The set of all labels is { A, B, C, 0, 1, ..., N-1 }.
  • Each edge of the tree has a positive integer length.
  • For each i (0 <= i < N), the distance between the vertex A and the vertex i is distancesA[i].
  • For each i (0 <= i < N), the distance between the vertex B and the vertex i is distancesB[i].
  • For each i (0 <= i < N), the distance between the vertex C and the vertex i is distancesC[i].

Find the number of trees that satisfy all of the conditions above, and return the number modulo 1,000,000,009.

Notes

  • The distance between two vertices s and t is defined as the sum of lengths of all edges on the only simple path between s and t.
  • Two trees T1 and T2 are different when T1 has an edge u-v such that in T2 the edge u-v is either not present at all, or it has a different length than the edge u-v in T1.

Constraints

  • distancesA, distancesB, and distancesC will contain the same number of elements.
  • distancesA, distancesB, and distancesC will contain between 1 and 50 elements, inclusive.
  • Each element of distancesA, distancesB, and distancesC will be between 1 and 100,000,000, inclusive.
Examples
0)
{1}
{2}
{3}
Returns: 6
1)
{1, 2}
{1, 2}
{1, 2}
Returns: 1
2)
{10, 11, 10, 5, 12, 10, 9, 9, 8, 6, 9, 12, 11, 8, 9, 9, 10, 4, 7, 12, 10, 13, 10, 3, 7, 12, 7, 11, 7, 7, 10, 8, 8, 6, 6, 10, 9, 8, 7, 9, 10, 9, 9, 7, 8, 9, 9, 9, 11, 7}
{8, 9, 8, 3, 10, 8, 7, 7, 6, 4, 7, 10, 9, 6, 7, 7, 8, 2, 5, 10, 8, 11, 8, 1, 5, 10, 5, 9, 5, 5, 8, 6, 6, 4, 4, 8, 7, 6, 5, 7, 8, 7, 7, 5, 6, 7, 7, 7, 9, 5}
{8, 5, 6, 3, 10, 8, 7, 1, 6, 4, 3, 4, 3, 4, 1, 1, 6, 8, 5, 4, 4, 5, 8, 5, 5, 10, 5, 5, 5, 5, 2, 2, 4, 2, 4, 8, 7, 6, 3, 7, 4, 5, 7, 5, 4, 5, 7, 7, 3, 1}
Returns: 966172686
3)
{5, 9, 4, 6, 6, 7, 5, 6, 3, 9, 3, 6, 5, 6, 5, 8, 8, 5, 6, 6, 5, 4, 6, 5, 5, 7, 7, 4, 6, 4, 4, 1, 7, 4, 6, 5, 7, 5, 4, 6, 7, 6, 3, 5, 6, 6, 2, 6, 7, 5}
{9, 5, 8, 10, 10, 7, 9, 10, 7, 9, 5, 10, 5, 6, 9, 4, 8, 9, 10, 6, 9, 4, 10, 9, 5, 11, 7, 8, 10, 8, 8, 9, 11, 8, 10, 9, 11, 5, 6, 10, 7, 10, 7, 9, 2, 6, 6, 10, 11, 9}
{7, 11, 6, 8, 8, 9, 3, 8, 5, 11, 5, 4, 7, 8, 7, 10, 10, 7, 8, 8, 3, 6, 8, 7, 7, 9, 9, 6, 4, 6, 6, 7, 5, 2, 8, 7, 9, 7, 6, 8, 9, 4, 5, 3, 8, 8, 4, 8, 9, 7}
Returns: 989568540
4)
{3, 5, 10, 9, 8, 13, 9, 7, 9, 8, 10, 11, 5, 7, 7, 7, 11, 11, 5, 6, 5, 6, 10, 1, 8, 3, 9, 9, 10, 14, 5, 7, 10, 8, 6, 9, 4, 9, 13, 11, 13, 7, 7, 2, 6, 9, 9, 12, 2, 8}
{7, 7, 4, 11, 10, 7, 3, 9, 11, 10, 12, 3, 7, 7, 9, 1, 3, 13, 9, 6, 3, 8, 2, 7, 10, 5, 11, 3, 12, 8, 7, 9, 12, 2, 8, 1, 4, 1, 15, 5, 15, 7, 9, 8, 8, 3, 3, 14, 6, 10}
{9, 9, 6, 13, 12, 9, 5, 11, 13, 12, 14, 5, 9, 9, 11, 3, 5, 15, 11, 8, 5, 10, 4, 9, 12, 7, 13, 5, 14, 10, 9, 11, 14, 4, 10, 3, 6, 3, 17, 7, 17, 9, 11, 10, 10, 5, 5, 16, 8, 12}
Returns: 678286243

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

Coding Area

Language: C++17 · define a public class UnknownTree with a public method int getCount(vector<int> distancesA, vector<int> distancesB, vector<int> distancesC) · 156 test cases · 2 s / 256 MB per case

Submitting as anonymous