TopCoder problem "RoadsReorganization" used in TCHS07 Finals (Division I Level Three)



Problem Statement

    

A Kingdom consists of several cities, some of which are connected by bidirectional roads. For any two cities A and B, there is exactly one simple path between them (a path is simple if it doesn't contain any city more than once). In terms of graph theory, the roads network in the Kingdom is a tree.

Unfortunately, the new King does not like trees, so he wants the road network to be a loop. In other words, each city must be directly connected to exactly 2 other cities, and for any two cities there still must be at least one path between them.

You will be given a String[] kingdom, representing the roads in the Kingdom. The i-th character in the j-th element of kingdom is equal to '1' (one) if there is a road between the i-th and the j-th cities, and '0' (zero) otherwise. Given that destroying a road or building a new road takes exactly one day, and knowing that King has only enough workers to perform 1 task per day, return the minimal number of days King needs to change the network to satisfy the new requirements. See examples for further clarification.

 

Definition

    
Class:RoadsReorganization
Method:minDaysCount
Parameters:String[]
Returns:int
Method signature:int minDaysCount(String[] kingdom)
(be sure your method is public)
    
 

Constraints

-kingdom will contain between 3 and 50 elements, inclusive.
-Each element of kingdom will contain exactly n characters, where n is the number of elements in kingdom.
-Each element of kingdom will contain only '0' (zero) and '1' (one) characters.
-The j-th character in the i-th element of kingdom will be equal to the i-th character in the j-th element of kingdom.
-The i-th character in the i-th element of kingdom will be '0'.
-There will be exactly one simple path between every pair of cities.
 

Examples

0)
    
{"010", "101", "010"}
Returns: 1
One day is needed to add the road between the 0-th and 2-nd cities.
1)
    
{"0111",
 "1000",
 "1000",
 "1000"}
Returns: 3
Remove any single road, and add another two.
2)
    
{"01010", "10100", "01000", "10001", "00010"}
Returns: 1
Add one road between the 2-nd and 4-th cities.
3)
    
{"0100100", "1011000", "0100000", "0100000", "1000011", "0000100", "0000100"}
Returns: 5
4)
    
{"011111", "100000", "100000", "100000", "100000", "100000"}
Returns: 7

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10764&pm=7808

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Dynamic Programming