Statistics

Problem Statement for "TheCitiesAndRoadsDivTwo"

Problem Statement

John and Brus have become very famous people all over the world, especially in Bolivia. Once they decided to visit their fan club in Bolivia. John has an old map of Bolivia which shows all of its cities and the roads connecting them. All roads are bidirectional, meaning they can be traversed in both directions. Since the map is old, it's possible that some additional roads have been built since the map was produced. However, roads are never destroyed in Bolivia, so all the roads on the map still exist.

Brus has discovered on the Internet that each pair of Bolivian cities now has exactly one simple path connecting them. A path between cities A and B is a sequence of cities starting with A and ending with B such that there's a road between each pair of consecutive cities in the sequence. The path is considered simple if it consists of distinct cities.

John and Brus have decided to add some new roads to the old map in such a way that the resulting map satisfies this condition. They can only add a road between a pair of cities if that road did not already exist in the old map. They can't add more than one road between the same pair of cities, and they can't add a road that leads from a city to itself. All added roads must be bidirectional.

You are given a String[] map. The j-th character of the i-th element of map will be 'Y' if there is a road between the i-th and j-th cities on the old map, or 'N' otherwise. Return the number of ways John and Brus can add new roads to the old map. Two ways are considered different if the sets of added roads are distinct. The order in which roads are added does not matter.

Definition

Class:
TheCitiesAndRoadsDivTwo
Method:
find
Parameters:
String[]
Returns:
int
Method signature:
int find(String[] map)
(be sure your method is public)

Notes

  • The answer will always fit in signed 32-bit integer.

Constraints

  • map will contain between 1 and 9 elements, inclusive.
  • Each element of map will contain exactly n characters, where n is the number of elements in map.
  • Each character of map will be either 'Y' of 'N'.
  • The j-th character of the i-th element of map will be equal to the j-th character of the i-th element of map.
  • The i-th character of the i-th element of map will be 'N'.
  • There will be at least one way for John and Brus to add new roads to the old map.

Examples

  1. {"NN", "NN"}

    Returns: 1

    The only way is to connect two cities with a road.

  2. {"NY", "YN"}

    Returns: 1

    Adding no roads is a possible valid way.

  3. {"NNY", "NNN", "YNN"}

    Returns: 2

    There are two possible ways - connect the second city with the first one or with the third one.

  4. {"NYNN", "YNNN", "NNNY", "NNYN"}

    Returns: 4

  5. {"N"}

    Returns: 1

  6. {"NNY", "NNY", "YYN"}

    Returns: 1

  7. {"NYN", "YNN", "NNN"}

    Returns: 2

  8. {"NNNNN", "NNNNN", "NNNNN", "NNNNN", "NNNNN"}

    Returns: 125

  9. {"NNYNNNYN", "NNNNNYNN", "YNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NYNNNNYN", "YNNNNYNN", "NNNNNNNN"}

    Returns: 320

  10. {"N"}

    Returns: 1

  11. {"N"}

    Returns: 1

  12. {"NNYNNNN", "NNNNNNN", "YNNNNNN", "NNNNNNY", "NNNNNNN", "NNNNNNN", "NNNYNNN"}

    Returns: 1372

  13. {"NNNNNNNN", "NNNNNNNY", "NNNNNYYN", "NNNNYNNN", "NNNYNNYN", "NNYNNNNN", "NNYNYNNN", "NYNNNNNN"}

    Returns: 80

  14. {"N"}

    Returns: 1

  15. {"NNNYNYN", "NNNNNNN", "NNNNNNY", "YNNNNNN", "NNNNNNN", "YNNNNNN", "NNYNNNN"}

    Returns: 294

  16. {"N"}

    Returns: 1

  17. {"NNY", "NNY", "YYN"}

    Returns: 1

  18. {"N"}

    Returns: 1

  19. {"NYNN", "YNNN", "NNNY", "NNYN"}

    Returns: 4

  20. {"NNNNNY", "NNNNNN", "NNNYNN", "NNYNNN", "NNNNNN", "YNNNNN"}

    Returns: 144

  21. {"NYYNN", "YNNYN", "YNNNY", "NYNNN", "NNYNN"}

    Returns: 1

  22. {"NNNNNNNYN", "NNNNNNYYN", "NNNNNNNNY", "NNNNNYNNN", "NNNNNNNNY", "NNNYNNYNN", "NYNNNYNNY", "YYNNNNNNN", "NNYNYNYNN"}

    Returns: 1

  23. {"NYNN", "YNNY", "NNNY", "NYYN"}

    Returns: 1

  24. {"NYNYYN", "YNYNNN", "NYNNNY", "YNNNNN", "YNNNNN", "NNYNNN"}

    Returns: 1

  25. {"NNYYYNNN", "NNYNNNNN", "YYNNNYNN", "YNNNNNNN", "YNNNNNNY", "NNYNNNYN", "NNNNNYNN", "NNNNYNNN"}

    Returns: 1

  26. {"NNYNYNN", "NNNYNYY", "YNNNNNN", "NYNNNNN", "YNNNNYN", "NYNNYNN", "NYNNNNN"}

    Returns: 1

  27. {"NYNNY", "YNNNN", "NNNYY", "NNYNN", "YNYNN"}

    Returns: 1

  28. {"NNNYNNN", "NNNYNNY", "NNNNNNY", "YYNNNNN", "NNNNNNY", "NNNNNNY", "NYYNYYN"}

    Returns: 1

  29. {"NYN", "YNY", "NYN"}

    Returns: 1

  30. {"NNNNYNN", "NNNNYNN", "NNNNYNY", "NNNNNNY", "YYYNNNN", "NNNNNNY", "NNYYNYN"}

    Returns: 1

  31. {"NNNNN", "NNNNN", "NNNNN", "NNNNN", "NNNNN"}

    Returns: 125

  32. {"NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN"}

    Returns: 262144

  33. {"NNNN", "NNNN", "NNNN", "NNNN"}

    Returns: 16

  34. {"NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN"}

    Returns: 16807

  35. {"NNN", "NNN", "NNN"}

    Returns: 3

  36. {"NNNN", "NNNN", "NNNN", "NNNN"}

    Returns: 16

  37. {"NNNN", "NNNN", "NNNN", "NNNN"}

    Returns: 16

  38. {"N"}

    Returns: 1

  39. {"NNNN", "NNNN", "NNNN", "NNNN"}

    Returns: 16

  40. {"N"}

    Returns: 1

  41. {"NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN"}

    Returns: 4782969

  42. {"NNNNNYNNN", "NNNYNNNNN", "NNNNNNNNY", "NYNNNNYNY", "NNNNNNNNY", "YNNNNNYYN", "NNNYNYNNN", "NNNNNYNNN", "NNYYYNNNN"}

    Returns: 1

  43. {"NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNYNN", "NNNNNNNNN", "NNNNNNNNN", "NNNYNNNNN", "NNNNNNNNN", "NNNNNNNNN"}

    Returns: 1062882

  44. {"NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN"}

    Returns: 4782969

  45. {"NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN"}

    Returns: 4782969

  46. {"NNNNNNNNY", "NNNNNNNNN", "NNNYNYNNN", "NNYNNNYNN", "NNNNNNNNN", "NNYNNNNYN", "NNNYNNNNN", "NNNNNYNNN", "YNNNNNNNN"}

    Returns: 810

  47. {"NYNNNNNNY", "YNNNNNNNN", "NNNNNNNNY", "NNNNNNYNN", "NNNNNNNYN", "NNNNNNYNN", "NNNYNYNNY", "NNNNYNNNN", "YNYNNNYNN"}

    Returns: 14

  48. {"NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN" }

    Returns: 4782969

  49. {"NNNNNNNYN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "YNNNNNNNN", "NNNNNNNNN" }

    Returns: 1062882

  50. {"NYNNNNNNY", "YNNNNNYNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NYNNNNNNN", "NNNNNNNNN", "YNNNNNNNN" }

    Returns: 26244

  51. {"NYNN", "YNNN", "NNNY", "NNYN" }

    Returns: 4

  52. {"NYNNNNNNN", "YNNNNNNNN", "NNNYNNNNN", "NNYNNNNNN", "NNNNNYNNN", "NNNNYNNNN", "NNNNNNNYN", "NNNNNNYNY", "NNNNNNNYN" }

    Returns: 1944

  53. {"NNN", "NNN", "NNN" }

    Returns: 3

  54. {"NYNNN", "YNNNN", "NNNNN", "NNNNY", "NNNYN" }

    Returns: 20

  55. {"NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN", "NNNNNNN" }

    Returns: 16807

  56. {"NYNN", "YNYN", "NYNY", "NNYN" }

    Returns: 1

  57. {"NNNNNN", "NNYNNN", "NYNNNN", "NNNNYN", "NNNYNY", "NNNNYN" }

    Returns: 36

  58. {"NYNNNNNNN", "YNNNNNNNN", "NNNYYNNNN", "NNYNNNNNN", "NNYNNNNNN", "NNNNNNNNN", "NNNNNNNYN", "NNNNNNYNN", "NNNNNNNNN" }

    Returns: 8748

  59. {"NYNNNNNNN", "YNYNNNNNN", "NYNNNNNNN", "NNNNYNNNN", "NNNYNYNNN", "NNNNYNNNN", "NNNNNNNYN", "NNNNNNYNY", "NNNNNNNYN" }

    Returns: 243

  60. {"NYNN", "YNNN", "NNNN", "NNNN" }

    Returns: 8

  61. {"NYNNNN", "YNNNNN", "NNNYNN", "NNYNNN", "NNNNNY", "NNNNYN" }

    Returns: 48

  62. {"NNNNN", "NNNNN", "NNNNN", "NNNNN", "NNNNN" }

    Returns: 125

  63. {"NYNNNNNNN", "YNYNNNNNN", "NYNNNNNNN", "NNNNYNNNN", "NNNYNNNNN", "NNNNNNYNN", "NNNNNYNYN", "NNNNNNYNY", "NNNNNNNYN" }

    Returns: 216

  64. {"NNNN", "NNNN", "NNNN", "NNNN" }

    Returns: 16

  65. {"NNY", "NNN", "YNN" }

    Returns: 2

  66. {"NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN", "NNNNNNNN" }

    Returns: 262144

  67. {"NNNN", "NNNN", "NNNY", "NNYN" }

    Returns: 8

  68. {"NYNNNNNNN", "YNNNNNNNN", "NNNYNNNNN", "NNYNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN" }

    Returns: 236196

  69. {"NYNNN", "YNNNN", "NNNNN", "NNNNN", "NNNNN" }

    Returns: 50

  70. {"NYYNN", "YNNNN", "YNNNN", "NNNNN", "NNNNN" }

    Returns: 15

  71. {"NYNNNNN", "YNNNNNN", "NNNYNNN", "NNYNNNN", "NNNNNYN", "NNNNYNY", "NNNNNYN" }

    Returns: 84

  72. {"NYNNNNNNN", "YNYNNNNNN", "NYNNNNNNN", "NNNNYNNNN", "NNNYNYNNN", "NNNNYNNNN", "NNNNNNNYN", "NNNNNNYNN", "NNNNNNNNN" }

    Returns: 1458

  73. {"NY", "YN" }

    Returns: 1

  74. {"NYNNN", "YNNNY", "NNNYN", "NNYNN", "NYNNN" }

    Returns: 6

  75. {"NYNNN", "YNNNN", "NNNYN", "NNYNN", "NNNNN" }

    Returns: 20

  76. {"NYNNNNNNN", "YNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN" }

    Returns: 1062882

  77. {"NNNYY", "NNNNN", "NNNNN", "YNNNN", "YNNNN" }

    Returns: 15

  78. {"NNNNNN", "NNYNNN", "NYNNNN", "NNNNYY", "NNNYNN", "NNNYNN" }

    Returns: 36

  79. {"NYNNNNNNN", "YNNNNNNNN", "NNNYNNNNN", "NNYNNNNNN", "NNNNNYNNN", "NNNNYNNNN", "NNNNNNNYN", "NNNNNNYNN", "NNNNNNNNN" }

    Returns: 11664

  80. {"NNNNNN", "NNNNNN", "NNNNNN", "NNNNNN", "NNNNNN", "NNNNNN" }

    Returns: 1296

  81. {"NYNNNNNN", "YNNNNNNN", "NNNYNNNN", "NNYNNNNN", "NNNNNYNN", "NNNNYNNN", "NNNNNNNY", "NNNNNNYN" }

    Returns: 1024

  82. {"NNNNNNNNY", "NNNNNNNYN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NNNNNNNNN", "NYNNNNNNN", "YNNNNNNNN" }

    Returns: 236196

  83. {"NYYN", "YNNN", "YNNN", "NNNN" }

    Returns: 3

  84. {"NNNN", "NNNY", "NNNN", "NYNN" }

    Returns: 8

  85. {"NYYNN", "YNNNN", "YNNNN", "NNNNY", "NNNYN" }

    Returns: 6

  86. {"NNNNY", "NNYYY", "NYNNN", "NYNNN", "YYNNN" }

    Returns: 1

  87. {"NYNNNN", "YNNNNN", "NNNYNN", "NNYNNN", "NNNNNN", "NNNNNN" }

    Returns: 144

  88. {"NNNNNN", "NNNNNY", "NNNNNN", "NNNNNN", "NNNNNN", "NYNNNN" }

    Returns: 432

  89. {"NYN", "YNY", "NYN" }

    Returns: 1

  90. {"NYYNNNN", "YNNNNNN", "YNNNNNN", "NNNNYNN", "NNNYNNN", "NNNNNNY", "NNNNNYN" }

    Returns: 84

  91. {"NNYNNY", "NNNNNN", "YNNNNN", "NNNNNN", "NNNNNN", "YNNNNN" }

    Returns: 108

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: