Connection Status:
Competition Arena > StrangeCountry

StrangeCountry

SRM 441 · 2009-05-27 · by giolekva

SRM 441 · 2009-05-27 · by giolekva · Graph Theory, Greedy
Class Name: StrangeCountry
Return Type: int
Method Name: transform
Arg Types: (vector<string>)
Problem Statement

Problem Statement

There is a country with N cities, some of which are connected with bidirectional roads. Your task is to reconfigure the roads so that it is possible to get from each city to every other city. You must do this using the minimum possible number of transformations, where each transformation consists of the following steps:
  1. Choose four different cities A, B, C and D, where roads (A, B) and (C, D) exist, but (A, C), (A, D), (B, C) and (B, D) do not exist.
  2. Destroy roads (A, B) and (C, D).
  3. Build two new roads - either (A, C) and (B, D), or (A, D) and (B, C).
The following images show an example of this transformation. From the first situation you can get the second one or the third one:
  

You are given a String[] g, where the j-th character of the i-th element is 'Y' if there is a road between cities i and j, and 'N' otherwise. Return minimal number of transformations required to accomplish your task, or return -1 if it is impossible.

Constraints

  • g will contain between 2 and 50 elements, inclusive.
  • Each element of g will contain exactly N characters 'Y' or 'N', where N is the number of elements in g.
  • For each i and j, g[i][j] will be equal to g[j][i].
  • For each i, g[i][i] will be equal to 'N'.
Examples
0)
{"NY",
 "YN"}
Returns: 0

This country is already connected.

1)
{"NYYNN",
 "YNYNN",
 "YYNNN",
 "NNNNY",
 "NNNYN"}
Returns: 1
2)
{"NYYNNNN",
 "YNYNNNN",
 "YYNNNNN",
 "NNNNYYN",
 "NNNYNYY",
 "NNNYYNY",
 "NNNNYYN"}
Returns: 1
3)
{"NYNYNNNNNNNN",
 "YNYNNNNNNNNN",
 "NYNYYNNNNNNN",
 "YNYNNNNNNNNN",
 "NNYNNYYNNNNN",
 "NNNNYNYNNNNN",
 "NNNNYYNNNNNN",
 "NNNNNNNNYYNN",
 "NNNNNNNYNYNN",
 "NNNNNNNYYNNN",
 "NNNNNNNNNNNY",
 "NNNNNNNNNNYN"}
Returns: 2
4)
{"NYNNNN",
 "YNYNNN",
 "NYNYNN",
 "NNYNNN",
 "NNNNNY",
 "NNNNYN"}
Returns: -1

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

Coding Area

Language: C++17 · define a public class StrangeCountry with a public method int transform(vector<string> g) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous