TopCoder problem "MallSecurity" used in Member SRM 468 (Division I Level Three)



Problem Statement

    The first mall of the kingdom is about to be inaugurated in a few days. The king wants to make sure that the mall is highly secured.



The mall has N floors, numbered 1 to N. Each floor has stations which allow people to enter or leave the floor to which the station belongs. All escalators in the mall begin and end at stations of adjacent floors. To make movement of people easier, super-escalators connect stations in floor 1 to stations in floor N. Each escalator or super-escalator can be used to go upwards as well as downwards. If the i-th floor has Ki stations then the stations are numbered from 1 to Ki. The escalators and super-escalators are constructed in such a way that a person can reach any station from any other station using them.



The king wants to have as many guards in the mall as possible to make it secure. Guards can only be placed at stations and at most 1 guard can be placed at a station. Moreover, the people of the kingdom become panicky if they see more than one guard at a time. Hence, there should be no such escalator (or super-escalator) such that guards are placed at both its end stations.



You are given a String[] escDescription which when concatenated represents a comma (',') separated list of escalators and super-escalators. Every escalator (or super-escalator) is of the form "A B C". If C is less than N, the String represents an escalator from station A of floor C, to station B of floor C+1. If C is equal to N, then the String represents a super-escalator from station A of floor C (= N), to station B of floor 1. Help the king by returning the maximum number of guards he can place in the mall.

 

Definition

    
Class:MallSecurity
Method:maxGuards
Parameters:int, String[]
Returns:int
Method signature:int maxGuards(int N, String[] escDescription)
(be sure your method is public)
    
 

Constraints

-N will be between 10 and 50, inclusive.
-The total number of stations in the mall will not exceed 100.
-escDescription will contain between 1 and 50 elements, inclusive.
-Each element of escDescription will contain between 1 and 50 characters, inclusive.
-The concatenation of the elements of escDescription will be a comma separated list of escalators and super-escalators.
-Each escalator and super-escalator will be given as "A B C" (quotes for clarity), where A, B and C are positive integers with no leading zeros.
-In each escalator and super-escalator description, A will be a valid number of station located on floor C.
-In each escalator and super-escalator description, B will be a valid number of station located on floor C + 1 (or on floor 1, if C = N).
-In each escalator and super-escalator description, C will be between 1 and N, inclusive.
-Each floor will have at least 1 station.
-The stations on each floor will be numbered from 1 to K, inclusive, where K is the total number of stations on this floor.
-Each pair of stations will be connected with at most one escalator or super-escalator.
-It will be possible to reach any station from any other station using escalators and super-escalators.
 

Examples

0)
    
10
{"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ", 
 "1 9,1 1 10"}
Returns: 5
There are 10 floors and each floor has only one station. The stations on adjacent floors are connected with escalators. The stations on floor 1 and on floor 10 are connected with a super-escalator. You can place 5 guards on stations of the following floors: 1, 3, 5, 7 and 9. Another solution is to place them on floors 2, 4, 6, 8, 10.
1)
    
11
{"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ", 
 "1 9,1 1 10"}
Returns: 6
This time there are 11 floors and there's no super-escalator. You can place 6 guards on stations of the following floors: 1, 3, 5, 7, 9, 11.
2)
    
10
{"1 1 7,1 2 9,2 1", 
 " 8,1 2 6,1 1 8,1 2 3,1 2 2,2 ", 
 "2 4,1 1 1,2 1 2,3 2 3,1 1 5,2 1 1,4 ", 
 "1 7,1 1 10,3 2 5,1 2 5,3 3 1,", 
 "3 2 8,3 1 2,1 1 3,4 4 2,2", 
 " 4 6,4 2 5,2 3 3,6 4 1,5 2 8,1 3 6,1 3 7,", 
 "4 3 8,1 3 8,5 2 3,4 2 8,2 6 7,1 3 9,", 
 "1 1 4,6 1 1,2 3 1,5 1 5,6 1 8,5 ", 
 "2 2,3 2 10,3 3 9,1 5 2,4 1 1,1 5 10"}
Returns: 25

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14183&pm=10877

Writer:

keshav_57

Testers:

Rustyoldman , ivan_metelsky , mohamedafattah , it4.kp

Problem categories:

Brute Force, Graph Theory, Math