Get Time

   Problem Statement  

 Problem Statement for TPS

Problem Statement

    Treeland has N cities, numbered 0 through N-1. There are N-1 undirected roads, each connecting a pair of cities. The roads form a tree. (I.e., each pair of cities is connected via some sequence of roads.)

You are given a String linked with N elements, each consisting of N characters. There is a road between city i and city j if and only if linked[i][j] is 'Y'. In all other cases linked[i][j] is 'N'.

The inhabitants of Treeland want to create the Treeland Positioning System (TPS). TPS will be a system that will help people determine which city they are in. The system will consist of K labeled beacons. Each beacon will be located in one of the cities. When a person turns on their TPS receiver, it will determine its distance to each of the beacons. (The distance is measured as the number of roads the person would have to use in order to reach the beacon.)

Obviously, TPS will only be usable if different cities correspond to different readings on the receiver. In other words, the number K and the placement of beacons must be such that there are no two cities where the receiver will report the same sequence of values. (Note that the beacons can be distinguished. See Example 1.)

Return the minimal possible value of K.


Method signature:int minimalBeacons(String[] linked)
(be sure your method is public)


-N will be between 1 and 50, inclusive.
-linked will contain N elements.
-Each element of linked will contain N characters.
-Each character of each element of linked will be either 'Y' or 'N'.
-For each i and j, if linked[i][j] is 'Y' then linked[j][i] is 'Y'.
-For each i, linked[i][i] will be 'N'.
-The graph described by linked will be a tree with N nodes.


Returns: 1
There are 4 cities and 3 roads: 0-1-2-3. One possible solution is to put a beacon in city 0. Then city i will have distance i from that beacon, and they are distinguishable.
Returns: 2
There are also 4 cities. The road network looks as follows:
1 - 0 - 2
1 beacon is not enough, for example:
  • If it is located in city 0, then cities 1,2 and 3 all have distance 1 from that beacon, they are not distinguishable.
  • If it is located in city 1, then cities 2, 3 all have distance 2 from that beacon, they are not distinguishable.
2 beacons are enough. For example, we can place them into cities 1 and 2. Then:
  • If we are in city 0 the receiver will show the distances 1, 1.
  • If we are in city 1 the receiver will show the distances 0, 2.
  • If we are in city 2 the receiver will show the distances 2, 0.
  • If we are in city 3 the receiver will show the distances 2, 2.
In each city the receiver shows a different sequence of distances.
Returns: 2
The graph looks as follows:
0           1
|           |
2 - 3 - 4 - 5
|   |   |   |
6   7   8   9
One optimal solution is to put beacons into cities 0 and 1.
Returns: 3
The graph looks as follows:
3   4   5
|   |   |
0 - 1 - 2
|   |   |
6   7   8
Returns: 8
Returns: 0
We don't need any beacon at all, since there is only 1 city.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 598 Round 1 - Division I, Level Three