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 vector clientCable and vector 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:vector , vector
Returns:int
Method signature:int secureNetwork(vector clientCable, vector serverCable)
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
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.