TopCoder problem "NetworkSecurity" used in SRM 480 (Division I Level Two)



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.
 

Definition

    
Class:NetworkSecurity
Method:secureNetwork
Parameters:String[], String[]
Returns:int
Method signature:int secureNetwork(String[] clientCable, String[] serverCable)
(be sure your method is public)
    
 

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10736

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14159&pm=10736

Writer:

dolphinigle

Testers:

PabloGilberto , ivan_metelsky , it4.kp

Problem categories:

Graph Theory, Greedy