Statistics

Problem Statement for "ExtendedDominoes"

Problem Statement

This problem statement contains superscripts that may not display correctly in some plugins. If that's the case, use the arena to see them.

You have recently bought a game of extended dominoes. Each domino is a rectangle partitioned into two squares, and each square contains a number between 0 and 9, inclusive. There are exactly 45 pieces - one for each pair of distinct numbers. Pieces may be reversed, so while there is only one piece containing the numbers 1 and 2, it can be used in either of the following ways: 

   +---+---+     +---+---+
   | 1 | 2 |     | 2 | 1 |
   +---+---+     +---+---+

Unfortunately, some of the pieces have disappeared, but there is still a possible game left: How many ways are there to construct a cycle collection with all the remaining pieces?

A cycle collection is a set of 1 or more cycles that do not share pieces. A cycle is constructed by ordering and orienting the pieces in such a way that the left number of the piece in position i is equal to the right number of the piece in position i-1, and the left number of the piece in the first position is equal to the right number of the piece in the last position (positions are numbered from left to right). 

   +---+---++---+---++---+---++---+---++---+---++---+---+
   | 1 | 2 || 2 | 5 || 5 | 4 || 4 | 2 || 2 | 8 || 8 | 1 |   
   +---+---++---+---++---+---++---+---++---+---++---+---+

   +---+---++---+---++---+---++---+---++---+---++---+---+
   | 1 | 2 || 2 | 4 || 4 | 5 || 5 | 2 || 2 | 8 || 8 | 1 |   
   +---+---++---+---++---+---++---+---++---+---++---+---+

   +---+---++---+---++---+---+  +---+---++---+---++---+---+
   | 1 | 2 || 2 | 8 || 8 | 1 |  | 4 | 5 || 5 | 2 || 2 | 4 |   
   +---+---++---+---++---+---+  +---+---++---+---++---+---+

The figure above shows three possible cycle collections that use the same set of pieces. We say that each piece is connected to the two pieces that surround it, and the first and last pieces are also connected. Two cycles are considered the same if each piece is connected to the same two other pieces in both cycles. Two cycle collections are the same if they contain the same set of cycles.

You will be given the existing pieces as a String[] pieces, where each element contains exactly two digits representing the two numbers on a single domino. Return the number of distinct cycle collections that can be formed with these pieces.

Definition

Class:
ExtendedDominoes
Method:
countCycles
Parameters:
String[]
Returns:
long
Method signature:
long countCycles(String[] pieces)
(be sure your method is public)

Notes

  • Remember that each cycle collection must use all the pieces, and no two cycles in a collection can share pieces.

Constraints

  • pieces will contain between 1 and 45 elements, inclusive.
  • Each element of pieces will contain exactly 2 characters.
  • Each character of each element of pieces will be a digit ('0'-'9').
  • In each element of pieces the value of its first character will be less than the value of its second character.
  • No two elements of pieces will be equal.
  • The number of cycles for pieces will be less than 263.

Examples

  1. {"12","25","45","24","28","18"}

    Returns: 3

    The example in the problem statement.

  2. {"01","12","23","34","45"}

    Returns: 0

    There is no way to form a cycle here.

  3. {"09","12","24","14","57","79","05"}

    Returns: 1

    The only possibility is: +---+---++---+---++---+---++---+---+ +---+---++---+---++---+---+ | 0 | 9 || 9 | 7 || 7 | 5 || 5 | 0 | | 1 | 2 || 2 | 4 || 4 | 1 | +---+---++---+---++---+---++---+---+ +---+---++---+---++---+---+

  4. {"34","35","36","37","45","46","47","56","57","67"}

    Returns: 243

  5. {"09"}

    Returns: 0

  6. {"36","18"}

    Returns: 0

  7. {"16","12","26"}

    Returns: 1

  8. {"57","69","12","08","39","35","07","46","18","24"}

    Returns: 1

  9. {"12","23","13","14","24","34"}

    Returns: 0

  10. {"12","23","13","14","24","34","45","15"}

    Returns: 0

  11. {"24","26","48","17","58","05","16","45","13","89","59","79","18","38","47","67","46","36","03","02","28","01","09","57","56","06","78","29","15","12","39","34","14","07","49","19","04","08","23","25","37","68","27","35","69"}

    Returns: 0

  12. {"69","48","17","79","13","19","49","37","39"}

    Returns: 0

  13. {"58","28","45","18","48","37","39","05","23","01","35","03","02","19","13","07","89","38","47","17","08","12","68","57","24","56","34","14","49","16","59","25","78","04"}

    Returns: 0

  14. {"34","67","07","89","16","58","26","25","35","23","49","15","13","01","12","45","24","78","19","02","69","29","79","68","57","14","38","56","39","36","59","06","37","46","03","27","05","17","09"}

    Returns: 0

  15. {"28","19","79","69","89","37","04","58","49","27","46","24","13","68","78","57","23","03","06","01","39","08","29","25"}

    Returns: 0

  16. {"25","16","36","24","13","27","17","09","04","29","14","48","58","05","79","18","68","38","03","59","02","07","57","08","06","15","49","37","26","19","28","46","47","39","69","35"}

    Returns: 0

  17. {"08","29","35","09","06","47","04","79","68","26","36","48","69","39","18","28","03","13","57","07","15","25","58","19","24","38","16","49","27","02","37","14","05","59","46","17"}

    Returns: 0

  18. {"05","68","24","57","69","49","26","56","34","36","23","78","46","18","37","13","12","08","47","14","35","06","27","79","07","16","17","59","45","19","25","38","15","09","04","28","29","39"}

    Returns: 3324274748525390625

  19. {"58","05","68","24","57","69","49","26","56","34","36","23","78","46","18","37","13","12","47","14","35","06","27","79","07","16","17","59","48","19","25","38","15","89","04","28","29","39"}

    Returns: 4653984647935546875

  20. {"58","18","39","36","25","13","19","14","26","06","57","78","59","29","47","56","16","12","04","79","46","49","34","35","02","15","03","68","69","17","24","28","27","89","48","05","07","38"}

    Returns: 0

  21. {"19","25","24","29","02","59","08","46","03","06","49","38","16","05","28","36","26","04","56","17","69","35","09","37","14","48","13","57","47","27","15","58","45","07","34","18","68","78","39","12","79"}

    Returns: 0

  22. {"19","49","03","39","59","17","45","04","06","07","16","58","09","47","46","48","36","68","13","57","38","08","01","78","25","23","05","69","14","89","12","34","28","67","37","15","79","56"}

    Returns: 4653984647935546875

  23. {"18","47","59","58","39","13","16","89","46","45","26","12","07","05","23","49","48","37","36","17","29","34","78","14","79","69","35","56","08","27","25","24","28","15","68","03","19","67"}

    Returns: 4653984647935546875

  24. {"27","04","15","16","25","08","13","45","48","14","36","26","46","18","34","37","68","89","17","24","01","29","38","56","23","03","57","05","78","67","58","59","12","07","39","06","47","02"}

    Returns: 4653984647935546875

  25. {"27","06","57","49","78","05","03","34","38","09","28","36","35","46","69","25","45","59","58","48","08","89"}

    Returns: 0

  26. {"12","19","38","48","23","46","01","04","03","28","27","45","13","47","89","17","67","78","35","68","49","79","36","14","59","37","16","08","39","26","24","02","15","07","29","56","58","69"}

    Returns: 3324274748525390625

  27. {"48","56","25","78","06","17","19","68","14","49","07","79","18","03","37","12","27","29","05","39","38","47","58","04","15","02","28","08","35","23","69","16","57","36","13","59","09","24"}

    Returns: 3324274748525390625

  28. {"03","07","34","06","17","29","49","69","13","59","57","25","15","67","26","28","16","68","48","39","23","08","19","12","79","37","36","05","45","18","27","58","89","02","78","35","14","46"}

    Returns: 3324274748525390625

  29. {"28","68","58","69","17","34","49","09","56","46","24","48","23","89","27","57","06","39","19","12","67","29","38","15","01","37","07","13","26","25","14","18","08","45","35","59","36","04"}

    Returns: 3324274748525390625

  30. {"45","05","67","49","47","12","03","57","26","48","37","68","29","36","56","46","69","04","13","58","01","78","16","38","09","79","59","08","27","14","24","17","15","25","89","23","28","19"}

    Returns: 3324274748525390625

  31. {"09","28","05","18","04","27","23","24","39","67","16","48","46","36","07","25","45","47","38","58","08","35","49","89","06","17","29","14","59","37","01","57","02","12","68","19","15","79"}

    Returns: 3324274748525390625

  32. {"23","78","25","03","01","58","17"}

    Returns: 1

  33. {"46","56","17","37","12","07","05","26","15","34","68","48","08","49","57","01","89"}

    Returns: 2187

  34. {"25","06","67","14","24","09","08","05","16","59","13","03","58","49","79","04","69","48","19","38","46","36"}

    Returns: 4100625

  35. {"67","07","18","46","69","68","01","09","35","78","14","05","58","34","49","59","38","79","37","89","17"}

    Returns: 2460375

  36. {"24","79","25","16","39","12","34","28","67","17","27","15","18","13","23"}

    Returns: 2025

  37. {"23","48","68","37","47","58","27","57","26","38","39","34","35","59","45","25"}

    Returns: 18225

  38. {"37","78","34","14","27","28","38","17","68","56","03","79","09","57"}

    Returns: 135

  39. {"58","16","29","23","12","56","19","13","08","05","47","27","45"}

    Returns: 27

  40. {"24","37","04","58","69","15","25","35","01","79","08","06"}

    Returns: 9

  41. {"08","47","15","37","19","57","02","78","49","18","58","35","12"}

    Returns: 81

  42. {"13","15","05","35","39","79","78","36","56","08"}

    Returns: 9

  43. {"19","02","23","57","09","69","25","06","59","04","05","36","16","03","12","37","14"}

    Returns: 10935

  44. {"47","67","17","19","48","39","45","04","37","06","14","05","18","12","57","01","07","59","02","49"}

    Returns: 455625

  45. {"89","16","05","13","08","38","47","26","36","19","12","17","48","37","34","28","14","49","02","39","68","57","06","46"}

    Returns: 61509375

  46. {"49","69","57","24","07","79","27","68","35","38","09"}

    Returns: 9

  47. {"02","18","25","08","14","48","49","38","47","34","45","01","23","28","13","36","68","03","79"}

    Returns: 91125

  48. {"01","24","39","79","08","17","78","04","13","68","19","06","67","48","14","69","12"}

    Returns: 10935

  49. {"49","48","47","16","67","69","57","46","34","08","35","37","04","03","89","59","58","01"}

    Returns: 32805

  50. {"89","56","34","26","37","13","08","25","59","14","15","09","01","48","29","69","18","78","07","47","35","28","17","06","58","38","39","05","57"}

    Returns: 226046953125

  51. {"45","23","69","39","67","27","36","34","25","18","38","68","78","89","46","26","37","49","48","14"}

    Returns: 1366875

  52. {"18","58","29","37","17","39","46","36","09","14","68","78","25","79","24","04","89","59","12","02","56","48","35","49","27","45","07","69","47","67"}

    Returns: 1582328671875

  53. {"13","57","25","27","28","34","59","18","45","02","08","47","01","89","17","58","35","05","04","14","12","78","19","48","38","15","07","29"}

    Returns: 527442890625

  54. {"12","29","05","03","37","49","67","56","26","18","07","06","14","24","47","27","39","23","69","19","79","68"}

    Returns: 4100625

  55. {"18","38","15","58","39","67","35","23","04","19","89","01","49","05","24","29","03","78","45","69","59","37","09","27","48","47","06","07","26","02"}

    Returns: 1130234765625

  56. {"47","08","05","39","34","07","56","01","36","27","35","58","59","57","12"}

    Returns: 405

  57. {"49","47","67","79","18","69","58","17","89","46","48","59","15","19","56"}

    Returns: 10935

  58. {"79","38","48","06","25","46","14","17","89","01","67","05","47","28","16","03"}

    Returns: 729

  59. {"45","07","47","14","25","69","09","78","23","05","19","06","89","58","57","67","37","08","49","17","68","18","15","01","79"}

    Returns: 717609375

  60. {"38","79","35","06","04","68","36","57","15","34","59","39","37","16","67","09","13","47","03","46","17"}

    Returns: 5740875

  61. {"35","46","26","24","34","27","59","23","48","25","08","69","45","47","49","02","05","07","14","15","67","56","16","03","06","38","57","37","18","36","39"}

    Returns: 11076300703125

  62. {"29","56","06","37","17","14","57","04","03","79","12","27","34","05","78","35","23","18","01","59","67","49","07","58","25","16","19","24","89","45","13"}

    Returns: 7911643359375

  63. {"16","38","39","34","28","08","89","12","46","24","23","78","68","69","49","67","03","27","02","48","36","17","18","56","04","25","26"}

    Returns: 21097715625

  64. {"09","14","58","07","35","34","01","59","45","18","13","38","29","02","03","25","47","78","89","79","05","57","28","23","15","12","19","17"}

    Returns: 376744921875

  65. {"49","27","39","15","16","14","13","58","25","23","26","19","45","09","78","29","05","28","34","46","01","89","56","04"}

    Returns: 61509375

  66. {"08","68","35","69","07","79","16","26","49","57","46","56","59","67","13","39","36","02","37","17","09","05","03","15"}

    Returns: 239203125

  67. {"27","78","28","17","18","48","47"}

    Returns: 9

  68. {"24","58","12","67","37","15","48","13","03","57","16","36","38","34","07","49","35","23","14","26","02","27","06","68","47","19"}

    Returns: 2152828125

  69. {"35","39","29","56","36","89","16","27","15","69","46","28","05","01","03","02","06"}

    Returns: 0

  70. {"24","69","67","14","49","25","18","28","46","47","13","15","58","07","19","06","17","12","16","02","27","34","08","26","57","23","78"}

    Returns: 0

  71. {"38","14","18","08","67","26","23","48","36","02","37","49","04","46","12","47","16","45","58","79","24","28","29","39","78","89","34","27","25","35","57","15","13","69","19","17"}

    Returns: 0

  72. {"29","12","35","08","58","37","78","03","47","67","38","36","59","56","57","48","04","05"}

    Returns: 0

  73. {"19","34","02","12","56","26","17","45","07","04","57","46","16","03","79","05","78","18","29","09"}

    Returns: 0

  74. {"45","06","16","69","04","36","27","24","56","67","09","46","03"}

    Returns: 0

  75. {"19","38","37","39","46","13","78","68","67","79","25","18","48","69","36","03","06","89","49","14"}

    Returns: 0

  76. {"35","26","08","13","15","38","39","56","09","19","02","48","03","49","07","23","37","24","04","46","06","05","34","57","01","59","89"}

    Returns: 0

  77. {"06","17","05","89","03","47","59","27","35","01","48","78","49","67","58","45","39","09","07","68","56","28"}

    Returns: 0

  78. {"69","15","29","45","18","28","37","07","14","05","57","24","19","17","09","08","68","12","26","89","03","34","78","39","16","04","58","27","79","67","02","36","59","23","48","01","06"}

    Returns: 0

  79. {"58","23","01","57","45","68","46","28","04","69","16","13","79","03","26","59","78","39","25","38","07","36","48","18","08","17","35","09","06","15","56","89","37","05"}

    Returns: 0

  80. {"26","17","03","06","58","02","08","67","28","68","25","07","05","01","13","79","09","46","27","16","15","23","34","78","18"}

    Returns: 717609375

  81. {"37","19","24","38","35","39","15","45","27","47","29","56","68","08","89","14","13","28","01","36","09","49","17","18","12","34","26","03"}

    Returns: 45209390625

  82. {"08","29","06","23","16","34","17","46","03","89","15","68","56","25","67","47","69","26","12","14","78","49","58","04","01","38","57","05","19","48","09","02","24","18","27"}

    Returns: 13568468361328125

  83. {"01", "02", "12", "03", "13", "23", "04", "14", "24", "34", "05", "15", "25", "35", "45", "06", "16", "26", "36", "46", "56", "07", "17", "27", "37", "47", "57", "67", "08", "18", "28", "38", "48", "58", "68", "78" }

    Returns: 1551328215978515625

  84. {"12", "13", "14", "15", "16", "17", "18", "19", "23", "24", "25", "26", "27", "28", "29", "34", "35", "36", "37", "38", "39", "45", "46", "47", "48", "49", "56", "57", "58", "59", "67", "68", "69", "78", "79", "89" }

    Returns: 1551328215978515625

  85. {"12", "13", "14", "15", "16", "17", "23", "24", "25", "26", "27", "34", "35", "36", "37", "45", "46", "47", "56", "57", "67", "09", "89", "08" }

    Returns: 170859375

  86. {"01", "12", "02", "03", "04", "34", "05", "06", "56" }

    Returns: 15

  87. {"01", "02", "03", "04", "05", "06", "12", "34", "56" }

    Returns: 15

  88. {"01", "02", "03", "04", "05", "06", "07", "08", "12", "13", "14", "15", "16", "17", "18", "23", "24", "25", "26", "27", "28", "34", "35", "36", "37", "38", "45", "46", "47", "48", "56", "57", "58", "67", "68", "78" }

    Returns: 1551328215978515625

  89. {"01", "02", "03", "04", "05", "06", "07", "08", "09", "12", "13", "14", "15", "16", "17", "18", "19", "23", "24", "25", "26", "27", "28", "29", "34", "35", "36", "37", "38", "39", "45", "46", "47", "48", "49", "56", "57", "58", "59", "67", "68", "69", "78", "79", "89" }

    Returns: 0

  90. {"34", "35", "36", "37", "45", "46", "47", "56", "57", "67", "16", "17", "26", "27" }

    Returns: 6075

  91. {"01", "02", "03", "04", "05", "06", "07", "08", "12", "34", "56", "78" }

    Returns: 105

  92. {"01", "18", "08", "12", "23", "13", "14", "45", "15" }

    Returns: 15

  93. {"01", "02", "03", "04", "12", "34", "05", "06", "56" }

    Returns: 15

  94. {"01", "12", "02", "13", "34", "04", "05", "15", "18", "89", "19" }

    Returns: 45

  95. {"01", "02", "03", "12", "13", "23" }

    Returns: 0

  96. {"34", "35", "36", "37", "45", "46", "47", "56", "57", "67" }

    Returns: 243

  97. {"01", "02", "03", "04", "05", "06", "12", "13", "14", "15", "16", "23", "24", "25", "26", "34", "35", "36", "45", "46", "56" }

    Returns: 170859375

  98. {"01", "02", "03", "04", "05", "06", "07", "08", "12", "13", "14", "15", "16", "17", "18", "24", "25", "26", "27", "28", "34", "35", "36", "37", "38", "45", "46", "47", "48", "56", "57", "58", "67", "68", "79", "89", "29", "39" }

    Returns: 4653984647935546875

  99. {"12", "13", "14", "15", "16", "17", "01", "19", "02", "03", "04", "05", "06", "07", "09", "23", "24", "25", "26", "27", "29", "34", "35", "36", "37", "39", "45", "46", "47", "49", "56", "57", "59", "67", "69", "79" }

    Returns: 1551328215978515625

  100. {"01", "02", "03", "04", "05", "06", "12", "13", "14", "15", "16", "17", "18", "23", "24", "25", "26", "27", "28", "34", "35", "36", "37", "38", "45", "46", "47", "48", "56", "57", "58", "67", "68" }

    Returns: 4522822787109375

  101. {"12", "23", "13", "34", "24" }

    Returns: 0

  102. {"01", "02", "03", "04", "05", "06", "07", "08", "09", "12", "13", "14", "15", "16", "17", "18", "19", "23", "24", "25", "26", "27", "28", "29", "34", "35", "36", "37", "38", "39", "45", "46", "47", "48", "49", "56", "57", "58", "59", "67", "68", "69", "78" }

    Returns: 0

  103. {"19", "29", "13", "39", "24", "49" }

    Returns: 3

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: