JumpDistancesOnTreeEasy
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 50 elements, inclusive.
- For each i, 0 <= p[i] <= i.
- S will contain between 1 and 50 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 is like: 0 / \ 1 4 / \ / \ 2 3 5 6 One of the possible route is: 0, 2, 3, 6, 5. The distance for each day is {2, 2, 4, 2} so S = {2, 4}.
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 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class JumpDistancesOnTreeEasy with a public method string isPossible(vector<int> p, vector<int> S) · 123 test cases · 2 s / 256 MB per case