Connection Status:
Competition Arena > TreeMoving

TreeMoving

SRM 711 · 2017-02-20 · by Arterm

SRM 711 · 2017-02-20 · by Arterm · Dynamic Programming, Graph Theory
Class Name: TreeMoving
Return Type: int
Method Name: count
Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given m trees. The trees are labeled T(0) through T(m-1). Each tree contains n vertices labeled 0 through n-1. A cyclic rotation of edges is the following procedure:
  1. In each tree you choose one of its edges. Let e(i) be the edge chosen in the tree T(i).
  2. You remove the chosen edge from the tree, producing a graph with n vertices and only n-2 edges.
  3. For each valid i, you add the edge e(i) to the tree T(i+1). Also, you add the edge e(m-1) to the tree T(0). For example, if e(0) was an edge that connected vertices 4 and 7 in T(0), the graph T(1) will now get a new edge that connects its vertices 4 and 7.
  4. The procedure was successful if and only if each T(i) is a tree again.
Count all possible ways in which we can successfully perform a cyclic rotation of edges. Return that count modulo (10^9 + 7). You are given the int n. You are also given the int[]s roots, a, b, and c, each with m elements. These are inputs to a pseudorandom generator that will produce the trees. In order to generate the tree T(i), we will first generate a temporary sequence X: 
X[0] = c[i]
for k = 1 to n-2:
    X[k] = (a[i] * X[k - 1] + b[i]) modulo 1,000,000,007
and then we use that sequence to generate the edges of the tree: 
for j = 0 to n-2:
    u[j] = (roots[i] + j + 1) modulo n
    v[j] = (roots[i] + (X[j] modulo (j + 1))) modulo n
    add the edge between u[j] and v[j] to the tree T(i)

Notes

  • The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of the allowed size within the given limits.

Constraints

  • n will be between 2 and 300, inclusive.
  • roots will contain between 2 and 300 elements, inclusive.
  • a and roots will contain the same number of elements.
  • b and roots will contain the same number of elements.
  • c and roots will contain the same number of elements.
  • Each element of roots will be between 0 and n - 1, inclusive.
  • Each element of a will be between 1 and 1,000,000,006, inclusive.
  • Each element of b will be between 0 and 1,000,000,006, inclusive.
  • Each element of c will be between 0 and 1,000,000,006, inclusive.
Examples
0)
3
{0, 2}
{1, 2}
{1, 0}
{2, 3}
Returns: 2

There are two trees, each of them contains 3 vertices. The tree T(0) is generated as follows: X[0] = c[0] = 2 X[1] = (a[0] * X[0] + b[0]) modulo 1,000,000,007 = 3 u[0] = (roots[0] + 1) modulo n = 1 v[0] = (roots[0] + (X[0] modulo 1)) modulo n = 0 u[1] = (roots[0] + 2) modulo n = 2 v[1] = (roots[0] + (X[1] modulo 2)) modulo n = 1 Hence, the tree T(0) contains the edges 1-0 and 2-1. The tree T(1) contains the edges 0-2 and 1-2. There are two ways to do a successful cyclic rotation of edges: we can either choose the edge 1-2 in each tree, or we can choose the edge 0-1 in T(0) and the edge 0-2 in T(1).

1)
3
{0, 0, 1}
{6, 1, 3}
{6, 5, 5}
{2, 5, 9}
Returns: 2

T(0) contains edges 1-0 and 2-0. T(1) contains edges 1-0 and 2-0. T(2) contains edges 2-1 and 0-1.

2)
5
{0, 1, 1, 1, 2}
{7, 4, 7, 9, 2}
{8, 3, 9, 5, 3}
{6, 0, 1, 5, 9}
Returns: 22
3)
3
{0, 0, 1}
{373206610, 937739946, 172315864}
{870770575, 635025870, 765158489}
{915938656, 747443899, 387215442}
Returns: 2

Watch out for integer overflow when generating the temporary sequence X.

4)
10
{0, 1, 0, 4, 0, 2, 1, 8, 5, 5}
{508821715, 481198414, 163209181, 56649169, 276327522, 13486359, 845629232, 482370937, 373100199, 297431939}
{256979012, 884002808, 393825387, 609998779, 816536931, 123064634, 673095376, 18224901, 510687925, 466437174}
{368733721, 596826005, 853637399, 436680590, 369153650, 853574577, 609377415, 903050702, 259325966, 105275092}
Returns: 17765

Watch out for integer overflow when calculating the answer.

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

Coding Area

Language: C++17 · define a public class TreeMoving with a public method int count(int n, vector<int> roots, vector<int> a, vector<int> b, vector<int> c) · 26 test cases · 2 s / 256 MB per case

Submitting as anonymous