GraphLabel
SRM 256 · 2005-08-02 · by lars2520
SRM 256 · 2005-08-02 · by lars2520 · Brute Force
Problem Statement
Problem Statement
An undirected graph is defined as a set of vertices with undirected edges connecting some of the pairs of vertices.
You will be given such a graph as a String[] where character j of element i is a '1' if and only if vertices i and j are connected. Such a graph has as many vertices in it as there are elements in the String[] . Your task is to assign an integer between 1 and the total number of vertices, inclusive, to each of these vertices. You may not assign the same integer to multiple vertices. Your goal is to assign these integers such that vertices which are connected have integers which are close to each other numerically. More specifically, let max be the maximum difference between the two integers assigned to any two connected vertices. You want to assign the integers to the vertices such that max is minimized. You should return that minimum max.
Constraints
- graph will contain between 2 and 9 elements, inclusive.
- Each element of graph will contain as many characters as graph has elements.
- Each character in graph will be '0' or '1'.
- Character j of element i of graph will be the same as character i of element j for all i and j.
- Character i of element i of graph will be '0' for all i.
- At least one character in graph will be '1'.
Examples
0)
{"010000",
"101111",
"010111",
"011010",
"011101",
"011010"}
Returns: 3
One way to do this is to assign the label 1 to the first vertex (represented by element 0 of the input), 3 to the second vertex, 4 to the third, 2 to the fourth, 5 to the fifth, and 6 to the sixth.
1)
{"01111001",
"10101000",
"11000101",
"10000111",
"11000111",
"00111000",
"00011000",
"10111000"}
Returns: 4
The labels corresponding to the elements of the input are: 2 1 3 4 5 7 8 6
2)
{"011110101",
"100111000",
"100000111",
"110011011",
"110101001",
"010110110",
"101001010",
"001101101",
"101110010"}
Returns: 4
3)
{"011111111",
"101111111",
"110111111",
"111011111",
"111101111",
"111110111",
"111111011",
"111111101",
"111111110"}
Returns: 8
4)
{"01","10"}
Returns: 1
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class GraphLabel with a public method int adjacentDifference(vector<string> graph) · 58 test cases · 2 s / 256 MB per case