Connection Status:
Competition Arena > SplittingFoxes3

SplittingFoxes3

2016 TCO Regional Wildcard · 2016-03-24 · by cgy4ever

2016 TCO Regional Wildcard · 2016-03-24 · by cgy4ever · Advanced Math, Graph Theory
Class Name: SplittingFoxes3
Return Type: int[]
Method Name: restore
Arg Types: (int, int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel is visiting the country Ecittalimes. This country contains n cities, numbered 0 through n-1. There are some railroads in the country. For each valid i, there is a one-directional railroad from city a[i] to city b[i].

Let S be a set of cities in Ecittalimes, and let M be a city in Ecittalimes. (M may or may not belong to S.) We say that city M is a possible meeting place for the set S if the following constraint is satisfied:
  • For each city X in S it is possible to travel by train (directly or indirectly) from X to M.

Let S be a set of cities in Ecittalimes, and let M be a city in Ecittalimes. (Again, M may or may not belong to S.) We say that city M is an optimal meeting place for the set S if the following constraints are satisfied:
  • M is a possible meeting place.
  • If another city M' is also a possible meeting place then it is possible to travel by train (directly or indirectly) from M to M'.

The system of railroads in Ecittalimes has a special property: Any non-empty set S of cities has exactly one optimal meeting place, denoted meet(S).

For each i, city i contains exactly num[i] attractions. Let T = sum(num) be the total number of attractions in the country.

In the morning, Fox Ciel always splits into k distinct foxes, numbered 0 through k-1. Each fox is teleported to one of the T attractions. (It is possible that multiple foxes are teleported to the same attraction.) Each fox will spend the day at its attraction. In the evening all foxes want to meet and merge into Fox Ciel again. In order to do that, they all travel by trains to the same city meet(S). Here, S is the set of cities that contained at least one fox during the day.

There are exactly T^k possibilites for Fox Ciel's day. For each of them, Ciel computed in which city the k foxes would meet. For each i, city i was the meetingplace exactly X[i] times. (The sum of all X[i] is exactly T^k.)

You are given the ints n and k: the number of cities and the number of foxes Ciel splits into. You are also given the int[]s a and b: the starts and ends of all railroad segments. Finally, you are given a int[] x. For each i, x[i] is equal to (X[i] modulo 1,000,000,007).

Your task is to use the above information to recover the unknown values num[i]: that is, the number of attractions in each city. If there is no solution consistent with the given values, return an empty int[]. Otherwise return any valid int[] num. Note that each value in num must be between 0 and 1,000,000,006, inclusive.

Constraints

  • n will be between 1 and 300, inclusive.
  • k will be between 1 and 1,000,000,000, inclusive.
  • a will contain between 0 and 1,000 elements, inclusive.
  • a and b will contain the same number of elements.
  • Each element in a and b will be between 0 and (n-1), inclusive.
  • For each i, a[i] != b[i].
  • The graph will satisfy the conditions described in problem statement.
  • x will contain exactly n elements.
  • Each element in x will be between 0 and 1,000,000,006, inclusive.
Examples
0)
3
2
{0,2}
{1,1}
{1,2,1}
Returns: {1, 0, 1 }

There are three cities and two railroads: 0 --> 1 and 2 --> 1. Fox Ciel splits into two foxes. One solution is that we have num = {1,0,1}. In other words, we claim that there is 1 attraction (called attraction alpha) in city 0, 0 attractions in city 1, and 1 attraction (called attraction beta) in city 2. There are 2^2 = 4 possibilities for Fox Ciel's day: If both foxes are at attraction alpha. they'll meet in city 0. If fox 0 is at attraction alpha and fox 1 at attraction beta, they'll meet in city 1. If fox 0 is at attraction beta and fox 1 at attraction alpha, they'll also meet in city 1. If both foxes are at attraction beta. they'll meet in city 2. Hence, our proposed solution gives X = {1,2,1}, which is precisely the given value of x.

1)
4
3
{1,1,0,3}
{0,3,2,2}
{7,1,49,7}
Returns: {1, 1, 1, 1 }

This time the graph looks like this (all edges are from top to bottom): 1 / \ 0 3 \ / 2

2)
1
2
{}
{}
{5}
Returns: { }

Suppose we have x attractions in node 0, then we have: x^2 = 5 mod 10^9+7. But there is no solution, so we should return {}.

3)
1
2
{}
{}
{4}
Returns: {1000000005 }

There are multiple valid solutions. For example, {2} is also a valid solution. You may return any valid solution.

4)
8
2
{0,2,2,4,4,6,1,3,5}
{1,1,3,3,5,5,7,7,7}
{1,4,4,12,9,24,16,30}
Returns: {1, 0, 2, 0, 3, 0, 4, 0 }

The graph looks like this (all edges are from top to bottom): 0 2 4 6 \ / \ / \ / 1 3 5 \ | / \ | / \|/ 7

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

Coding Area

Language: C++17 · define a public class SplittingFoxes3 with a public method vector<int> restore(int n, int k, vector<int> a, vector<int> b, vector<int> x) · 88 test cases · 2 s / 256 MB per case

Submitting as anonymous