Statistics

Problem Statement for "RoadReform"

Problem Statement

There are n cities in the Kingdom. Some pairs of cities are connected by bidirectional roads, and there exists a path between every pair of cities.

The King thinks that supporting so many roads is very expensive, so he decided to close some of them. He wants to close as many roads as possible, but, of course, he still wants each city to be reachable from any other city.

A city is a dead end if it is connected to only one other city by a direct road. You will be given a String[] roads, with the j-th character of the i-th element of roads being '1' (one) if the i-th and j-th cities are connected by a direct road, and '0' (zero) otherwise. Return the maximal number of dead ends the Kingdom may have after the reform.

Definition

Class:
RoadReform
Method:
findMaxDeadendCount
Parameters:
String[]
Returns:
int
Method signature:
int findMaxDeadendCount(String[] roads)
(be sure your method is public)

Constraints

  • roads will contain between 2 and 15 elements, inclusive.
  • Each element of roads will contain exactly n characters, where n is the number of elements in roads.
  • Each element of roads will contain digits '0' and '1' only.
  • The j-th character in the i-th element of roads will be equal to the i-th character in the j-th element.
  • The i-th character in the i-th element of roads will be '0'.
  • Each pair of cities in the input will be connected by a path.

Examples

  1. {"01", "10"}

    Returns: 2

    Two cities are connected by a road. The King can't close this road and both cities will still be dead ends.

  2. {"01000", "10100", "01010", "00101", "00010"}

    Returns: 2

    The cities of the Kingdom are aligned in a chain. As in example 0, no road can be closed without splitting the Kingdom.

  3. {"01111", "10000", "10000", "10000", "10000"}

    Returns: 4

  4. {"0111", "1011", "1101", "1110"}

    Returns: 3

    Each pair of cities is connected by a direct road. The King can close roads 1<->2, 2<->3 and 1<->3, thus making cities 1, 2 and 3 dead ends.

  5. {"0100000001", "1010000000", "0101000000", "0010100000", "0001010000", "0000101000", "0000010100", "0000001010", "0000000101", "1000000010"}

    Returns: 2

  6. {"011111111111111", "101111111111111", "110111111111111", "111011111111111", "111101111111111", "111110111111111", "111111011111111", "111111101111111", "111111110111111", "111111111011111", "111111111101111", "111111111110111", "111111111111011", "111111111111101", "111111111111110"}

    Returns: 14

  7. { "011", "100", "100" }

    Returns: 2

  8. { "0101", "1000", "0001", "1010" }

    Returns: 2

  9. { "0001", "0001", "0001", "1110" }

    Returns: 3

  10. { "00101", "00011", "10000", "01000", "11000" }

    Returns: 2

  11. { "00111", "00010", "10000", "11000", "10000" }

    Returns: 3

  12. { "01101", "10011", "10011", "01101", "11110" }

    Returns: 4

  13. { "000101", "000001", "000010", "100010", "001100", "110000" }

    Returns: 2

  14. { "000100", "000010", "000011", "100010", "011100", "001000" }

    Returns: 3

  15. { "010000", "101010", "010101", "001000", "010001", "001010" }

    Returns: 4

  16. { "011011", "100011", "100111", "001001", "111001", "111110" }

    Returns: 5

  17. { "0000011", "0001100", "0000010", "0100000", "0100001", "1010000", "1000100" }

    Returns: 2

  18. { "0100110", "1000101", "0000100", "0000010", "1110000", "1001000", "0100000" }

    Returns: 3

  19. { "0110010", "1000000", "1000000", "0000101", "0001011", "1000100", "0001100" }

    Returns: 4

  20. { "0000100", "0011100", "0100100", "0100001", "1110001", "0000001", "0001110" }

    Returns: 5

  21. { "0110111", "1011111", "1100110", "0100111", "1111001", "1111001", "1101110" }

    Returns: 6

  22. { "01100000", "10000010", "10000001", "00000001", "00000110", "00001000", "01001000", "00110000" }

    Returns: 2

  23. { "00010010", "00000100", "00000001", "10001100", "00010000", "01010000", "10000001", "00100010" }

    Returns: 3

  24. { "01000101", "10001000", "00000001", "00000001", "01000010", "10000000", "00001000", "10110000" }

    Returns: 4

  25. { "01000101", "10110100", "01001010", "01000100", "00100001", "11010010", "00100100", "10001000" }

    Returns: 5

  26. { "01111010", "10100011", "11011001", "10101000", "10110001", "00000001", "11000001", "01101110" }

    Returns: 6

  27. { "00111111", "00011000", "10011011", "11101000", "11110111", "10001010", "10101101", "10101010" }

    Returns: 7

  28. { "001000000", "000000001", "100100000", "001001000", "000000101", "000100010", "000010010", "000001100", "010010000" }

    Returns: 2

  29. { "001000100", "000000011", "100011000", "000001000", "001000010", "001100000", "100000000", "010010000", "010000000" }

    Returns: 3

  30. { "000001010", "001100000", "010000100", "010000010", "000000001", "100000000", "001000010", "100100101", "000010010" }

    Returns: 4

  31. { "000000001", "001100001", "010010010", "010010011", "001100100", "000000100", "000011000", "001100000", "110100000" }

    Returns: 5

  32. { "010000000", "100001110", "000100101", "001000000", "000000100", "010000000", "011010000", "010000000", "001000000" }

    Returns: 6

  33. { "011110000", "100000110", "100111001", "101001100", "101000100", "001100010", "010110011", "010001101", "001000110" }

    Returns: 7

  34. { "011111110", "100111110", "100111111", "111011101", "111101011", "111110111", "111101011", "111011101", "001111110" }

    Returns: 8

  35. { "0000001100", "0001000010", "0000010001", "0100000000", "0000000001", "0010000100", "1000000010", "1000010000", "0100001000", "0010100000" }

    Returns: 2

  36. { "0000000011", "0000000010", "0000001000", "0000000101", "0000010000", "0000101100", "0010010000", "0001010000", "1100000000", "1001000000" }

    Returns: 3

  37. { "0001000001", "0001010000", "0000000100", "1100001000", "0000000001", "0100001000", "0001010010", "0010000010", "0000001100", "1000100000" }

    Returns: 4

  38. { "0011001100", "0000000010", "1000001000", "1000010000", "0000000101", "0001000000", "1010000000", "1000100001", "0100000001", "0000100110" }

    Returns: 5

  39. { "0100000001", "1001000011", "0000100000", "0100011110", "0010001010", "0001000001", "0001100110", "0001001000", "0101101000", "1100010000" }

    Returns: 6

  40. { "0010010010", "0001110010", "1000010111", "0100000100", "0100010100", "1110101100", "0000010100", "0011111010", "1110000100", "0010000000" }

    Returns: 7

  41. { "0100000001", "1001101011", "0000010000", "0100011111", "0100010111", "0011100001", "0101000001", "0001100001", "0101100001", "1101111110" }

    Returns: 8

  42. { "0011111111", "0011110101", "1101101100", "1110111111", "1111010101", "1101101110", "1011010011", "1111110011", "1001011100", "1101101100" }

    Returns: 9

  43. { "00000001000", "00001000001", "00010100000", "00100010000", "01000000100", "00100000100", "00010000010", "10000000001", "00001100000", "00000010000", "01000001000" }

    Returns: 2

  44. { "00011000001", "00010000010", "00000000100", "11000000000", "10000001000", "00000010000", "00000101000", "00001010000", "00100000001", "01000000000", "10000000100" }

    Returns: 3

  45. { "00011000001", "00010000010", "00000000100", "11000000000", "10000001000", "00000010000", "00000101000", "00001010000", "00100000001", "01000000000", "10000000100" }

    Returns: 3

  46. { "00000001001", "00010010100", "00010000000", "01100000000", "00000001100", "00000000010", "01000000110", "10001000000", "01001010010", "00000110100", "10000000000" }

    Returns: 4

  47. { "00100010000", "00000101101", "10000000101", "00001001000", "00010000000", "01000000000", "10000000000", "01010000011", "01100000000", "00000001000", "01100001000" }

    Returns: 5

  48. { "00000000100", "00100110010", "01000100010", "00000000010", "00000100110", "01101000010", "01000000000", "00000000001", "10001000000", "01111100001", "00000001010" }

    Returns: 6

  49. { "01000110000", "10000000001", "00000111000", "00000000100", "00000101000", "10101000010", "10100001101", "00101010000", "00010010001", "00000100001", "01000010110" }

    Returns: 7

  50. { "00001101010", "00101101000", "01000010010", "00001100111", "11010110000", "11011001110", "00101000000", "11000100000", "00010100001", "10110100000", "00010000100" }

    Returns: 8

  51. { "01110100110", "10111100011", "11000110011", "11000111101", "01000010001", "11110000001", "00111001010", "00010010100", "10010001010", "11100010101", "01111100010" }

    Returns: 9

  52. { "01111110111", "10001111011", "10001001011", "10001101101", "11110111111", "11011011010", "11001101101", "01111110111", "10011011011", "11101101101", "11111011110" }

    Returns: 10

  53. { "010000001000", "100000100000", "000110000000", "001000010000", "001000000000", "000000000101", "010000000100", "000100000010", "100000000010", "000001100000", "000000011000", "000001000000" }

    Returns: 2

  54. { "000000010100", "001000010001", "010000000010", "000001001000", "000000100010", "000100000100", "000010000000", "110000000000", "000100000001", "100001000000", "001010000000", "010000001000" }

    Returns: 3

  55. { "000010000000", "001000000000", "010000001000", "000000010110", "100001000000", "000010100000", "000001010001", "000100100001", "001000000100", "000100001000", "000100000000", "000000110000" }

    Returns: 4

  56. { "001110000001", "000000000011", "100000000000", "100001000000", "100000010000", "000100000010", "000000001001", "000010000000", "000000100100", "000000001000", "010001000000", "110000100000" }

    Returns: 5

  57. { "010000000001", "100000000000", "000010101000", "000001000101", "001000000000", "000100000000", "001000001000", "000000001010", "001000110001", "000100000001", "000000010000", "100100001100" }

    Returns: 6

  58. { "010111100001", "101000000001", "010000000010", "100010100100", "100101101001", "100010100010", "100111001001", "000000000100", "000010100000", "000100010010", "001001000100", "110010100000" }

    Returns: 7

  59. { "001000000001", "000100001000", "100011100010", "010010001000", "001100000001", "001000000000", "001000010001", "000000100000", "010100000011", "000000000010", "001000001101", "100010101010" }

    Returns: 8

  60. { "001111101000", "000000101100", "100110000110", "101000001011", "101001101100", "100010111000", "110011000010", "000001000100", "110111000101", "011010011000", "001100100000", "000100001000" }

    Returns: 9

  61. { "010100010011", "100110110000", "000100001010", "111000010001", "010001111000", "000010110000", "010011010011", "110111100111", "001010000011", "000000010000", "101000111001", "100100111010" }

    Returns: 10

  62. { "010101101110", "100111101111", "000111111101", "111001111101", "011000111111", "111100111111", "111111001110", "001111001101", "111111110111", "111111111001", "110011101001", "011111011110" }

    Returns: 11

  63. { "0100010000000", "1000000010000", "0000100000010", "0000000100100", "0010000000000", "1000000000100", "0000000100000", "0001001000000", "0100000001000", "0000000010001", "0001010000000", "0010000000001", "0000000001010" }

    Returns: 2

  64. { "0010100000000", "0010000010000", "1100000000000", "0000000010100", "1000000000001", "0000001000100", "0000010001000", "0000000001000", "0101000000000", "0000001100000", "0001010000010", "0000000000101", "0000100000010" }

    Returns: 3

  65. { "0011010000100", "0000000001000", "1000000001000", "1000000100100", "0000001000000", "1000000000001", "0000100100000", "0001001000000", "0000000000010", "0110000000000", "1001000000000", "0000000010001", "0000010000010" }

    Returns: 4

  66. { "0000010011000", "0011000000000", "0100010000000", "0100000010000", "0000000000010", "1010000000000", "0000000000011", "0000000001001", "1001000001100", "1000000110000", "0000000010001", "0000101000000", "0000001100100" }

    Returns: 5

  67. { "0000000001100", "0000010000100", "0000000011010", "0000010000001", "0000000110000", "0101000100000", "0000000100000", "0000111000000", "0010100000001", "1010000000010", "1100000000000", "0010000001000", "0001000010000" }

    Returns: 6

  68. { "0000000001010", "0000010001100", "0000110001010", "0000000000110", "0010000001000", "0110001000000", "0000010000001", "0000000011100", "0000000101100", "1110100110000", "0101000110000", "1011000000000", "0000001000000" }

    Returns: 7

  69. { "0110000000100", "1000101000101", "1001000001000", "0010001100010", "0100000000001", "0000000000001", "0101000001000", "0001000010110", "0000000100000", "0010001000000", "1100000100010", "0001000100100", "0100110000000" }

    Returns: 8

  70. { "0001010010010", "0010000010001", "0100100100001", "1000011010011", "0010000010000", "1001000100000", "0001000011100", "0010010000000", "1101101000100", "0000001000110", "0000001011000", "1001000001000", "0111000000000" }

    Returns: 9

  71. { "0011010000000", "0000000000100", "1000101100010", "1000000000100", "0010010001100", "1000101000000", "0010010001000", "0010000000100", "0000000000100", "0000101000000", "0101100110001", "0010000000000", "0000000000100" }

    Returns: 10

  72. { "0000101001101", "0011111110000", "0101010011000", "0110100101111", "1101000001010", "0110000110111", "1100000010111", "0101010001111", "0110011001010", "1011100110101", "1001011101010", "0001111110101", "1001011101010" }

    Returns: 11

  73. { "0110110000001", "1011111110111", "1101111111111", "0110001111111", "1110011111110", "1110101111010", "0111110111111", "0111111000001", "0111111001111", "0011111010010", "0111101010011", "0111111011101", "1111001110110" }

    Returns: 12

  74. { "00001000000100", "00100000000010", "01000000100000", "00001000001000", "10010000000000", "00000010000000", "00000100000001", "00000000010001", "00100000010000", "00000001100000", "00010000000000", "10000000000010", "01000000000100", "00000011000000" }

    Returns: 2

  75. { "00000100010000", "00100000001000", "01000000000001", "00000000100001", "00000011000000", "10000000000010", "00001000000000", "00001000000100", "00010000000000", "10000000000100", "01000000000100", "00000001011000", "00000100000000", "00110000000000" }

    Returns: 3

  76. { "00000000101000", "00000001000000", "00001000000100", "00000010000001", "00100000100000", "00000010000000", "00010101010000", "01000010000000", "10001000000000", "00000010000000", "10000000000010", "00100000000000", "00000000001001", "00010000000010" }

    Returns: 4

  77. { "01000000000100", "10001000000000", "00010011000000", "00100010001000", "01000000000100", "00000000000100", "00110000010000", "00100000000001", "00000000000011", "00000010001000", "00010000010000", "10001100000010", "00000000100100", "00000001100000" }

    Returns: 5

  78. { "01010000000000", "10001000000010", "00000010000000", "10000000000100", "01000000000000", "00000010010000", "00100100001001", "00000000000010", "00000000010010", "00000100100001", "00000010000000", "00010000000000", "01000001100000", "00000010010000" }

    Returns: 6

  79. { "00000000000100", "00100001010000", "01000000000001", "00000010100100", "00000000010000", "00000000100100", "00010000001011", "01000000000000", "00010100000000", "01001000000000", "00000010000000", "10010100000000", "00000010000000", "00100010000000" }

    Returns: 7

  80. { "00000000000010", "00000110001000", "00010010100000", "00100001000100", "00000000000100", "01000001100100", "01100000000000", "00010100000000", "00100100000010", "00000000000010", "01000000000001", "00011100000000", "10000000110000", "00000000001000" }

    Returns: 8

  81. { "01010011001000", "10000011101000", "00000010110010", "10000000010001", "00000000010000", "00000000100010", "11100001000000", "11000010000000", "01100100000000", "00111000001100", "11000000010100", "00000000011000", "00100100000000", "00010000000000" }

    Returns: 9

  82. { "01101000100100", "10000110000000", "10000001010100", "00001000010010", "10010000101001", "01000000110000", "01000001010000", "00100010001010", "10001100000110", "00110110000100", "00001001000000", "10100000110000", "00010001100000", "00001000000000" }

    Returns: 10

  83. { "00001101001011", "00001000100001", "00001011100001", "00000001000100", "11100110101101", "10001001000100", "00101000110110", "10110100011000", "01101010010000", "00000011100010", "10001001000000", "00011110000000", "10000010010000", "11101000000000" }

    Returns: 11

  84. { "01100001011100", "10110100111011", "11001000000001", "01000100000010", "00100010010010", "01010000100001", "00001000011010", "10000000100110", "01000101000110", "11001010000000", "11000010000000", "10000001100011", "01011011100100", "01100100000100" }

    Returns: 12

  85. { "01011111111111", "10111110111110", "01010111111111", "11101111111011", "11010101011110", "11111011111111", "11110101001001", "10111110001011", "11110100011111", "11111100100111", "11111111100111", "11101100111010", "11111101111101", "10110111111010" }

    Returns: 13

  86. { "010011011111110", "100110101101111", "000101011011101", "011010101011110", "110100100111001", "101000111111111", "010111001111101", "101001001111111", "111101110011010", "110011110001111", "101111111001011", "111111111110111", "111101110101001", "110101011111000", "011011110111100" }

    Returns: 14

  87. { "001101111000010", "000011000011111", "100100010001101", "101001101101110", "010000101010011", "110100111011111", "100111011010000", "101001100011011", "100111100100110", "000100001000111", "010011110000111", "011101010000111", "011101001111000", "110111011111000", "011011010111000" }

    Returns: 13

  88. { "010000010100010", "100010110100110", "000000010011000", "000001001000000", "010001100100011", "000110010100010", "010010001101110", "111001001000011", "000100110011010", "110011100000110", "001000001000011", "001000101000000", "010000100100000", "110011111110001", "000010010010010" }

    Returns: 12

  89. { "000000110100100", "001100000000001", "010001000010010", "010000000011101", "000000011000010", "001000100000010", "100001000000100", "100010000000001", "000010000000000", "100000000011100", "001100000100000", "000100000100010", "100100100100010", "001011000001101", "010100010000010" }

    Returns: 11

  90. { "000001000000000", "001000001001000", "010000101001000", "000011000000100", "000101011000001", "100110010010000", "001000010100010", "000011100000110", "011010000010100", "000000100010000", "000001001100000", "011000000000000", "000100011000000", "000000110000000", "000010000000000" }

    Returns: 10

  91. { "000000000000001", "000100000100010", "000011110000000", "010000100000000", "001000000000000", "001000010000000", "001100001011000", "001001000001011", "000000100000000", "010000000000010", "000000100000001", "000000110000100", "000000000001000", "010000010100000", "100000010010000" }

    Returns: 9

  92. { "001000000000011", "000000010000000", "100000000000000", "000000010100000", "000000000110000", "000000000000001", "000000000001000", "010100001001000", "000000010000000", "000110000000001", "000010000000100", "000000110000010", "000000000010010", "100000000001101", "100001000100010" }

    Returns: 8

  93. { "010000100000001", "100001000000100", "000010000000000", "000001001001000", "001000000000010", "010100000001000", "100000000000000", "000000000000010", "000100000000000", "000000000000011", "000000000000010", "000101000000000", "010000000000000", "000010010110000", "100000000100000" }

    Returns: 7

  94. { "010000000001000", "100000000000000", "000000000100000", "000000000000011", "000000010101000", "000000000000001", "000000000010100", "000010000000010", "000000000101010", "001010001001000", "000000100001000", "100010001110000", "000000100000000", "000100011000000", "000101000000000" }

    Returns: 6

  95. { "000000001001001", "000000010000011", "000010100000000", "000000000000100", "001001000000000", "000010000000000", "001000001000000", "010000000010000", "100000100000000", "000000000010010", "000000010100100", "100000000000000", "000100000010000", "010000000100000", "110000000000000" }

    Returns: 5

  96. { "000100000001000", "000000011000000", "000000001010000", "100001000010000", "000001000000001", "000110000000000", "000000000000001", "010000000000100", "011000000000000", "000000000010010", "001100000100000", "100000000000000", "000000010000000", "000000000100000", "000010100000000" }

    Returns: 4

  97. { "001010000000000", "000001011000000", "100000100000000", "000001000000000", "100000000001000", "010100000000000", "001000000000000", "010000000010000", "010000000000100", "000000000011000", "000000010100000", "000010000100000", "000000001000001", "000000000000001", "000000000000110" }

    Returns: 3

  98. { "010000000000001", "101000000000000", "010100000000000", "001010000000000", "000101000000000", "000010100000000", "000001010000000", "000000101000000", "000000010100000", "000000001010000", "000000000101000", "000000000010100", "000000000001010", "000000000000101", "100000000000010" }

    Returns: 2

  99. {"010000000111", "101000000000", "010100000000", "001010000000", "000101000000", "000010100000", "000001010000", "000000101000", "000000010100", "100000001010", "100000000101", "100000000010" }

    Returns: 4

  100. {"011011111111111", "101011111111111", "110011111111111", "000000000000111", "111001111100111", "111010111010111", "111011010110111", "111011101110111", "111011010110111", "111010111010111", "111001111100111", "111000000000000", "111111111110011", "111111111110101", "111111111110110" }

    Returns: 13

  101. {"01000", "10100", "01010", "00101", "00010" }

    Returns: 2

  102. {"0111", "1011", "1101", "1110" }

    Returns: 3

  103. {"010000000000011", "101000000000001", "010100000000001", "001010000000001", "000101000000001", "000010100000001", "000001010000001", "000000101000001", "000000010100001", "000000001010001", "000000000101001", "000000000010101", "000000000001011", "100000000000101", "111111111111110" }

    Returns: 14

  104. {"011111", "101111", "110111", "111011", "111101", "111110" }

    Returns: 5

  105. {"0100000001", "1010000000", "0101000000", "0010100000", "0001010000", "0000101000", "0000010100", "0000001010", "0000000101", "1000000010" }

    Returns: 2

  106. {"010100011011110", "101010111101100", "010001111110011", "100000110000100", "010000110011110", "001000010110010", "011110001000110", "111111001001100", "111000110001010", "011001000010000", "101011000101000", "110010011010100", "110110110001001", "101011101000001", "001000000000110" }

    Returns: 13

  107. {"011111111111111", "101111111111111", "110111111111111", "111011111111111", "111101111111111", "111110111111111", "111111011111111", "111111101111111", "111111110111111", "111111111011111", "111111111101111", "111111111110111", "111111111111011", "111111111111101", "111111111111110" }

    Returns: 14

  108. {"011111111111110", "101111111111111", "110101111111111", "111011111101110", "110101111111111", "111110111111111", "111111011111111", "111111101111111", "111111110111111", "111111111011111", "111011111101111", "111111111110111", "111111111111011", "111111111111101", "011011111111110" }

    Returns: 14

  109. {"01100", "10111", "11000", "01000", "01000" }

    Returns: 4

  110. {"0110", "1010", "1101", "0010" }

    Returns: 3

  111. {"0101", "1011", "0100", "1100" }

    Returns: 3

  112. {"001010", "001001", "110100", "001011", "100100", "010100" }

    Returns: 4

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: