Statistics

Problem Statement for "GraphLabel"

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.

Definition

Class:
GraphLabel
Method:
adjacentDifference
Parameters:
String[]
Returns:
int
Method signature:
int adjacentDifference(String[] graph)
(be sure your method is public)

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

  1. {"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.

  2. {"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

  3. {"011110101", "100111000", "100000111", "110011011", "110101001", "010110110", "101001010", "001101101", "101110010"}

    Returns: 4

  4. {"011111111", "101111111", "110111111", "111011111", "111101111", "111110111", "111111011", "111111101", "111111110"}

    Returns: 8

  5. {"01","10"}

    Returns: 1

  6. {"0000000","0001011","0001001","0110101","0001000","0100001","0111010"}

    Returns: 2

  7. {"00001001","00111111","01001011","01000011","11100000","01000011","01110100","11110100"}

    Returns: 4

  8. {"0000111","0011001","0100101","0100001","1010010","1000100","1111000"}

    Returns: 2

  9. {"011011110","101111011","110111011","011001010","111001011","111110110","100001000","111111001","011010010"}

    Returns: 5

  10. {"01110010","10010101","10000011","11000100","00000000","01010010","10100100","01100000"}

    Returns: 3

  11. {"01110011","10001101","10001001","10000010","01100110","01001001","10011001","11100110"}

    Returns: 4

  12. {"01","10"}

    Returns: 1

  13. {"0110","1000","1000","0000"}

    Returns: 1

  14. {"01100","10010","10001","01000","00100"}

    Returns: 1

  15. {"0011000","0011010","1100101","1100010","0010000","0101000","0010000"}

    Returns: 2

  16. {"011011110","100000110","100100100","001011111","100101101","100110000","111110011","110100100","000110100"}

    Returns: 4

  17. {"001011010","000111010","100101100","011010100","110101001","111010001","001100011","110000100","000011100"}

    Returns: 5

  18. {"01","10"}

    Returns: 1

  19. {"001","001","110"}

    Returns: 1

  20. {"001110100","001001111","110111001","101011100","101101100","011110001","110110010","010000101","011001010"}

    Returns: 4

  21. {"0011010","0001101","1001011","1110111","0101001","1011001","0111110"}

    Returns: 3

  22. {"000010","001001","010011","000011","101100","011100"}

    Returns: 2

  23. {"01011101","10100000","01000111","10001100","10010000","10110000","00100001","10100010"}

    Returns: 3

  24. {"0010000","0010101","1101001","0010001","0100000","0000000","0111000"}

    Returns: 2

  25. {"01","10"}

    Returns: 1

  26. {"0100","1001","0001","0110"}

    Returns: 1

  27. {"001001111","000100010","100111000","011000000","001000010","101000001","100000000","110010000","100001000"}

    Returns: 3

  28. {"01101011","10011111","10001110","01001011","11110001","01100011","11110101","11011110"}

    Returns: 5

  29. {"000","001","010"}

    Returns: 1

  30. {"0110100","1010100","1100011","0000010","1100010","0011101","0010010"}

    Returns: 3

  31. {"00001011","00000100","00010101","00101111","10010011","01110011","10011100","10111100"}

    Returns: 3

  32. {"000010011","001011100","010001101","000011111","110101100","011110100","011111010","100100101","101100010"}

    Returns: 4

  33. {"00111111","00011011","10000010","11000110","11000001","10010000","11110000","11001000"}

    Returns: 4

  34. {"01010011","10101000","01001100","10001111","01110011","00110001","10011000","10011100"}

    Returns: 4

  35. {"00111100","00010001","10011011","11100101","10100110","10011000","00101000","01110000"}

    Returns: 3

  36. {"01010111","10110011","01010110","11100011","00000101","10101000","11110000","11011000"}

    Returns: 4

  37. {"01000","10011","00001","01000","01100"}

    Returns: 2

  38. {"01100","10011","10001","01001","01110"}

    Returns: 2

  39. {"010011","101101","010000","010000","100000","110000"}

    Returns: 2

  40. {"00011110","00001111","00011111","10101100","11110101","11111001","11100001","01101110"}

    Returns: 4

  41. {"000011100","000010001","000000100","000000100","110000100","100000111","101111001","000001001","010001110"}

    Returns: 3

  42. {"000010101","001110001","010001011","010000010","110000111","001000100","100011001","001110001","111010110"}

    Returns: 4

  43. {"011100101","100101100","100110011","111011111","001100111","010100101","110111001","001110001","101111110"}

    Returns: 4

  44. {"00011010","00001100","00000110","10001001","11010000","01100010","10100100","00010000"}

    Returns: 2

  45. {"01","10"}

    Returns: 1

  46. {"0001110","0000001","0001011","1010001","1000000","1010001","0111010"}

    Returns: 3

  47. {"010","101","010"}

    Returns: 1

  48. {"001100101","000000001","100000011","100000011","000000110","000000101","100011000","001110000","111101000"}

    Returns: 4

  49. {"000111000","000110011","000010100","110000111","111000100","100000011","001110011","010101101","010101110"}

    Returns: 5

  50. {"00011101","00100001","01011010","10100111","10100001","10010010","00110101","11011010"}

    Returns: 4

  51. {"010011000","101010111","010001101","000001011","110001101","101110100","011011011","010100100","011110100"}

    Returns: 5

  52. {"010111110","101001100","010001110","100001111","100001110","111110010","111110001","101111001","000100110"}

    Returns: 5

  53. {"000100110","001001010","010111011","101011100","001100000","011100101","100101011","111000101","001001110"}

    Returns: 4

  54. {"001","000","100"}

    Returns: 1

  55. {"01","10"}

    Returns: 1

  56. {"011111111", "101111111", "110111111", "111011111", "111101111", "111110111", "111111010", "111111101", "111111010" }

    Returns: 7

  57. {"011111111", "101111111", "110111111", "111011111", "111101111", "111110111", "111111010", "111111101", "111111010" }

    Returns: 7

  58. {"011111111", "101111111", "110111111", "111011111", "111101111", "111110111", "111111010", "111111101", "111111010" }

    Returns: 7

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: