TopCoder SRM 598 - 950: TPS

Problem Statement

Treeland有n个城市,标号从0...n-1。有n-1条双向道路连接了n个城市构成一颗树。
Treeland的居民想要建造一套 TPS系统(Treeland Positioning System)。
TPS是一个能帮助人定位他在哪个城市的系统。
系统由k个信标构成，每个信标被安放在一个城市。
当一个人打开他的TPS接收器的时候他能得到他与每一个信标的距离
(这里距离指树上两点之间经过的边的数量) 。
显然只有当在不同的城市打开TPS接收器接受到的信息不一样的时候TPS系统才能正常工作。
（也就不存在两个不同的城市使得在他们那里接收到的信号相同）
**注意不同的信标之间是可以区分的**。
求最少安放多少信标才能使TPS系统正常工作。

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.

Test cases

input
- linked {"NYNN",
  "YNYN",
  "NYNY",
  "NNYN"}
output
Returns 1

note

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.
input
- linked {"NYYY",
  "YNNN",
  "YNNN",
  "YNNN"}
output
Returns 2
note
There are also 4 cities. The road network looks as follows:
```
1 - 0 - 2
    |
    3
```
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.
input
- linked {"NNYNNNNNNN",
  "NNNNNYNNNN",
  "YNNYNNYNNN",
  "NNYNYNNYNN",
  "NNNYNYNNYN",
  "NYNNYNNNNY",
  "NNYNNNNNNN",
  "NNNYNNNNNN",
  "NNNNYNNNNN",
  "NNNNNYNNNN"}
output
Returns 2
note
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.
input
- linked {"NYNYNNYNN",
  "YNYNYNNYN",
  "NYNNNYNNY",
  "YNNNNNNNN",
  "NYNNNNNNN",
  "NNYNNNNNN",
  "YNNNNNNNN",
  "NYNNNNNNN",
  "NNYNNNNNN"}
output
Returns 3
note
The graph looks as follows:
```
3   4   5
|   |   |
0 - 1 - 2
|   |   |
6   7   8
```
input
- linked {"NYYYYYYYYY",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN",
  "YNNNNNNNNN"}
output
Returns 8
input
- linked { "N" }
output
Returns 0

note

We don't need any beacon at all, since there is only 1 city.

back to the menu

SRM 598 1 950 TPS

Problem Statement

Definition

Limits

Constraints

Test cases