Statistics

Problem Statement for "TreeUnionDiv2"

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Manao is studying graph theory and simple cycles in particular. A simple cycle of length L ≥ 3 in graph G is a sequence of vertices (v0, v1, ..., vL-1) such that all v0, v1, ..., vL-1 are pairwise distinct and for each i=0..L-1, an edge between vi and v(i+1) mod L exists in G.

Manao is interested in graphs formed by connecting two trees. The connection process is as follows. Manao takes two trees composed of N vertices each. The vertices in each tree are labeled from 0 to N - 1. Then, he generates some permutation P of numbers from 0 to N - 1. Finally, the graph is formed by connecting vertex i of the first tree to vertex P[i] of the second tree, for each i from 0 to N - 1. To remove ambiguity, the vertices of the first tree within the graph are referred to as A0, A1, ..., AN-1 and the vertices of the second graph are referred to as B0, B1, ..., BN-1. Manao wants to know the maximum number of simple cycles of length K which the resulting graph could contain if he chooses P optimally.

You are given two String[]s, tree1 and tree2. Both contain N elements, each of them N characters long. The j-th character in the i-th element of tree1 is 'X' if vertices i and j in the first tree are connected and '-' otherwise. tree2 describes the second tree in the same fashion.

Compute and return the maximum possible number of simple cycles of length K in the graph formed by connecting the two given trees as described above. Two simple cycles are equal if one of them can be cyclically shifted, or reversed and cyclically shifted, to coincide with the second. According to this definition, (1, 2, 3, 4), (2, 3, 4, 1) and (3, 2, 1, 4) are all equal.

Definition

Class:
TreeUnionDiv2
Method:
maximumCycles
Parameters:
String[], String[], int
Returns:
int
Method signature:
int maximumCycles(String[] tree1, String[] tree2, int K)
(be sure your method is public)

Constraints

  • tree1 and tree2 will each contain N elements, where N is between 1 and 9, inclusive.
  • Each element of tree1 and tree2 will be N characters long.
  • Each element of tree1 and tree2 will consist of 'X' and '-' characters only.
  • tree1[i][i] and tree2[i][i] will be '-' for each i between 0 and N-1.
  • tree1[i][j] will be equal to tree1[j][i] for each i, j between 0 and N-1.
  • tree2[i][j] will be equal to tree2[j][i] for each i, j between 0 and N-1.
  • Both tree1 and tree2 will describe a graph which is a tree.
  • K will be between 3 and 7, inclusive.

Examples

  1. {"-X", "X-"}

    {"-X", "X-"}

    4

    Returns: 1

    Manao has two trees with two vertices each. He can connect them in two ways: Either way, the resulting graph is a single cycle of length 4.

  2. {"-X-", "X-X", "-X-"}

    {"-X-", "X-X", "-X-"}

    5

    Returns: 2

    These are the possible six graphs which can be obtained by connecting the two given trees: Except for the two topmost graphs, all the graphs contain two cycles of length 5.

  3. {"-X-", "X-X", "-X-"}

    {"-X-", "X-X", "-X-"}

    3

    Returns: 0

    These are the same trees as in the previous example. You can see at the pictures that none of the obtained graphs contains a cycle of length 3.

  4. {"-X---", "X-XXX", "-X---", "-X---", "-X---"}

    {"-X-X-", "X-X-X", "-X---", "X----", "-X---"}

    6

    Returns: 5

    When the permutation P is {0, 3, 2, 1, 4}, the resulting graph contains the following five simple cycles of length 6: A0, A1, A4, B4, B1, B0 A0, A1, A2, B2, B1, B0 A1, A2, B2, B1, B0, B3 A1, A2, B2, B1, B4, A4 A1, A4, B4, B1, B0, B3 The corresponding graph is the following:

  5. {"-XX------", "X------X-", "X--XX-X--", "--X--X---", "--X------", "---X----X", "--X------", "-X-------", "-----X---"}

    {"-X-------", "X-X------", "-X-XX----", "--X---X--", "--X--X---", "----X--XX", "---X-----", "-----X---", "-----X---"}

    7

    Returns: 17

  6. {"-X--","X-X-","-X-X","--X-"}

    {"---X","--X-","-X-X","X-X-"}

    6

    Returns: 4

  7. {"--X-X","--X--","XX-X-","--X--","X----"}

    {"---X-","----X","---X-","X-X-X","-X-X-"}

    6

    Returns: 8

  8. {"-XX---","X-----","X--XXX","--X---","--X---","--X---"}

    {"-----X","-----X","---X-X","--X---","-----X","XXX-X-"}

    6

    Returns: 13

  9. {"-XXXX--","X------","X------","X-----X","X----X-","----X--","---X---"}

    {"----XXX","---X---","-----X-","-X---X-","X------","X-XX---","X------"}

    6

    Returns: 16

  10. {"-XXXXXXXX", "X--------", "X--------", "X--------", "X--------", "X--------", "X--------", "X--------", "X--------"}

    {"-XXXXXXXX", "X--------", "X--------", "X--------", "X--------", "X--------", "X--------", "X--------", "X--------"}

    6

    Returns: 28

  11. {"-X-XX","X-X--","-X---","X----","X----"}

    {"-XX-X","X----","X--X-","--X--","X----"}

    3

    Returns: 0

  12. {"-X","X-"}

    {"-X","X-"}

    3

    Returns: 0

  13. {"-X-","X-X","-X-"}

    {"-X-","X-X","-X-"}

    3

    Returns: 0

  14. {"-XXX--","X-----","X---XX","X-----","--X---","--X---"}

    {"-XXX-X","X---X-","X-----","X-----","-X----","X-----"}

    3

    Returns: 0

  15. {"-X-X--","X-X--X","-X--X-","X-----","--X---","-X----"}

    {"-X-X--","X-X--X","-X----","X---X-","---X--","-X----"}

    3

    Returns: 0

  16. {"-X--","X-X-","-X-X","--X-"}

    {"-XX-","X---","X--X","--X-"}

    3

    Returns: 0

  17. {"-X-XX","X-X--","-X---","X----","X----"}

    {"-XX-X","X----","X--X-","--X--","X----"}

    3

    Returns: 0

  18. {"-X","X-"}

    {"-X","X-"}

    3

    Returns: 0

  19. {"-X--","X-X-","-X-X","--X-"}

    {"-XX-","X--X","X---","-X--"}

    3

    Returns: 0

  20. {"-X-X","X-X-","-X--","X---"}

    {"-X-X","X-X-","-X--","X---"}

    4

    Returns: 3

  21. {"-X","X-"}

    {"-X","X-"}

    4

    Returns: 1

  22. {"-XXX-X--","X-----X-","X-------","X---X---","---X---X","X-------","-X------","----X---"}

    {"-XXX--X-","X-------","X------X","X---XX--","---X----","---X----","X-------","--X-----"}

    4

    Returns: 6

  23. {"-XXXX-X--","X--------","X----X---","X------X-","X--------","--X-----X","X--------","---X-----","-----X---"}

    {"-XX------","X--------","X--X-XXX-","--X-X----","---X-----","--X-----X","--X------","--X------","-----X---"}

    4

    Returns: 7

  24. {"-XXXXX","X-----","X-----","X-----","X-----","X-----"}

    {"-XX---","X--XX-","X----X","-X----","-X----","--X---"}

    4

    Returns: 3

  25. {"-X---","X-XX-","-X---","-X--X","---X-"}

    {"-X---","X-XX-","-X--X","-X---","--X--"}

    4

    Returns: 4

  26. {"-X-X---","X-X----","-X--X-X","X----X-","--X----","---X---","--X----"}

    {"-XX-X--","X------","X--X---","--X--XX","X------","---X---","---X---"}

    4

    Returns: 5

  27. {"-X------","X-X----X","-X-X-X--","--X-X-X-","---X----","--X-----","---X----","-X------"}

    {"-XXX----","X---XX--","X-------","X------X","-X----X-","-X------","----X---","---X----"}

    4

    Returns: 6

  28. {"-XXX-----","X----X-X-","X--------","X---X-X-X","---X-----","-X-------","---X-----","-X-------","---X-----"}

    {"-X-------","X-XXXX---","-X----X-X","-X-------","-X-------","-X-----X-","--X------","-----X---","--X------"}

    4

    Returns: 7

  29. {"-X-------","X-X------","-X-XXX---","--X------","--X---X--","--X----X-","----X----","-----X--X","-------X-"}

    {"-X-XXX---","X-X------","-X-------","X-----X--","X--------","X--------","---X---XX","------X--","------X--"}

    4

    Returns: 7

  30. {"-X","X-"}

    {"-X","X-"}

    5

    Returns: 0

  31. {"-XX","X--","X--"}

    {"-X-","X-X","-X-"}

    5

    Returns: 2

  32. {"-X","X-"}

    {"-X","X-"}

    5

    Returns: 0

  33. {"-XXX","X---","X---","X---"}

    {"-XX-","X---","X--X","--X-"}

    5

    Returns: 3

  34. {"-X------","X-XX-X--","-X------","-X--X---","---X--X-","-X-----X","----X---","-----X--"}

    {"-X--X---","X-X--X-X","-X-X----","--X-----","X-----X-","-X------","----X---","-X------"}

    5

    Returns: 10

  35. {"-X","X-"}

    {"-X","X-"}

    5

    Returns: 0

  36. {"-XX----","X--XX--","X----X-","-X-----","-X-----","--X---X","-----X-"}

    {"-X-----","X-X----","-X-X-X-","--X-X--","---X---","--X---X","-----X-"}

    5

    Returns: 7

  37. {"-X-----","X-XXX--","-X---X-","-X-----","-X----X","--X----","----X--"}

    {"-X-X---","X-X-XX-","-X-----","X------","-X----X","-X-----","----X--"}

    5

    Returns: 8

  38. {"-X-X--X","X-X----","-X--XX-","X------","--X----","--X----","X------"}

    {"-X----X","X-XX---","-X-----","-X--XX-","---X---","---X---","X------"}

    5

    Returns: 8

  39. {"-X","X-"}

    {"-X","X-"}

    5

    Returns: 0

  40. {"-XX-----","X--X-X-X","X-------","-X--X-X-","---X----","-X------","---X----","-X------"}

    {"-X--X---","X-XX----","-X------","-X---X--","X-----XX","---X----","----X---","----X---"}

    6

    Returns: 14

  41. {"-XX","X--","X--"}

    {"-XX","X--","X--"}

    6

    Returns: 1

  42. {"-X---","X-XXX","-X---","-X---","-X---"}

    {"-X-X-","X-X--","-X---","X---X","---X-"}

    6

    Returns: 3

  43. {"-X","X-"}

    {"-X","X-"}

    6

    Returns: 0

  44. {"-XX-X----","X--X-----","X----X---","-X----XX-","X--------","--X------","---X----X","---X-----","------X--"}

    {"-XXXXX---","X--------","X--------","X--------","X------X-","X-----X-X","-----X---","----X----","-----X---"}

    6

    Returns: 19

  45. {"-X--","X-X-","-X-X","--X-"}

    {"-X--","X-X-","-X-X","--X-"}

    6

    Returns: 4

  46. {"-X--X---","X-XX-X--","-X------","-X-----X","X-----X-","-X------","----X---","---X----"}

    {"-XX----X","X--X--X-","X---X---","-X------","--X--X--","----X---","-X------","X-------"}

    6

    Returns: 16

  47. {"-XX-XX-","X------","X--X---","--X----","X-----X","X------","----X--"}

    {"-X-----","X-XX---","-X-----","-X--XX-","---X---","---X--X","-----X-"}

    6

    Returns: 16

  48. {"-X","X-"}

    {"-X","X-"}

    6

    Returns: 0

  49. {"-X-XX","X-X--","-X---","X----","X----"}

    {"-XX-X","X--X-","X----","-X---","X----"}

    6

    Returns: 8

  50. {"-XX---X--","X--------","X--X-----","--X-XX---","---X-----","---X---XX","X--------","-----X---","-----X---"}

    {"-X-------","X-XX-----","-X--X----","-X----XX-","--X--X---","----X----","---X----X","---X-----","------X--"}

    7

    Returns: 16

  51. {"-X","X-"}

    {"-X","X-"}

    7

    Returns: 0

  52. {"-X","X-"}

    {"-X","X-"}

    7

    Returns: 0

  53. {"-XX------","X--XX----","X----X---","-X-------","-X----X--","--X-----X","----X--X-","------X--","-----X---"}

    {"-X-------","X-XX-----","-X--XX---","-X------X","--X------","--X---XX-","-----X---","-----X---","---X-----"}

    7

    Returns: 17

  54. {"-XX-XX---","X--X-----","X--------","-X------X","X-----X--","X--------","----X--X-","------X--","---X-----"}

    {"-XX------","X-------X","X--X-----","--X-X----","---X-XX--","----X--X-","----X----","-----X---","-X-------"}

    7

    Returns: 17

  55. {"-X-------","X-X-X--XX","-X-X-XX--","--X------","-X-------","--X------","--X------","-X-------","-X-------"}

    {"-XXX---X-","X---X-X--","X--------","X----X---","-X-------","---X----X","-X-------","X--------","-----X---"}

    7

    Returns: 16

  56. {"-X--XX","X-XX--","-X----","-X----","X-----","X-----"}

    {"-X-X--","X-X--X","-X----","X---X-","---X--","-X----"}

    7

    Returns: 7

  57. {"-X---","X-X--","-X-XX","--X--","--X--"}

    {"-X-X-","X-X-X","-X---","X----","-X---"}

    7

    Returns: 4

  58. {"-XX","X--","X--"}

    {"-XX","X--","X--"}

    7

    Returns: 0

  59. {"-XXX","X---","X---","X---"}

    {"-XX-","X---","X--X","--X-"}

    7

    Returns: 1

  60. {"-"}

    {"-"}

    3

    Returns: 0

  61. {"-XX-X---X","X--X-----","X--------","-X---X---","X-----X--","---X-----","----X--X-","------X--","X--------"}

    {"-XX---X--","X--X-----","X---XX---","-X------X","--X------","--X------","X------X-","------X--","---X-----"}

    7

    Returns: 17

  62. {"-XXXX---X","X------X-","X--------","X----XX--","X--------","---X-----","---X-----","-X-------","X--------"}

    {"-X-X-----","X-X------","-X-----X-","X---X-X--","---X-X--X","----X----","---X-----","--X------","----X----"}

    6

    Returns: 21

  63. {"-XXX--X-X","X---X----","X--------","X----X---","-X-------","---X-----","X------X-","------X--","X--------"}

    {"-X-X-----","X-X-X----","-X-----X-","X--------","-X---X---","----X-X--","-----X--X","--X------","------X--"}

    5

    Returns: 10

  64. {"-X-X--X--","X-X------","-X--X--X-","X----X---","--X------","---X----X","X--------","--X------","-----X---"}

    {"-X--X----","X-XX-----","-X-------","-X-------","X----X---","----X-XX-","-----X---","-----X--X","-------X-"}

    4

    Returns: 7

  65. {"-XX------","X---X---X","X--X-X---","--X------","-X-----X-","--X---X--","-----X---","----X----","-X-------"}

    {"-X-------","X-X-X--X-","-X-X-----","--X---X--","-X---X---","----X----","---X----X","-X-------","------X--"}

    5

    Returns: 11

  66. {"-X-X-----","X-X--X---","-X--X-X-X","X--------","--X------","-X-----X-","--X------","-----X---","--X------"}

    {"-X-X--XX-","X-X------","-X-------","X---X----","---X-X---","----X---X","X--------","X--------","-----X---"}

    6

    Returns: 19

  67. {"-XX------","X-----X--","X--X-----","--X-X--X-","---X-X---","----X---X","-X-------","---X-----","-----X---"}

    {"-XXXX--XX","X----X---","X--------","X-----X--","X--------","-X-------","---X-----","X--------","X--------"}

    6

    Returns: 15

  68. {"-X-------","X-XX-----","-X-------","-X--XX-XX","---X--X--","---X-----","----X----","---X-----","---X-----"}

    {"-X-X-XX--","X-X------","-X--X--X-","X--------","--X------","X-------X","X--------","--X------","-----X---"}

    6

    Returns: 19

  69. {"-XXXX----","X--------","X-----X--","X------X-","X----X---","----X---X","--X------","---X-----","-----X---"}

    {"-XX-X----","X--X-----","X----X--X","-X-------","X-----X--","--X----X-","----X----","-----X---","--X------"}

    5

    Returns: 10

  70. {"-XX-----X","X--XX----","X-----XX-","-X---X---","-X-------","---X-----","--X------","--X------","X--------"}

    {"-X-------","X-X-X---X","-X-X-----","--X--X---","-X-------","---X--X--","-----X-X-","------X--","-X-------"}

    6

    Returns: 16

  71. {"-XXX----X","X---X----","X--------","X----XXX-","-X-------","---X-----","---X-----","---X-----","X--------"}

    {"-XX-X-X--","X----X---","X--X-----","--X------","X------X-","-X-------","X--------","----X---X","-------X-"}

    7

    Returns: 18

  72. {"-X-------","X-X------","-X-XX-X--","--X--X---","--X------","---X---XX","--X------","-----X---","-----X---"}

    {"-XX--X---","X--X--X--","X--------","-X--X---X","---X---X-","X--------","-X-------","----X----","---X-----"}

    5

    Returns: 11

  73. {"-X-X-----","X-X--XX--","-X-----X-","X---X----","---X-----","-X-------","-X------X","--X------","------X--"}

    {"-XX--X---","X---X-X--","X--X-----","--X----X-","-X-------","X--------","-X------X","---X-----","------X--"}

    4

    Returns: 7

  74. {"-XX--X---","X-----X--","X--X-----","--X-X----","---X-----","X--------","-X-----XX","------X--","------X--"}

    {"-XX---X--","X---X----","X--X-----","--X------","-X---X--X","----X----","X------X-","------X--","----X----"}

    4

    Returns: 7

  75. {"-X------X","X-X-X----","-X-X-----","--X--X---","-X-----X-","---X--X--","-----X---","----X----","X--------"}

    {"-XX-X----","X------XX","X--X--X--","--X------","X----X---","----X----","--X------","-X-------","-X-------"}

    7

    Returns: 17

  76. {"-X-XX----","X-X-----X","-X----X--","X--------","X----X-X-","----X----","--X------","----X----","-X-------"}

    {"-X-------","X-X---XX-","-X-XX----","--X------","--X--X--X","----X----","-X-------","-X-------","----X----"}

    4

    Returns: 7

  77. {"-XX-X----","X-----XX-","X--X-----","--X--X---","X--------","---X-----","-X-------","-X------X","-------X-"}

    {"-X-----X-","X-XXXX---","-X----X-X","-X-------","-X-------","-X-------","--X------","X--------","--X------"}

    5

    Returns: 11

  78. {"-X--XX-X-","X-XX----X","-X-------","-X----X--","X--------","X--------","---X-----","X--------","-X-------"}

    {"-X-------","X-XXX----","-X-------","-X-------","-X---X-X-","----X-X--","-----X---","----X---X","-------X-"}

    6

    Returns: 19

  79. {"-X-X--X--","X-X-----X","-X--X----","X--------","--X--X-X-","----X----","X--------","----X----","-X-------"}

    {"-X---X-XX","X-XXX----","-X----X--","-X-------","-X-------","X--------","--X------","X--------","X--------"}

    6

    Returns: 21

  80. {"-XXX---X-","X--------","X--------","X---XX--X","---X-----","---X--X--","-----X---","X--------","---X-----"}

    {"-X--X----","X-X------","-X-X-XX--","--X----X-","X--------","--X------","--X------","---X----X","-------X-"}

    6

    Returns: 19

  81. {"-X-XX","X-X--","-X---","X----","X----"}

    {"-XX-X","X--X-","X----","-X---","X----"}

    5

    Returns: 6

  82. {"-XX-X","X--X-","X----","-X---","X----"}

    {"-X---","X-X-X","-X-X-","--X--","-X---"}

    4

    Returns: 4

  83. {"-X---","X-X--","-X-X-","--X-X","---X-"}

    {"-X-X-","X-X--","-X---","X---X","---X-"}

    6

    Returns: 7

  84. {"-XXX--","X----X","X---X-","X-----","--X---","-X----"}

    {"-X--X-","X-XX--","-X---X","-X----","X-----","--X---"}

    6

    Returns: 12

  85. {"-X----","X-XX--","-X---X","-X--X-","---X--","--X---"}

    {"-X-X--","X-X-X-","-X----","X-----","-X---X","----X-"}

    6

    Returns: 12

  86. {"-X--X-","X-X---","-X-X--","--X---","X----X","----X-"}

    {"-X-X--","X-X---","-X--X-","X-----","--X--X","----X-"}

    7

    Returns: 8

  87. {"-X-----","X-X--X-","-X-XX--","--X----","--X---X","-X-----","----X--"}

    {"-X-----","X-X----","-X-X--X","--X-XX-","---X---","---X---","--X----"}

    4

    Returns: 6

  88. {"-X----X","X-X----","-X-X---","--X-XX-","---X---","---X---","X------"}

    {"-XX----","X--X---","X---X-X","-X---X-","--X----","---X---","--X----"}

    7

    Returns: 12

  89. {"-X-X---","X-X-X--","-X---X-","X-----X","-X-----","--X----","---X---"}

    {"-X---X-","X-X----","-X-X---","--X-X--","---X---","X-----X","-----X-"}

    7

    Returns: 11

  90. {"-X---X--","X-X-----","-X-XX---","--X---XX","--X-----","X-------","---X----","---X----"}

    {"-X-X----","X-X-X-X-","-X------","X----X--","-X------","---X----","-X-----X","------X-"}

    5

    Returns: 10

  91. {"-XX-X---","X-------","X--X----","--X--X--","X------X","---X--X-","-----X--","----X---"}

    {"-X---X--","X-X-X---","-X-X---X","--X---X-","-X------","X-------","---X----","--X-----"}

    5

    Returns: 10

  92. {"-X--X---","X-X-----","-X-X--X-","--X-----","X----X--","----X--X","--X-----","-----X--"}

    {"-XX-X-X-","X--X----","X-------","-X------","X----X--","----X--X","X-------","-----X--"}

    6

    Returns: 16

  93. {"-XX-----X","X------X-","X--X-----","--X-XX---","---X--X--","---X-----","----X----","-X-------","X--------"}

    {"-XX-X----","X--X-----","X--------","-X---XX--","X------X-","---X----X","---X-----","----X----","-----X---"}

    4

    Returns: 8

  94. {"-X-------","X-XX--X--","-X--X--X-","-X---X---","--X-----X","---X-----","-X-------","--X------","----X----"}

    {"-X---XXX-","X-XX-----","-X-------","-X--X----","---X-----","X--------","X-------X","X--------","------X--"}

    5

    Returns: 12

  95. {"-XXX---X-","X-----X--","X--------","X---X---X","---X-X---","----X----","-X-------","X--------","---X-----"}

    {"-XX-X----","X--X-----","X------X-","-X---X---","X--------","---X--X-X","-----X---","--X------","-----X---"}

    7

    Returns: 16

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: