WSNParentsAssignment

SRM 367 · 2007-09-26 · by gevak

SRM 367 · 2007-09-26 · by gevak · Graph Theory

Show categories

Class Name: WSNParentsAssignment

Return Type: int[]

Method Name: minNetworkBurdenLevel

Arg Types: (vector<string>, string)

Problem Statement

A wireless sensor network consists of several independent measuring devices and one control center. Each device must be able to send its sensor readings to the control center, but due to limitations in range, not all of the devices can communicate directly with the control center. To solve this problem, each device is assigned a single parent to which it is capable of directly transmitting data. A parent can be either another device or the control center. Each device receives readings from all its children (if it has any), adds its own readings, and passes everything to its parent. All the readings must eventually reach the control center. The number of children a device has is called the device's burden level. The burden level of the entire network is the maximum burden level among all its devices. Note that the control center is not a device.

You are given a String[] network, where the j-th character of the i-th element is equal to 'Y' if the i-th device can directly transmit data to the j-th device, and 'N' otherwise. A wireless sensor network in this problem always represents a directed acyclic graph, so if device d1 can transmit data directly or indirectly to device d2, then device d2 can't transmit data directly or indirectly to device d1. You are also given a String nearest, the i-th character of which is 'Y' if the i-th device can communicate directly with the control center, and 'N' otherwise. You must assign a parent to each device in a way that minimizes the burden level of the entire network. Return a int[], the i-th element of which is the parent assigned to the i-th device. If the parent is another device, the i-th element must be the 0-based index of the parent device. If the parent is the control center, the i-th element must be n, where n is the number of devices in the network. If there are multiple possible return values, return the one among them that comes first lexicographically. If it is not possible to assign parents in such a way that the control center can receive all the devices' readings, return an empty int[].

Notes

A int[] a1 comes before a int[] a2 lexicographically if a1 contains a smaller value at the first index at which they differ.

Constraints

network will contain between 1 and 50 elements, inclusive.
Each element of network will contain exactly n characters, where n is the number of elements in network.
Each element of network will contain characters 'N' and 'Y' only.
network will represent a directed acyclic graph.
nearest will contain exactly n characters, where n is the number of elements in network.
nearest will contain characters 'N' and 'Y' only.

Examples

{"NNY","NNY","NNN"}
"NNY"
Returns: {2, 2, 3 }

There is only one possible configuration here. Assign device 2 as the parent of devices 0 and 1, and assign the control center as the parent of device 2. The network's burden level here is 2.

{"NYY","NNY","NNN"}
"NNY"
Returns: {1, 2, 3 }

This is similar to example 0, but in this case, device 0 can transmit data directly to device 1. Therefore, we assign device 1 as the parent of device 0 because that reduces the network's burden level to 1.

{"NYNNNN","NNNNNN","NYNYNN","NNNNNN","NYNYNN","NYNNNN"}
"NYNYNN"
Returns: {1, 6, 3, 6, 3, 1 }

{"N"}
"Y"
Returns: {1 }

{"N"}
"N"
Returns: { }

There is only one device here, and it cannot communicate directly with the control center. Therefore, it is impossible for the control center to get readings from the device.

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

Coding Area

Language: C++17 · define a public class WSNParentsAssignment with a public method vector<int> minNetworkBurdenLevel(vector<string> network, string nearest) · 81 test cases · 2 s / 256 MB per case