Connection Status:
Competition Arena > NetworkSecurity

NetworkSecurity

SRM 480 · 2009-11-12 · by dolphinigle

SRM 480 · 2009-11-12 · by dolphinigle · Graph Theory, Greedy
Class Name: NetworkSecurity
Return Type: int
Method Name: secureNetwork
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

TopCoder Security Agency (TSA) has been hired to secure a network system. In this network, there are several client computers and server computers which for the sake of conciseness will be called clients and servers, respectively. There are several one directional data cables in the network: between clients and from clients to servers. A data path in the network is defined as a series of 2 or more computers C1, C2, C3, ..., CN such that for each i between 1 and N-1, there exists a data cable from Ci to C(i+1). To avoid infinite data loops, the network is acyclic, that is, there does not exist a data path that originates and ends at the same computer. A client C is connected to a server S if there exists a data path originating at C and ending at S.

TSA is going to secure the network by installing data gates on some of the cables. The network is said to be secure if for every pair of connected client and server, there exists at least one data path between them which uses at least one cable on which a data gate is installed.

There are N clients numbered 0 through N-1 and M servers numbered 0 through M-1. The data cables are given as String[] clientCable and String[] serverCable. The j-th character of the i-th element of clientCable is 'Y' if there exists a data cable from client i to client j, or 'N' otherwise. The j-th character of the i-th element of serverCable is 'Y' if there exists a data cable from client i to server j, or 'N' otherwise.

Return the minimum number of data gates that needs to be installed to make the network secure.

Constraints

  • clientCable will contain between 1 and 50 elements, inclusive.
  • Each element of clientCable will contain exactly N characters, where N is the number of elements in clientCable.
  • Each character in clientCable will be 'Y' or 'N'.
  • The i-th character of the i-th element of clientCable will be 'N'.
  • serverCable will contain the same number of elements as clientCable.
  • Each element of serverCable will contain between 1 and 50 characters, inclusive.
  • All elements of serverCable will contain the same number of characters.
  • Each character in serverCable will be 'Y' or 'N'.
  • The network will be acyclic as described in the problem statement.
Examples
0)
{"NYN"
,"NNN"
,"NYN"}
{"YN"
,"YN"
,"NY"}
Returns: 2

All three clients are connected to server 0 and only client 2 is connected to server 1. If the data gates are installed on the two cables as shown in the picture above, then each of the following data paths between a client and server will contain at least one cable on which a data gate is installed: C0->C1->S0 C1->S0 C2->C1->S0 C2->S1

1)
{"NN"
,"NN"}
{"NNN"
,"NNN"}
Returns: 0

No client is connected to any server and hence the network is secure.

2)
{"NYNN"
,"NNNN"
,"NNNY"
,"NNNN"}
{"YYN"
,"NNN"
,"NNY"
,"NNN"}
Returns: 3
3)
{"N"}
{"N"}
Returns: 0
4)
{"N"}
{"Y"}
Returns: 1

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

Coding Area

Language: C++17 · define a public class NetworkSecurity with a public method int secureNetwork(vector<string> clientCable, vector<string> serverCable) · 134 test cases · 2 s / 256 MB per case

Submitting as anonymous