Connection Status:
Competition Arena > KingdomReorganization

KingdomReorganization

SRM 531 · 2011-11-22 · by Mimino

SRM 531 · 2011-11-22 · by Mimino · Graph Theory, Greedy
Class Name: KingdomReorganization
Return Type: int
Method Name: getCost
Arg Types: (vector<string>, vector<string>, vector<string>)
Problem Statement

Problem Statement

This problem statement contains subscripts and may not be shown properly outside of the applet.


The greatest king of all times, Michael IV, is going to make big changes in his kingdom. The kingdom is composed of N cities (for simplicity numbered from 0 to N-1). Some pairs of cities are connected by bidirectional roads. We say that there is a path between different cities A and B if there exists a sequence of unique cities {C1, C2, ..., CM}, such that C1 = A and CM = B and for each index i < M, there is a road between cities Ci and Ci+1.


The current state of the kingdom is miserable. Some pairs of cities are not connected by any path. On the other hand, other pairs of cities are connected by multiple different paths, and that leads to complicated traffic routing. Michael wants to build some new roads and destroy some of the already existing roads in the kingdom so that after the reconstruction there will exist exactly one path between every pair of distinct cities. As building new roads and destroying old ones costs a lot of money, Michael wants to minimize the total cost spent on the reconstruction.


You are given a String[] kingdom describing the current state of the kingdom. There is a road between the cities i and j if and only if kingdom[i][j] = '1' and kingdom[j][i] = '1'. You are also given a String[] build and a String[] destroy. If no road exists between cities i and j, then the cost of building it is encoded by build[i][j]. If there already is a road between cities i and j, then the cost of destroying it is encoded by destroy[i][j]. The costs in both String[]s are encoded as characters, where 'A', 'B', ..., 'Z' represent the costs 0, 1, ..., 25, respectively and 'a', 'b', ..., 'z' represent the costs 26, 27, ..., 51, respectively. Your task is to find and return the minimal cost needed for the kingdom reconstruction.

Notes

  • N, the number of cities in the kingdom can be determined as the number of elements of kingdom.
  • Two paths {A1, A2, ..., AR} and {B1, B2, ..., BS} are considered different if either R is not equal to S or there exists i <= R, such that Ai is not equal to Bi.
  • There can never exist a road leading from some city to itself.
  • The values in build that correspond to existing roads can simply be ignored. Similarly, ignore the values in destroy that correspond to nonexistent roads.

Constraints

  • N will be between 1 and 50, inclusive.
  • kingdom, build and destroy will each contain N elements.
  • Each of the elements of kingdom, build and destroy will contain N characters.
  • Each character in each element of kingdom will be either '0' or '1'.
  • For each i, kingdom[i][i] will be '0'.
  • For each i and j, kingdom[i][j] will be equal to kingdom[j][i].
  • Each character in each element of build and destroy will be either an uppercase letter ('A'-'Z') or a lowercase letter ('a'-'z').
  • For each i, build[i][i] and destroy[i][i] will be 'A'.
  • For each i and j, build[i][j] will be equal to build[j][i].
  • For each i and j, destroy[i][j] will be equal to destroy[j][i].
Examples
0)
{"000","000","000"}
{"ABD","BAC","DCA"}
{"ABD","BAC","DCA"}
Returns: 3

There are three cities in the kingdom, totally disconnected. The only optimal solution is to build the roads between cities 0-1 (cost 1) and 1-2 (cost 2).

1)
{"011","101","110"}
{"ABD","BAC","DCA"}
{"ABD","BAC","DCA"}
Returns: 1

Now the three cities form a connected triangle and we need to destroy one road. Optimal solution is to destroy the road between the cities 0-1 (cost 1).

2)
{"011000","101000","110000","000011","000101","000110"}
{"ABDFFF","BACFFF","DCAFFF","FFFABD","FFFBAC","FFFDCA"}
{"ABDFFF","BACFFF","DCAFFF","FFFABD","FFFBAC","FFFDCA"}
Returns: 7

We have six cities forming two separate triangles. Like in the Example 1, destroy one road in each triangle (costs 1 for each road) and then join the triangles by a new road (costs 5).

3)
{"0"}
{"A"}
{"A"}
Returns: 0

One city is okay just as it is.

4)
{"0001","0001","0001","1110"}
{"AfOj","fAcC","OcAP","jCPA"}
{"AWFH","WAxU","FxAV","HUVA"}
Returns: 0

We have four cities, which are connected in such a way that there is exactly one path between each two cities. Thus there is nothing to reconstruct.

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

Coding Area

Language: C++17 · define a public class KingdomReorganization with a public method int getCost(vector<string> kingdom, vector<string> build, vector<string> destroy) · 36 test cases · 2 s / 256 MB per case

Submitting as anonymous