Connection Status:
Competition Arena > TPS

TPS

SRM 598 · 2013-06-25 · by cgy4ever

SRM 598 · 2013-06-25 · by cgy4ever · Dynamic Programming
Class Name: TPS
Return Type: int
Method Name: minimalBeacons
Arg Types: (vector<string>)
Problem Statement

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.

Constraints

  • 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.
Examples
0)
{"NYNN",
 "YNYN",
 "NYNY",
 "NNYN"}
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.

1)
{"NYYY",
 "YNNN",
 "YNNN",
 "YNNN"}
Returns: 2

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.

2)
{"NNYNNNNNNN",
 "NNNNNYNNNN",
 "YNNYNNYNNN",
 "NNYNYNNYNN",
 "NNNYNYNNYN",
 "NYNNYNNNNY",
 "NNYNNNNNNN",
 "NNNYNNNNNN",
 "NNNNYNNNNN",
 "NNNNNYNNNN"}
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.

3)
{"NYNYNNYNN",
 "YNYNYNNYN",
 "NYNNNYNNY",
 "YNNNNNNNN",
 "NYNNNNNNN",
 "NNYNNNNNN",
 "YNNNNNNNN",
 "NYNNNNNNN",
 "NNYNNNNNN"}
Returns: 3

The graph looks as follows: 3 4 5 | | | 0 - 1 - 2 | | | 6 7 8

4)
{"NYYYYYYYYY",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN",
 "YNNNNNNNNN"}
Returns: 8
5)
{"N"}
Returns: 0

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

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

Coding Area

Language: C++17 · define a public class TPS with a public method int minimalBeacons(vector<string> linked) · 112 test cases · 2 s / 256 MB per case

Submitting as anonymous