Statistics

Problem Statement for "CaterpillarSpanningTrees"

Problem Statement

Time limit is 5 seconds.

Caterpillars are undirected trees in which there exists a path that contains every vertex of degree two or more.

An ASCII drawing of a sample caterpillar is shown below. Horizontal edges in the drawing show one possible path with the property mentioned above. 

                O O O         O   O   O
                 \|/          |    \ /
O --- O --- O --- O --- O --- O --- O
            |     |\          |     |
            O     O O         O     O

You are given the String[] G containing the adjacency matrix of a small undirected graph with N labeled (i.e., distinct) vertices. Count all spanning trees of this graph that are caterpillars.

Definition

Class:
CaterpillarSpanningTrees
Method:
count
Parameters:
String[]
Returns:
long
Method signature:
long count(String[] G)
(be sure your method is public)

Notes

  • Note that we want the exact answer, not an answer modulo something. (The total number of spanning trees of a complete graph on 16 vertices fits into a 64-bit signed integer, so there can be no overflow.)

Constraints

  • N will be between 1 and 16, inclusive.
  • G will contain N elements.
  • Each element of G will contain N characters.
  • Each character in G will be 'Y' or 'N'.
  • For each i, G[i][i] = 'N'.
  • For each i and j, G[i][j] = G[j][i].
  • The graph represented by G will be connected.

Examples

  1. {"NYNN", "YNYY", "NYNY", "NYYN"}

    Returns: 3

    The graph looks as follows: 0---1---2 \ / 3 It has three different spanning trees. Each of those is a caterpillar.

  2. {"N"}

    Returns: 1

    The graph consists of a single isolated vertex. Its spanning tree also consists of that one vertex. By definition, this trivial tree is also a caterpillar so we do count it.

  3. {"NYYYYYY", "YNYYYYY", "YYNYYYY", "YYYNYYY", "YYYYNYY", "YYYYYNY", "YYYYYYN"}

    Returns: 15967

    The complete graph on 7 vertices has 16807 different spanning trees. Almost all of them are caterpillars. The only unlabeled tree on seven vertices that is not a caterpillar is shown below. O---O---O---O---O | O | O There are 7 * 20 * 6 = 840 spanning trees of K_7 that look like this. Thus, there are 16807 - 840 distinct caterpillar spanning trees.

  4. { "NYNNNNNNNNNNN", "YNYNNNNNNNNNN", "NYNYYNNNNNNNN", "NNYNNNNNNNNNN", "NNYNNYYYYYNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNYYY", "NNNNNNNNNYNNN", "NNNNNNNNNYNNN", "NNNNNNNNNYNNN"}

    Returns: 1

    This graph is the 13-vertex caterpillar shown below. 5 6 7 12 \|/ | 0 --- 1 --- 2 --- 4 --- 9 --- 11 | | | 3 8 10

  5. {"NY", "YN"}

    Returns: 1

  6. {"NYY", "YNY", "YYN"}

    Returns: 3

  7. {"NNY", "NNY", "YYN"}

    Returns: 1

  8. {"NYN", "YNY", "NYN"}

    Returns: 1

  9. {"NYY", "YNN", "YNN"}

    Returns: 1

  10. {"NYNY", "YNNN", "NNNY", "YNYN"}

    Returns: 1

  11. {"NNYN", "NNYN", "YYNY", "NNYN"}

    Returns: 1

  12. {"NNYN", "NNYY", "YYNN", "NYNN"}

    Returns: 1

  13. {"NYYY", "YNYY", "YYNY", "YYYN"}

    Returns: 16

  14. {"NYYN", "YNYY", "YYNY", "NYYN"}

    Returns: 8

  15. {"NYNY", "YNYY", "NYNY", "YYYN"}

    Returns: 8

  16. {"NYYY", "YNYY", "YYNY", "YYYN"}

    Returns: 16

  17. {"NYNNN", "YNYYY", "NYNNN", "NYNNN", "NYNNN"}

    Returns: 1

  18. {"NNYNN", "NNYNN", "YYNNY", "NNNNY", "NNYYN"}

    Returns: 1

  19. {"NNYYY", "NNYYN", "YYNNY", "YYNNN", "YNYNN"}

    Returns: 11

  20. {"NNYYY", "NNYNY", "YYNNN", "YNNNY", "YYNYN"}

    Returns: 11

  21. {"NYYNN", "YNYYY", "YYNYY", "NYYNY", "NYYYN"}

    Returns: 40

  22. {"NYYYY", "YNYYY", "YYNYY", "YYYNY", "YYYYN"}

    Returns: 125

  23. {"NNYNNN", "NNYYNY", "YYNNYN", "NYNNNN", "NNYNNN", "NYNNNN"}

    Returns: 1

  24. {"NNYNYN", "NNYNNN", "YYNNNN", "NNNNYY", "YNNYNY", "NNNYYN"}

    Returns: 3

  25. {"NYYYYN", "YNYNYY", "YYNYNN", "YNYNNY", "YYNNNN", "NYNYNN"}

    Returns: 61

  26. {"NYYYNN", "YNYYYY", "YYNYYN", "YYYNYY", "NYYYNY", "NYNYYN"}

    Returns: 336

  27. {"NNYYYN", "NNNNYN", "YNNYYN", "YNYNYY", "YYYYNY", "NNNYYN"}

    Returns: 40

  28. {"NYYYYY", "YNYYYY", "YYNYYY", "YYYNYY", "YYYYNY", "YYYYYN"}

    Returns: 1296

  29. {"NNNNNNY", "NNYNNNN", "NYNNNNY", "NNNNYYN", "NNNYNNY", "NNNYNNN", "YNYNYNN"}

    Returns: 1

  30. {"NNNNYNN", "NNNNYYN", "NNNYYNN", "NNYNYYY", "YYYYNYN", "NYNYYNN", "NNNYNNN"}

    Returns: 21

  31. {"NNYYYYY", "NNYYYNN", "YYNYNNY", "YYYNYNN", "YYNYNNN", "YNNNNNN", "YNYNNNN"}

    Returns: 112

  32. {"NYYYNNY", "YNYYYYY", "YYNNYYY", "YYNNYNY", "NYYYNNY", "NYYNNNN", "YYYYYNN"}

    Returns: 1304

  33. {"NYYYYYN", "YNYNYYY", "YYNYYYY", "YNYNYNY", "YYYYNYN", "YYYNYNY", "NYYYNYN"}

    Returns: 3816

  34. {"NYYYYYY", "YNYYYYY", "YYNYYYY", "YYYNYYY", "YYYYNYY", "YYYYYNY", "YYYYYYN"}

    Returns: 15967

  35. {"NNNNYNNN", "NNYYNYNN", "NYNYNNNN", "NYYNNNYY", "YNNNNNNY", "NYNNNNNN", "NNNYNNNY", "NNNYYNYN"}

    Returns: 9

  36. {"NYYYNYYY", "YNNNNNYN", "YNNYNNYN", "YNYNNNYN", "NNNNNYYY", "YNNNYNYN", "YYYYYYNN", "YNNNYNNN"}

    Returns: 626

  37. {"NNNYYYNY", "NNYNNNNY", "NYNYNYNN", "YNYNNYYN", "YNNNNYYY", "YNYYYNNN", "NNNYYNNN", "YYNNYNNN"}

    Returns: 416

  38. {"NYYNNYNY", "YNNYYNYN", "YNNNYYYY", "NYNNYYNN", "NYYYNNYY", "YNYYNNNY", "NYYNYNNY", "YNYNYYYN"}

    Returns: 4539

  39. {"NYNYNYNY", "YNYYNYYY", "NYNYNYYY", "YYYNYYYY", "NNNYNYYY", "YYYYYNYY", "NYYYYYNY", "YYYYYYYN"}

    Returns: 43305

  40. {"NYYYYYYY", "YNYYYYYY", "YYNYYYYY", "YYYNYYYY", "YYYYNYYY", "YYYYYNYY", "YYYYYYNY", "YYYYYYYN"}

    Returns: 225184

  41. {"NNNNYNYYN", "NNYNYYYNN", "NYNNNYNNY", "NNNNNNNNY", "YYNNNNNNN", "NYYNNNNNN", "YYNNNNNYY", "YNNNNNYNN", "NNYYNNYNN"}

    Returns: 83

  42. {"NNNYYYYNN", "NNNYNNNYN", "NNNNYNNNN", "YYNNNNYYN", "YNYNNYYYN", "YNNNYNYYN", "YNNYYYNNY", "NYNYYYNNN", "NNNNNNYNN"}

    Returns: 429

  43. {"NYYYNNYNN", "YNYNYYNNN", "YYNNYNNYN", "YNNNYNYNN", "NYYYNNNYN", "NYNNNNNYY", "YNNYNNNYY", "NNYNYYYNY", "NNNNNYYYN"}

    Returns: 4387

  44. {"NYYYNYYNY", "YNYYYNYYY", "YYNYYYYNY", "YYYNYYYYY", "NYYYNYNNY", "YNYYYNNYN", "YYYYNNNYY", "NYNYNYYNN", "YYYYYNYNN"}

    Returns: 256284

  45. {"NYYYYYYYY", "YNNYYYYYY", "YNNYYYYYY", "YYYNYYYYY", "YYYYNYYYY", "YYYYYNYYY", "YYYYYYNNY", "YYYYYYNNY", "YYYYYYYYN"}

    Returns: 2161241

  46. {"NYYYYYYYY", "YNYYYYYYY", "YYNYYYYYY", "YYYNYYYYY", "YYYYNYYYY", "YYYYYNYYY", "YYYYYYNYY", "YYYYYYYNY", "YYYYYYYYN"}

    Returns: 3573369

  47. {"NNNNNYNNYY", "NNYNYNNYYN", "NYNNYNNNNN", "NNNNNNYNYN", "NYYNNNYNNN", "YNNNNNNNNN", "NNNYYNNNNY", "NYNNNNNNYN", "YYNYNNNYNN", "YNNNNNYNNN"}

    Returns: 122

  48. {"NNNYNNNYNY", "NNNYNNNNYN", "NNNNYYYNNY", "YYNNYNNNNN", "NNYYNYYNYY", "NNYNYNYNYN", "NNYNYYNNYN", "YNNNNNNNNN", "NYNNYYYNNN", "YNYNYNNNNN"}

    Returns: 1338

  49. {"NNYNNNYYYN", "NNYNNYNYYN", "YYNNYNYNYY", "NNNNYNYYNN", "NNYYNNYYYN", "NYNNNNYYYY", "YNYYYYNYYY", "YYNYYYYNNN", "YYYNYYYNNY", "NNYNNYYNYN"}

    Returns: 223379

  50. {"NYNYYYYYNN", "YNYNYNYYYY", "NYNNYYYYYN", "YNNNYYNYYY", "YYYYNYNNYY", "YNYYYNYNYY", "YYYNNYNNYY", "YYYYNNNNNN", "NYYYYYYNNY", "NYNYYYYNYN"}

    Returns: 1578509

  51. {"NYYYYYYYYY", "YNYYYYYYYY", "YYNYNYYYYY", "YYYNNYYYYY", "YYNNNYYNYY", "YYYYYNYNYN", "YYYYYYNNYY", "YYYYNNNNYY", "YYYYYYYYNY", "YYYYYNYYYN"}

    Returns: 14634885

  52. {"NYYYYYYYYY", "YNYYYYYYYY", "YYNYYYYYYY", "YYYNYYYYYY", "YYYYNYYYYY", "YYYYYNYYYY", "YYYYYYNYYY", "YYYYYYYNYY", "YYYYYYYYNY", "YYYYYYYYYN"}

    Returns: 63006400

  53. {"NNNNNYYNNNN", "NNYYNNNYNNY", "NYNNNNNYYNY", "NYNNNNYNNYY", "NNNNNNNNNNY", "YNNNNNNNNNN", "YNNYNNNNNNY", "NYYNNNNNYYN", "NNYNNNNYNNN", "NNNYNNNYNNN", "NYYYYNYNNNN"}

    Returns: 198

  54. {"NYNNYYNNYNN", "YNNNYYYYNNN", "NNNYNYYYYYY", "NNYNYYNYYYN", "YYNYNNNNNNN", "YYYYNNNNNNN", "NYYNNNNNYYY", "NYYYNNNNYNY", "YNYYNNYYNYY", "NNYYNNYNYNN", "NNYNNNYYYNN"}

    Returns: 413734

  55. {"NNYNNNNYNYY", "NNYYNYYYNYY", "YYNYNNYNYNN", "NYYNYYYNYNY", "NNNYNNNNNYN", "NYNYNNYYNNY", "NYYYNYNYNNY", "YYNNNYYNNNY", "NNYYNNNNNYN", "YYNNYNNNYNY", "YYNYNYYYNYN"}

    Returns: 465040

  56. {"NYYYYYNYYNY", "YNNNYNYYYNN", "YNNYYYNYYYY", "YNYNNYYYYYY", "YYYNNYYYYYY", "YNYYYNYNYYY", "NYNYYYNYNNY", "YYYYYNYNYNY", "YYYYYYNYNYY", "NNYYYYNNYNN", "YNYYYYYYYNN"}

    Returns: 44324839

  57. {"NYYYYYYYYYY", "YNYYYYNYYYN", "YYNYYYYNYYY", "YYYNYNNYYYY", "YYYYNYYNNYY", "YYYNYNYYYNY", "YNYNYYNYNYY", "YYNYNYYNYYY", "YYYYNYNYNYN", "YYYYYNYYYNY", "YNYYYYYYNYN"}

    Returns: 140573568

  58. {"NYYYYYYYYYY", "YNYYYYYYYYY", "YYNYYYYYYYY", "YYYNYYYYYYY", "YYYYNYYYYYY", "YYYYYNYYYYY", "YYYYYYNYYYY", "YYYYYYYNYYY", "YYYYYYYYNYY", "YYYYYYYYYNY", "YYYYYYYYYYN"}

    Returns: 1222037531

  59. {"NNNNNNYNNNYN", "NNYNNNNNNNNN", "NYNYNNNNNYNN", "NNYNNYYNYNNY", "NNNNNNNNYNNY", "NNNYNNNNNNYN", "YNNYNNNYYNNN", "NNNNNNYNNNNY", "NNNYYNYNNNNN", "NNYNNNNNNNNN", "YNNNNYNNNNNY", "NNNYYNNYNNYN"}

    Returns: 104

  60. {"NYNYYYNYNNYN", "YNNYNYYNNNNN", "NNNNYYYNYYNN", "YYNNNNNYNYNN", "YNYNNNNNNNNN", "YYYNNNYNYNNN", "NYYNNYNNYNYN", "YNNYNNNNNYYN", "NNYNNYYNNYYY", "NNYYNNNYYNNN", "YNNNNNYYYNNY", "NNNNNNNNYNYN"}

    Returns: 230052

  61. {"NNNYNYNYNNNY", "NNYYYNYNYNNY", "NYNYYNNYYYNN", "YYYNYNNNNNYN", "NYYYNYYYYNYN", "YNNNYNNYNNYN", "NYNNYNNYYYNY", "YNYNYYYNNNNN", "NYYNYNYNNYYN", "NNYNNNYNYNNY", "NNNYYYNNYNNY", "YYNNNNYNNYYN"}

    Returns: 3984749

  62. {"NYNYYYNNYYYY", "YNNNYNNYYYYN", "NNNYYNYNYNNY", "YNYNYYYNYYYN", "YYYYNNNNYYYN", "YNNYNNNYNYYY", "NNYYNNNYYYNY", "NYNNNYYNYYYY", "YYYYYNYYNNYY", "YYNYYYYYNNYN", "YYNYYYNYYYNN", "YNYNNYYYYNNN"}

    Returns: 114643353

  63. {"NYYYYYYNYYYY", "YNYYNYYYYYYN", "YYNYYYYYNYYN", "YYYNYYYYYYYY", "YNYYNNYYYYNY", "YYYYNNYNYYYY", "YYYYYYNYYYYY", "NYYYYNYNYYYY", "YYNYYYYYNYYY", "YYYYYYYYYNYY", "YYYYNYYYYYNY", "YNNYYYYYYYYN"}

    Returns: 5528394888

  64. {"NYYYYYYYYYYY", "YNYYYYYYYYYY", "YYNYYYYYYYYY", "YYYNYYYYYYYY", "YYYYNYYYYYYY", "YYYYYNYYYYYY", "YYYYYYNYYYYY", "YYYYYYYNYYYY", "YYYYYYYYNYYY", "YYYYYYYYYNYY", "YYYYYYYYYYNY", "YYYYYYYYYYYN"}

    Returns: 25856693424

  65. {"NNNNYNNNNNNNN", "NNNNNNNNNNYNN", "NNNNNNYNNNYNN", "NNNNNNNNYNNNN", "YNNNNNYNNNNNY", "NNNNNNNNNYYNY", "NNYNYNNNNNYNN", "NNNNNNNNNNNYN", "NNNYNNNNNNNYY", "NNNNNYNNNNNNN", "NYYNNYYNNNNNY", "NNNNNNNYYNNNN", "NNNNYYNNYNYNN"}

    Returns: 6

  66. {"NNNNYYNNNNNNN", "NNNNNNNNYNNYN", "NNNYYNNNNNYYN", "NNYNNNNNYNYNY", "YNYNNNNNYNYNN", "YNNNNNNNYNNNN", "NNNNNNNNNYNNY", "NNNNNNNNYYNNN", "NYNYYYNYNNNNY", "NNNNNNYYNNNYN", "NNYYYNNNNNNNN", "NYYNNNNNNYNNN", "NNNYNNYNYNNNN"}

    Returns: 3458

  67. {"NNYNYYYNNYNYY", "NNNNNNNNYYNNY", "YNNYYNYYNNNNN", "NNYNNNYYNNNNN", "YNYNNYYNYYYYY", "YNNNYNYYNYNNN", "YNYYYYNYNNYYN", "NNYYNYYNNNNYN", "NYNNYNNNNNNYN", "YYNNYYNNNNYNN", "NNNNYNYNNYNNN", "YNNNYNYYYNNNN", "YYNNYNNNNNNNN"}

    Returns: 2153532

  68. {"NYNNNYNNNYYYN", "YNNYYNYNNNYNN", "NNNNYNYYYNNNY", "NYNNNYYNYNYNN", "NYYNNYYNNYNNY", "YNNYYNYNYNNYY", "NYYYYYNYNNYNN", "NNYNNNYNNNYNY", "NNYYNYNNNNNYY", "YNNNYNNNNNNYN", "YYNYNNYYNNNNY", "YNNNNYNNYYNNN", "NNYNYYNYYNYNN"}

    Returns: 9750673

  69. {"NYYNNYYNNNYYY", "YNYYNYNYYYYYY", "YYNNYYYNNNYYY", "NYNNNYYYNNYYN", "NNYNNNYNNYNYN", "YYYYNNNYYNYYY", "YNYYYNNYNYNYY", "NYNYNYYNYYYYN", "NYNNNYNYNNYYN", "NYNNYNYYNNYNN", "YYYYNYNYYYNNY", "YYYYYYYYYNNNY", "YYYNNYYNNNYYN"}

    Returns: 836044794

  70. {"NNYNYYYYYYYYY", "NNYYYNYYYYYYY", "YYNYYNNYYYYYY", "NYYNYYYYNNYYY", "YYYYNYYYYNYYY", "YNNYYNYYNYYYY", "YYNYYYNYYYNYY", "YYYYYYYNYYYYY", "YYYNYNYYNYYYN", "YYYNNYYYYNYYN", "YYYYYYNYYYNYY", "YYYYYYYYYYYNY", "YYYYYYYYNNYYN"}

    Returns: 68776761091

  71. {"NYYYYYYYYYYYY", "YNYYYYYYYYYYY", "YYNYYYYYYYYYY", "YYYNYYYYYYYYY", "YYYYNYYYYYYYY", "YYYYYNYYYYYYY", "YYYYYYNYYYYYY", "YYYYYYYNYYYYY", "YYYYYYYYNYYYY", "YYYYYYYYYNYYY", "YYYYYYYYYYNYY", "YYYYYYYYYYYNY", "YYYYYYYYYYYYN"}

    Returns: 592684459237

  72. {"NNYNNNYYYNNNYN", "NNYYNNNNNNNNNN", "YYNNYNNNNYNNNY", "NYNNNNNNNYNNNY", "NNYNNNNNNYNNNN", "NNNNNNNNNNNYNN", "YNNNNNNNNNNNYN", "YNNNNNNNYYYYNN", "YNNNNNNYNNNNNN", "NNYYYNNYNNYNNN", "NNNNNNNYNYNNNN", "NNNNNYNYNNNNYN", "YNNNNNYNNNNYNN", "NNYYNNNNNNNNNN"}

    Returns: 2814

  73. {"NYYNNNYYYNYYYN", "YNYYNNNYNNYYYN", "YYNNYNYYYYNYYN", "NYNNNYNYYNYNYN", "NNYNNNYNNYYYNN", "NNNYNNYNNNNYYY", "YNYNYYNNNNNNNY", "YYYYNNNNYNNNNY", "YNYYNNNYNNNYNN", "NNYNYNNNNNYNNY", "YYNYYNNNNYNNNN", "YYYNYYNNYNNNNY", "YYYYNYNNNNNNNY", "NNNNNYYYNYNYYN"}

    Returns: 249696578

  74. {"NNNYYYYYNNYNYN", "NNNYYYYNYYNNYN", "NNNYNNYNYYYYNY", "YYYNNYYYYNNNYN", "YYNNNNYYYNNYNY", "YYNYNNYNYNNYYN", "YYYYYYNNYNYNYY", "YNNYYNNNNYYYYY", "NYYYYYYNNYYYYN", "NYYNNNNYYNYNNY", "YNYNNNYYYYNNNN", "NNYNYYNYYNNNNY", "YYNYNYYYYNNNNY", "NNYNYNYYNYNYYN"}

    Returns: 5854958457

  75. {"NNNYYYYNNYYNNY", "NNYNYYYYYNNYYY", "NYNYNYYNYNNYNY", "YNYNYNNNYYNNYY", "YYNYNYYYYYYNYY", "YYYNYNYYYYYYYY", "YYYNYYNYYYYYYN", "NYNNYYYNYYNYYN", "NYYYYYYYNYYYYN", "YNNYYYYYYNYNYN", "YNNNYYYNYYNYYY", "NYYNNYYYYNYNYY", "NYNYYYYYYYYYNN", "YYYYYYNNNNYYNN"}

    Returns: 97997334922

  76. {"NYYYNYYNYYYYYY", "YNYYYYYYYYYYYN", "YYNYNNYYNYYYYY", "YYYNYYNYYNYYYY", "NYNYNYYYYYYYYY", "YYNYYNYYNYYYYY", "YYYNYYNYYYYYYY", "NYYYYYYNYYNYYY", "YYNYYNYYNNNYYY", "YYYNYYYYNNYYYN", "YYYYYYYNNYNYYY", "YYYYYYYYYYYNYY", "YYYYYYYYYYYYNY", "YNYYYYYYYNYYYN"}

    Returns: 1714149550397

  77. {"NYYYYYYYYYYYYY", "YNYYYYYYYYYYYY", "YYNYYYYYYYYYYY", "YYYNYYYYYYYYYY", "YYYYNYYYYYYYYY", "YYYYYNYYYYYYYY", "YYYYYYNYYYYYYY", "YYYYYYYNYYYYYY", "YYYYYYYYNYYYYY", "YYYYYYYYYNYYYY", "YYYYYYYYYYNYYY", "YYYYYYYYYYYNYY", "YYYYYYYYYYYYNY", "YYYYYYYYYYYYYN"}

    Returns: 14630486811136

  78. {"NYNNNYNNNNNNNNN", "YNNNNNNYYYNNNNY", "NNNNNYNNNYNNNNN", "NNNNNNNNYNNNNNN", "NNNNNNNNNYNNNNN", "YNYNNNNNNNYNNYN", "NNNNNNNYYNNNNNN", "NYNNNNYNNNNNNNN", "NYNYNNYNNNNNNNN", "NYYNYNNNNNNYNYN", "NNNNNYNNNNNNYNN", "NNNNNNNNNYNNNNN", "NNNNNNNNNNYNNNN", "NNNNNYNNNYNNNNN", "NYNNNNNNNNNNNNN"}

    Returns: 24

  79. {"NYNNNYNNNYYYNYN", "YNNYNNNNYYYYNNN", "NNNYNNYNNNNNNNN", "NYYNNNNNYNYNNNY", "NNNNNNNNNNYNNNN", "YNNNNNYNYNNYYYN", "NNYNNYNNYYNNYYY", "NNNNNNNNNNNYNNN", "NYNYNYYNNNNNNNY", "YYNNNNYNNNNNNYN", "YYNYYNNNNNNNNNN", "YYNNNYNYNNNNNNN", "NNNNNYYNNNNNNNN", "YNNNNYYNNYNNNNN", "NNNYNNYNYNNNNNN"}

    Returns: 215561

  80. {"NNNNNNNNNYNNNYN", "NNNNNNNYNYYYNNN", "NNNYNYNYNNNNYNY", "NNYNYYYNYNYNYYN", "NNNYNNNNYYYNYNN", "NNYYNNNNNNNNNYN", "NNNYNNNNNNYYYYY", "NYYNNNNNNNNNYYY", "NNNYYNNNNYYNNYY", "YYNNYNNNYNNNYYN", "NYNYYNYNYNNNNNY", "NYNNNNYNNNNNNYN", "NNYYYNYYNYNNNNN", "YNNYNYYYYYNYNNN", "NNYNNNYYYNYNNNN"}

    Returns: 68156131

  81. {"NNNNYNNYYYNYNYY", "NNYNNNNYNYNNNNY", "NYNYNNYYYNYYNYN", "NNYNYYYYYNNYNYN", "YNNYNNNYYYNNYYY", "NNNYNNNNYNYYYYN", "NNYYNNNYYYYYNYY", "YYYYYNYNNYYYYYY", "YNYYYYYNNYYYNYN", "YYNNYNYYYNNYNYY", "NNYNNYYYYNNNYNY", "YNYYNYYYYYNNYYY", "NNNNYYNYNNYYNNN", "YNYYYYYYYYNYNNY", "YYNNYNYYNYYYNYN"}

    Returns: 92716172212

  82. {"NYYYNYYNNNNNNYY", "YNYNYYYYNYNYYYY", "YYNYNYYYNYYYYYY", "YNYNYNYNYYNYYYY", "NYNYNYYYYNNYYYY", "YYYNYNNNNYNYYYY", "YYYYYNNNYYNNYYN", "NYYNYNNNYYYYYYY", "NNNYYNYYNYYYNYN", "NYYYNYYYYNYNNYY", "NNYNNNNYYYNNYYY", "NYYYYYNYYNNNNYY", "NYYYYYYYNNYNNYY", "YYYYYYYYYYYYYNY", "YYYYYYNYNYYYYYN"}

    Returns: 1821737319659

  83. {"NYYYYYYYYYYYYYN", "YNYYYYYYNNYNYNY", "YYNYYYYYYYYYYYY", "YYYNYYYYNYNYNYY", "YYYYNYNYYYYYNYY", "YYYYYNNYYYYYYNY", "YYYYNNNYYNYYYYY", "YYYYYYYNNYYYYYY", "YNYNYYYNNNYNYNY", "YNYYYYNYNNYYYYY", "YYYNYYYYYYNYYYY", "YNYYYYYYNYYNYYY", "YYYNNYYYYYYYNNN", "YNYYYNYYNYYYNNY", "NYYYYYYYYYYYNYN"}

    Returns: 18601340632174

  84. {"NYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYY", "YYNYYYYYYYYYYYY", "YYYNYYYYYYYYYYY", "YYYYNYYYYYYYYYY", "YYYYYNYYYYYYYYY", "YYYYYYNYYYYYYYY", "YYYYYYYNYYYYYYY", "YYYYYYYYNYYYYYY", "YYYYYYYYYNYYYYY", "YYYYYYYYYYNYYYY", "YYYYYYYYYYYNYYY", "YYYYYYYYYYYYNYY", "YYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYN"}

    Returns: 386952126342615

  85. {"NYYNNNNNNNYNNYNN", "YNNNNNNNNYNNNNNN", "YNNYYNNNNNNYNNNN", "NNYNNNNNNNYNNNNN", "NNYNNYNYYNNNNNNN", "NNNNYNNYNYYNNNNN", "NNNNNNNNYYNNYNYN", "NNNNYYNNNNNNNNNY", "NNNNYNYNNYNYNNYN", "NYNNNYYNYNNNNNNN", "YNNYNYNNNNNNYYYY", "NNYNNNNNYNNNNNNY", "NNNNNNYNNNYNNNNN", "YNNNNNNNNNYNNNYN", "NNNNNNYNYNYNNYNN", "NNNNNNNYNNYYNNNN"}

    Returns: 493750

  86. {"NNNYNNNNYYNNYNNN", "NNNYNYNNNYYYYYYY", "NNNNNNNYNNNYYNNY", "YYNNYNYYYNNYYYNN", "NNNYNNNNNYYYYYNY", "NYNNNNYYNNNNYNNN", "NNNYNYNYNNYNNYNY", "NNYYNYYNNYNYNNYN", "YNNYNNNNNNNNNNNN", "YYNNYNNYNNNNNYYN", "NYNNYNYNNNNYNYYY", "NYYYYNNYNNYNYNYY", "YYYYYYNNNNNYNYNY", "NYNYYNYNNYYNYNYN", "NYNNNNNYNYYYNYNN", "NYYNYNYNNNYYYNNN"}

    Returns: 5883761092

  87. {"NYNNYYNYYYNNYNYN", "YNYYNNNNYNNYYNYN", "NYNNYNYNYYNYNNYY", "NYNNYNNNYNYYYNYN", "YNYYNYYYYNYNYNYY", "YNNNYNYNYNNYNNYN", "NNYNYYNNNNYYNYYY", "YNNNYNNNNNYYNYNN", "YYYYYYNNNYYYYYNN", "YNYNNNNNYNNNYNYY", "NNNYYNYYYNNYYYYN", "NYYYNYYYYNYNYYYN", "YYNYYNNNYYYYNYNY", "NNNNNNYYYNYYYNYN", "YYYYYYYNNYYYNYNY", "NNYNYNYNNYNNYNYN"}

    Returns: 570224648988

  88. {"NYNYYNNYYYYYNYYN", "YNNYYYYYYYNYNNNY", "NNNYNYNNYNNYNYYY", "YYYNNNYNYNNNYYNY", "YYNNNYYYYYYYYNYY", "NYYNYNYNYYYYYYYN", "NYNYYYNNNYNYNYYY", "YYNNYNNNYYYYNYYY", "YYYYYYNYNYYYNYYY", "YYNNYYYYYNNYYNYN", "YNNNYYNYYNNYNNYN", "YYYNYYYYYYYNNYYN", "NNNYYYNNNYNNNYNY", "YNYYNYYYYNNYYNNN", "YNYNYYYYYYYYNNNY", "NYYYYNYYYNNNYNYN"}

    Returns: 7616855772895

  89. {"NYYYYYYNYNYYYNYY", "YNYYYYYYNYYNNNNN", "YYNYYYYYYYYYYYYY", "YYYNYYYYYYYYNYYY", "YYYYNYNYYNYYYYNY", "YYYYYNYYYYYYYYYY", "YYYYNYNYYYYYYYYY", "NYYYYYYNYYYYYYYY", "YNYYYYYYNYNYNYYY", "NYYYNYYYYNYYYYNY", "YYYYYYYYNYNYYYYY", "YNYYYYYYYYYNYYYY", "YNYNYYYYNYYYNYNY", "NNYYYYYYYYYYYNYY", "YNYYNYYYYNYYNYNY", "YNYYYYYYYYYYYYYN"}

    Returns: 890976670310632

  90. {"NYYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYYY", "YYNYYYYYYYYYYYYY", "YYYNYYYYYYYYYYYY", "YYYYNYYYYYYYYYYY", "YYYYYNYYYYYYYYYY", "YYYYYYNYYYYYYYYY", "YYYYYYYNYYYYYYYY", "YYYYYYYYNYYYYYYY", "YYYYYYYYYNYYYYYY", "YYYYYYYYYYNYYYYY", "YYYYYYYYYYYNYYYY", "YYYYYYYYYYYYNYYY", "YYYYYYYYYYYYYNYY", "YYYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYYN"}

    Returns: 10916525199478336

  91. {"NYYNNYNNNNNNNNNY", "YNNNYNYNYNNYNNNY", "YNNNNNNYNNNNNNNN", "NNNNNNYNNNYYNNNN", "NYNNNNNNYNNYYNYY", "YNNNNNNNNYNNNNNN", "NYNYNNNNNNNNYNNN", "NNYNNNNNNNNNNNNN", "NYNNYNNNNNNNYYNN", "NNNNNYNNNNNNNNNN", "NNNYNNNNNNNNNYYN", "NYNYYNNNNNNNNYYY", "NNNNYNYNYNNNNNNY", "NNNNNNNNYNYYNNNN", "NNNNYNNNNNYYNNNN", "YYNNYNNNNNNYYNNN"}

    Returns: 0

  92. {"NYYNYNYNYNYNNYYN", "YNYNYNYNNYNYNYNY", "YYNNNNYYNYNYNNNN", "NNNNYNNNNNNNNNYN", "YYNYNYNYYYNNNNNN", "NNNNYNNYYNNYNNNN", "YYYNNNNNYNYNYNNY", "NNYNYYNNNNYNNYNY", "YNNNYYYNNNNNYYYN", "NYYNYNNNNNNNYNNY", "YNNNNNYYNNNNNNNN", "NYYNNYNNNNNNNYYY", "NNNNNNYNYYNNNYNY", "YYNNNNNYYNNYYNNY", "YNNYNNNNYNNYNNNN", "NYNNNNYYNYNYYYNN"}

    Returns: 948129080

  93. {"NYNYYYNYNYYNNYNN", "YNYNNNYYNNYNYNYN", "NYNYNNNNYNYYNNYY", "YNYNYNNNYYNYYNNN", "YNNYNNYYNNNNYYNY", "YNNNNNYNNNYYNYYY", "NYNNYYNNNYYYYYYY", "YYNNYNNNYNYNNYYN", "NNYYNNNYNYNYYYYY", "YNNYNNYNYNNNYYNN", "YYYNNYYYNNNNYNNY", "NNYYNYYNYNNNYNNY", "NYNYYNYNYYYYNYYN", "YNNNYYYYYYNNYNYY", "NYYNNYYYYNNNYYNY", "NNYNYYYNYNYYNYYN"}

    Returns: 474149861908

  94. {"NNNYYNNNYYYYNYYY", "NNNYYYYYNYNYYYYY", "NNNYYNNYYYYYYYYY", "YYYNYNYNNNYYYYYY", "YYYYNYNYNYYYYNYY", "NYNNYNYNNNNYYNNN", "NYNYNYNNYNNYYNNN", "NYYNYNNNNNYYNYYY", "YNYNNNYNNYYNNYNY", "YYYNYNNNYNYYYYYN", "YNYYYNNYYYNYYYNY", "YYYYYYYYNYYNYYNY", "NYYYYYYNNYYYNYYY", "YYYYNNNYYYYYYNYN", "YYYYYNNYNYNNYYNN", "YYYYYNNYYNYYYNNN"}

    Returns: 7757561934711

  95. {"NNYYYYNYYYYYNNYY", "NNYYNYYYYYYYYYYY", "YYNNYYNYYNYYYYYY", "YYNNNYYYYYYYYYYY", "YNYNNYYYYYYYNYYY", "YYYYYNYYYYYYNYNY", "NYNYYYNYYYYYYYYY", "YYYYYYYNYYYYYYYY", "YYYYYYYYNNNYYYYY", "YYNYYYYYNNYYNYNY", "YYYYYYYYNYNYYYYY", "YYYYYYYYYYYNYYYN", "NYYYNNYYYNYYNYYY", "NYYYYYYYYYYYYNNY", "YYYYYNYYYNYYYNNY", "YYYYYYYYYYYNYYYN"}

    Returns: 823431519551531

  96. {"NNYNNYNNNYYNNNNN", "NNYNNYNNYNNYNNYN", "YYNNNNNNNNNYNYNN", "NNNNNNYYYNNNNNYN", "NNNNNNYNYNNNNNNN", "YYNNNNNNYNNNYNNN", "NNNYYNNNYNNNNYNN", "NNNYNNNNNNNYNNNN", "NYNYYYYNNYNNNYNY", "YNNNNNNNYNNYNYNY", "YNNNNNNNNNNYNNNY", "NYYNNNNYNYYNYYNN", "NNNNNYNNNNNYNYNN", "NNYNNNYNYYNYYNYN", "NYNYNNNNNNNNNYNN", "NNNNNNNNYYYNNNNN"}

    Returns: 4606260

  97. {"NNNNNNNNNNYNNNNN", "NNYNNNNYYNNYYNYN", "NYNNYYYNNNYNNYNN", "NNNNNNYNNNNNYNNN", "NNYNNNYYYYNNYNYY", "NNYNNNYYYNNYNYNN", "NNYYYYNNYNYYNNYN", "NYNNYYNNYYYYNYNN", "NYNNYYYYNNNNNNYY", "NNNNYNNYNNYNNYYN", "YNYNNNYYNYNNNNNY", "NYNNNYYYNNNNNYNY", "NYNYYNNNNNNNNYNY", "NNYNNYNYNYNYYNNY", "NYNNYNYNYYNNNNNN", "NNNNYNNNYNYYYYNN"}

    Returns: 508257463

  98. {"NNYYYYNNNYYNYNYN", "NNYYYYNYYNNNNNNN", "YYNYNYYNYYNYYYNN", "YYYNNYYNNYYYNYYY", "YYNNNYNYYNYYNNNY", "YYYYYNYYNYYNNYNY", "NNYYNYNNNNNYNYNY", "NYNNYYNNNYYNNNYN", "NYYNYNNNNYYYNNYN", "YNYYNYNYYNYYNYNY", "YNNYYYNYYYNNNNYY", "NNYYYNYNYYNNNYNN", "YNYNNNNNNNNNNYYY", "NNYYNYYNNYNYYNYY", "YNNYNNNYYNYNYYNN", "NNNYYYYNNYYNYYNN"}

    Returns: 365389539282

  99. {"NYNYYYYYYYYNYYYN", "YNNYNYYNYYNYYYYY", "NNNNYYYYNYYYYYYN", "YYNNYYNYNNYNYYYY", "YNYYNYYYYNYYYYYY", "YYYYYNYNYYYNYYYY", "YYYNYYNNYNYYNYNN", "YNYYYNNNYYYYYYNN", "YYNNYYYYNYYYYNYY", "YYYNNYNYYNYYNYYY", "YNYYYYYYYYNNYYYN", "NYYNYNYYYYNNYNYY", "YYYYYYNYYNYYNYYY", "YYYYYYYYNYYNYNYY", "YYYYYYNNYYYYYYNY", "NYNYYYNNYYNYYYYN"}

    Returns: 131315472847517

  100. {"NNYYYYNNYYNYYYYY", "NNYNNYYYYYYYYYYY", "YYNYYYYYNYYYYYNY", "YNYNYYYYYYYNYYYY", "YNYYNYYYYYNYYYYY", "YYYYYNYNNYYYYYYY", "NYYYYYNNYYYYYNYY", "NYYYYNNNYYYNNYYY", "YYNYYNYYNYYYYYYY", "YYYYYYYYYNYYYYYY", "NYYYNYYYYYNYYYNN", "YYYNYYYNYYYNYYYY", "YYYYYYYNYYYYNNYY", "YYYYYYNYYYYYNNYN", "YYNYYYYYYYNYYYNY", "YYYYYYYYYYNYYNYN"}

    Returns: 604438324369952

  101. {"NYNNYNNYNNNNNYNN", "YNYNYNNNYNYNYNNN", "NYNNNNNNYNNYNNYY", "NNNNNNNNNYNNNNNY", "YYNNNNNNYNNNNNNN", "NNNNNNNNYNYYNYYN", "NNNNNNNNNYNNNYNN", "YNNNNNNNNNNNNNNY", "NYYNYYNNNYNNNYYY", "NNNYNNYNYNNNNNNN", "NYNNNYNNNNNNNNYN", "NNYNNYNNNNNNNNNY", "NYNNNNNNNNNNNNNN", "YNNNNYYNYNNNNNNY", "NNYNNYNNYNYNNNNY", "NNYYNNNYYNNYNYYN"}

    Returns: 674833

  102. {"NNNNNNNYNYNNYNNY", "NNYNYNNYYNNYNYYN", "NYNNNYNYNYYNNNNY", "NNNNNNNYNYNNYNNN", "NYNNNNYNNNYNYNNN", "NNYNNNNYYYYYYYYN", "NNNNYNNNNNYNYYYN", "YYYYNYNNNNYYNNNN", "NYNNNYNNNNYNNYYN", "YNYYNYNNNNNNNNNN", "NNYNYYYYYNNNYNYY", "NYNNNYNYNNNNNYYN", "YNNYYYYNNNYNNNNN", "NYNNNYYNYNNYNNNY", "NYNNNYYNYNYYNNNY", "YNYNNNNNNNYNNYYN"}

    Returns: 1268387034

  103. {"NNYYNYYNNNNNYYNY", "NNNNYNYYYYYNNNYN", "YNNYYNNYYYYYYYNY", "YNYNYYNNYNYNYYNY", "NYYYNNYNNNNYYYNN", "YNNYNNNNYYNYNNNY", "YYNNYNNNYYNYNYYN", "NYYNNNNNYNYNYYNY", "NYYYNYYYNYNYYYNN", "NYYNNYYNYNNYNYYY", "NYYYNNNYNNNYNYYN", "NNYNYYYNYYYNNNYN", "YNYYYNNYYNNNNNYN", "YNYYYNYYYYYNNNNY", "NYNNNNYNNYYYYNNN", "YNYYNYNYNYNNNYNN"}

    Returns: 332382840547

  104. {"NNYYYNYYNYNYYYYN", "NNYNYNYYYYNYYYYY", "YYNYYYYNYNNYNYYY", "YNYNYYYYYYNYNYYY", "YYYYNYYYYNYYYYNY", "NNYYYNYYYYNNYYYN", "YYYYYYNYYYYYNYYY", "YYNYYYYNNYYYNYYY", "NYYYYYYNNYYNYNYN", "YYNYNYYYYNYYYYYY", "NNNNYNYYYYNNNYYN", "YYYYYNYYNYNNNYYN", "YYNNYYNNYYNNNNNN", "YYYYYYYYNYYYNNYY", "YYYYNYYYYYYYNYNY", "NYYYYNYYNYNNNYYN"}

    Returns: 50946758510424

  105. {"NYYYNYNYYYNYYYYY", "YNYYYYYYYYYYYYYY", "YYNNYYYYYNNYYYYN", "YYNNNYYYYYYYYYYY", "NYYNNYYYYYYYYYYY", "YYYYYNYYYNYNNYYY", "NYYYYYNYYYNYYYNY", "YYYYYYYNYYYYYYNY", "YYYYYYYYNYYNYNYY", "YYNYYNYYYNYYYYYY", "NYNYYYNYYYNYYYYN", "YYYYYNYYNYYNNYYY", "YYYYYNYYYYYNNYYY", "YYYYYYYYNYYYYNYY", "YYYYYYNNYYYYYYNY", "YYNYYYYYYYNYYYYN"}

    Returns: 833935745424746

  106. {"NY", "YN" }

    Returns: 1

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: