JumpDistancesOnTree
SRM 716 · 2017-05-20 · by cgy4ever
SRM 716 · 2017-05-20 · by cgy4ever · Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
Treeland is a country with n cities, numbered 0 through n-1.
Obviously, the topology of Treeland is a tree: there are exactly n-1 bidirectional roads, each connecting two cities in such a way that it is possible to travel from any city to any other city.
You are given the description of the road network: the int[] p with n-1 elements.
For each valid index i, there is a road that connects the cities i+1 and p[i].
The distance between two cities is the smallest number of roads you need to use in order to travel from one city to the other.
Rabbit Hanako had a trip in Treeland. She started her trip on day 0 in the city x[0] = 0. On each of the following m days she chose a city x[i] (possibly the same as her current city) and traveled there by using the only direct route. Each day she wrote down the distance she traveled - i.e., on day i she wrote down the distance d[i] between the cities x[i-1] and x[i]. After the trip was over, she constructed a set D that contained all values d[i] she wrote down.
For example, if d[1], d[2], ..., d[m] are {1, 0, 0, 1, 3, 5, 0} then the set D will be {0, 1, 3, 5}.
You know that Hanako's trip had the form described above, but you don't know the value m and the values x[i]. You are given aint[] S.
Check whether it is possible that S = D.
In other words, check whether there are values m and x[1] ... x[m] such that the set of distances D will contain exactly the same elements as the given int[] S.
Return "Possible" if such a trip exists and "Impossible" if it does not.
Rabbit Hanako had a trip in Treeland. She started her trip on day 0 in the city x[0] = 0. On each of the following m days she chose a city x[i] (possibly the same as her current city) and traveled there by using the only direct route. Each day she wrote down the distance she traveled - i.e., on day i she wrote down the distance d[i] between the cities x[i-1] and x[i]. After the trip was over, she constructed a set D that contained all values d[i] she wrote down.
For example, if d[1], d[2], ..., d[m] are {1, 0, 0, 1, 3, 5, 0} then the set D will be {0, 1, 3, 5}.
You know that Hanako's trip had the form described above, but you don't know the value m and the values x[i]. You are given a
Return "Possible" if such a trip exists and "Impossible" if it does not.
Constraints
- p will contain between 1 and 2,000 elements, inclusive.
- For each i, 0 <= p[i] <= i.
- S will contain between 1 and 2,000 elements, inclusive.
- Each element in S will be between 0 and |p|, inclusive.
- For each i, S[i] < S[i+1].
Examples
0)
{0,1,1,0,4,4}
{2,4}
Returns: "Possible"
The tree looks as follows: 0 / \ 1 4 / \ / \ 2 3 5 6 One valid trip has m = 4 and x = {0, 2, 3, 6, 5}. For this trip the distances traveled are {2, 2, 4, 2}, and thus the set of all distances D is exactly {2, 4}, as required.
1)
{0,1,1,0,4,4}
{1,2,3,4,5}
Returns: "Impossible"
The maximal possible distance between any two cities is 4, so you will never have 5 in D.
2)
{0,1,1,0,4,4}
{3,4}
Returns: "Impossible"
3)
{0,1,2,3,4,0,6,7,8,9}
{2,4,6,8,10}
Returns: "Impossible"
4)
{0}
{1}
Returns: "Possible"
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class JumpDistancesOnTree with a public method string isPossible(vector<int> p, vector<int> S) · 122 test cases · 2 s / 256 MB per case