Connection Status:
Competition Arena > FoxConnection

FoxConnection

SRM 604 · 2013-12-22 · by cgy4ever

SRM 604 · 2013-12-22 · by cgy4ever · Dynamic Programming
Class Name: FoxConnection
Return Type: int
Method Name: minimalDistance
Arg Types: (vector<int>, vector<int>, string)
Problem Statement

Problem Statement

There are N cities in Treeland. The cities are numbered 1 through N. The roads in Treeland have the topology of a tree. That is, there are exactly N-1 bidirectional roads in Treeland, each connecting a pair of cities, and it is possible to travel between any two cities along the roads. For the purpose of this problem, all roads have the same length, and this length is our unit of distance.

You are given two int[]s A and B that describe the tree. Each of these int[]s has N-1 elements. For each valid i, there is a road that connects the cities A[i] and B[i].

There are some foxes in Treeland. Currently, each of the foxes lives in a different city. You are given a String haveFox with N characters. For each i, character i of haveFox is 'Y' if there is a fox in city i+1, or 'N' otherwise.

The foxes would like to live closer to each other. To achieve that, some foxes (possibly all of them or none at all) will move to different cities. There are three constraints for the move:
  1. After the foxes move, there must again be at most one fox in each city. (There are no restrictions on how the foxes travel while they are moving.)
  2. After the foxes move, the set of cities inhabited by the foxes must be connected. That is, for any two different cities i and j that both contain a fox, all the cities on the (only) path between i and j must also contain a fox.
  3. The total distance traveled by the foxes during the move must be as small as possible.


Return the smallest possible sum of distances traveled by the foxes.

Constraints

  • N will be between 2 and 50, inclusive.
  • A will contain exactly N-1 elements.
  • Each element of A will be between 1 and N, inclusive.
  • B will contain exactly N-1 elements.
  • Each element of B will be between 1 and N, inclusive.
  • The graph described by A and B will be a tree.
  • haveFox will contain exactly N characters.
  • Each character in haveFox will be either 'Y' or 'N'.
Examples
0)
{1,2,3}
{2,3,4}
"YNNY"
Returns: 2

Treeland looks as follows: 1-2-3-4. Two foxes are located in city 1 and city 4. One optimal solution is: The fox located in city 1 moves to city 2. The fox located in city 4 moves to city 3.

1)
{1,1,1,1}
{2,3,4,5}
"NYYYY"
Returns: 1

We can move any one of the foxes to city 1. After that the cities with foxes will form a connected set.

2)
{1,3,4,5,4}
{2,2,2,4,6}
"YNYNYY"
Returns: 2
3)
{1,2,3,4,5,6,7,8,9}
{2,3,4,5,6,7,8,9,10}
"YNNNYNYNNY"
Returns: 7
4)
{1,2,3,4,3,6,8,7}
{2,3,4,5,6,8,9,6}
"YNNYYNYYY"
Returns: 3
5)
{1}
{2}
"NY"
Returns: 0

There can be only 1 fox.

6)
{1}
{2}
"NN"
Returns: 0

And there can be no foxes.

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

Coding Area

Language: C++17 · define a public class FoxConnection with a public method int minimalDistance(vector<int> A, vector<int> B, string haveFox) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous