Statistics

Problem Statement for "Sunnygraphs"

Problem Statement

Hero has just constructed a very specific graph. He started with n isolated vertices, labeled 0 through n-1. For each vertex i Hero then chose a vertex a[i] (other than i) and he added an edge that connected i and a[i]. This way he created a graph with n vertices and n edges. Note that if a[x]=y and a[y]=x, the vertices x and y were connected by two different edges. Hero now wants to perform the following procedure:
  1. Add a new isolated vertex number n.
  2. Choose a subset M of the original vertices.
  3. For each x in M, erase an edge between vertices x and a[x].
  4. For each x in M, add a new edge between vertices x and n.
Hero's goal is to create a final graph in which the vertices 0 and 1 are in the same connected component. (I.e., there is a path from one of them to the other.) In step 2 of the above procedure Hero has 2^n possible subsets to choose from. A choice of M is good if it produces a graph with the desired property. Count how many of the 2^n possibilities are good choices. Return that count as a long.

Definition

Class:
Sunnygraphs
Method:
count
Parameters:
int[]
Returns:
long
Method signature:
long count(int[] a)
(be sure your method is public)

Constraints

  • a will contain n elements.
  • n will be between 2 and 50, inclusive.
  • Each element in a will be between 0 and n - 1, inclusive.
  • For each i between 0 and n - 1 holds a[i] != i.

Examples

  1. {1,0}

    Returns: 4

    The original graph contained the vertices 0 and 1. This pair of vertices was connected by two edges. Next, Hero added a new vertex 2. Then he had to choose one of four possible subsets M: If he chose M = {}, the resulting graph contained the edges 0-1 and 0-1. The vertices 0 and 1 were connected. If he chose M = {0}, the resulting graph contained the edges 0-1 and 0-2. The vertices 0 and 1 were connected. If he chose M = {1}, the resulting graph contained the edges 0-1 and 1-2. The vertices 0 and 1 were connected. Finally, if he chose M = {0, 1}, the resulting graph contained the edges 0-2 and 1-2. And again, the vertices 0 and 1 were connected: there is a path 0-1-2. As all four choices of M are good, the correct answer is 4.

  2. {2,2,0}

    Returns: 7

    Here, the original graph contained the edges 0-2, 0-2, and 1-2. For this graph M = {1} is not a good choice. This choice produces a graph with edges 0-2, 0-2, and 1-3. In this graph the vertices 0 and 1 are not in the same connected component. The other seven possible choices of M are all good.

  3. {2,3,0,1}

    Returns: 9

  4. {2,2,3,4,3}

    Returns: 30

  5. {29,34,40,17,16,12,0,40,20,35,5,13,27,7,29,13,14,39,42,9,30,38,27,40,34,33,42,20,29,42,12,29,30,21,4,5,7,25,24,17,39,32,9}

    Returns: 8787503087616

    Watch out for integer overflow.

  6. {6,11,27,33,0,13,2,22,15,11,7,19,17,23,30,8,9,22,6,16,16,30,0,20,4,8,5,12,31,26,16,12,25,15,12}

    Returns: 33025949696

  7. {23,24,4,6,20,16,26,11,28,24,9,26,13,17,28,8,12,9,11,3,5,19,18,24,0,27,30,23,6,11,5}

    Returns: 2013265920

  8. {16,6,21,17,21,9,0,10,18,17,12,24,23,15,22,23,4,14,22,21,4,22,24,3,23}

    Returns: 33529856

  9. {12,7,12,25,8,20,9,9,25,21,13,22,21,6,5,13,18,0,16,12,5,10,9,24,12,23}

    Returns: 66322432

  10. {11,9,16,14,3,4,14,12,4,5,4,15,4,4,9,14,5}

    Returns: 129024

  11. {18,18,20,28,7,27,8,13,40,3,7,21,30,17,13,34,29,16,15,11,0,9,39,36,38,23,24,8,4,9,29,22,35,5,13,23,3,27,34,23,8}

    Returns: 2198754820096

  12. {3,3,0,11,8,11,14,8,4,7,12,12,13,7,8,14}

    Returns: 65280

  13. {5,2,11,12,12,4,3,2,6,8,3,0,2}

    Returns: 8128

  14. {1,0}

    Returns: 4

  15. {7,10,14,2,13,8,4,3,11,1,1,0,4,1,7}

    Returns: 23808

  16. {27,30,16,23,5,25,9,24,3,24,11,14,2,24,25,23,4,11,5,25,15,15,31,15,12,19,12,17,4,15,24,26}

    Returns: 4257480704

  17. {9,2,0,43,12,14,39,25,24,3,16,17,22,0,6,21,18,29,34,35,23,43,28,28,20,11,5,12,31,24,8,13,17,10,15,9,15,26,4,13,21,27,36,39}

    Returns: 17386027614208

  18. {1,0,0,2,1}

    Returns: 32

  19. {3,2,1,2,2,6,0}

    Returns: 104

  20. {27,14,25,17,18,1,20,19,29,8,22,29,24,16,7,25,23,0,0,6,5,14,15,6,12,4,1,29,5,22}

    Returns: 1061191680

  21. {15,19,18,22,6,10,15,0,10,19,15,6,7,22,7,3,10,1,8,15,13,5,20}

    Returns: 8257536

  22. {7,13,5,13,12,10,8,12,9,12,1,1,8,9}

    Returns: 15616

  23. {11,16,15,0,0,11,5,6,12,14,7,8,3,16,0,14,2}

    Returns: 127104

  24. {16,2,37,12,22,17,4,33,20,25,31,30,16,15,1,38,34,35,21,2,31,39,27,0,4,4,3,16,15,5,12,4,13,26,39,11,38,25,6,26}

    Returns: 1090921693184

  25. {3,3,3,4,0,0,10,4,12,3,13,13,11,14,2}

    Returns: 30720

  26. {44,44,19,44,19,38,5,36,1,46,48,13,47,5,0,42,7,47,40,13,48,45,20,41,7,48,2,12,12,33,24,13,12,7,0,19,4,24,22,7,37,12,32,42,45,30,13,9,39}

    Returns: 562941363486720

  27. {3,2,7,0,7,7,7,0}

    Returns: 200

  28. {7,32,5,21,31,4,24,31,21,2,0,6,30,12,17,1,4,19,15,32,15,19,19,0,3,10,15,30,10,15,21,15,19}

    Returns: 7583301632

  29. {23,8,27,32,34,37,21,4,10,3,25,20,38,14,18,4,36,4,20,18,8,27,39,27,4,12,38,35,38,28,27,35,36,35,21,37,17,31,17,26}

    Returns: 1082298204160

  30. {10,27,22,2,5,29,11,0,28,5,30,27,9,10,25,3,24,21,10,24,8,5,29,2,15,4,1,3,19,15,28}

    Returns: 2130182144

  31. {37,29,36,1,27,27,21,9,0,13,14,1,37,15,3,13,32,24,1,32,39,30,28,27,4,35,40,18,10,7,7,4,23,21,23,26,3,10,11,9,0}

    Returns: 2165737259008

  32. {10,13,9,12,9,7,2,9,11,13,5,4,8,12}

    Returns: 16256

  33. {3,13,1,17,17,27,26,11,23,21,14,7,14,26,20,14,3,18,25,20,22,6,16,0,18,10,17,4}

    Returns: 268173312

  34. {3,4,3,4,3}

    Returns: 28

  35. {33,29,15,28,9,2,16,20,20,24,8,17,19,34,20,16,18,20,19,21,37,12,24,31,4,7,16,8,20,22,26,16,36,15,8,11,25,13}

    Returns: 269525975040

  36. {3,19,17,6,20,15,18,6,11,5,15,1,9,16,4,20,4,2,15,13,2}

    Returns: 2081280

  37. {3,25,32,20,33,9,31,6,1,13,4,30,32,31,18,2,25,21,6,33,11,16,33,2,27,9,14,21,6,31,0,28,22,0}

    Returns: 16512974848

  38. {18,28,21,24,12,8,10,1,22,7,2,28,4,8,8,25,13,5,4,24,24,10,2,26,19,1,4,3,8}

    Returns: 499384320

  39. {29,22,9,25,36,34,21,2,12,26,11,39,25,38,3,0,11,19,3,9,37,8,8,45,17,26,21,2,34,48,26,21,42,28,25,23,13,27,21,25,21,10,12,3,8,48,39,27,39}

    Returns: 558002151096320

  40. {4,2,3,2,5,0}

    Returns: 49

  41. {31,24,31,16,13,7,31,29,16,26,6,29,19,15,25,12,10,9,5,16,7,12,28,5,28,6,22,4,29,15,14,33,17,6}

    Returns: 16106127360

  42. {25,25,4,0,23,9,18,11,5,16,24,17,3,4,25,21,5,1,16,16,1,16,12,6,14,15}

    Returns: 66584576

  43. {3,3,0,1}

    Returns: 14

  44. {7,6,1,4,5,1,2,8,3}

    Returns: 449

  45. {3,3,5,2,2,1}

    Returns: 62

  46. {16,32,24,13,25,27,14,8,32,13,31,1,23,17,0,17,33,18,5,5,5,4,32,29,33,21,22,23,0,9,4,26,7,10}

    Returns: 16106127360

  47. {8,8,7,6,2,2,10,12,13,2,12,3,5,12,5,3}

    Returns: 65024

  48. {16,0,10,12,19,15,2,15,16,13,2,1,4,3,8,14,9,5,10,13,16,20,16,3,10}

    Returns: 33488896

  49. {5,12,14,8,18,19,17,36,11,30,19,12,21,23,16,7,15,14,13,12,8,26,18,24,4,26,30,36,18,21,36,20,39,29,3,34,7,30,30,31}

    Returns: 1090921693184

  50. {38,21,23,29,41,12,0,19,40,5,7,24,23,11,33,9,5,34,35,36,5,24,28,17,3,23,0,0,16,14,35,14,30,41,0,21,3,16,26,35,23,1}

    Returns: 3833258311680

  51. {3,0,0,0}

    Returns: 14

  52. {1,4,0,6,7,4,2,6,6}

    Returns: 512

  53. {1,3,3,0}

    Returns: 16

  54. {5,4,4,4,2,10,0,4,2,1,2}

    Returns: 1792

  55. {12,4,12,4,6,8,3,13,11,5,6,12,14,3,15,1,12,7,8,9}

    Returns: 987136

  56. {23,10,37,7,27,16,3,32,31,48,3,31,14,29,6,17,23,6,7,29,24,16,47,32,48,17,27,8,45,38,42,37,7,12,18,28,44,30,37,46,30,2,39,3,41,21,34,26,44,15}

    Returns: 1037938976620544

  57. {3,5,12,1,22,13,10,15,21,17,17,6,4,21,0,11,22,2,7,21,9,5,3}

    Returns: 7995392

  58. {22,45,10,35,38,7,7,12,14,44,29,18,46,34,28,33,31,4,6,24,10,8,29,13,30,40,25,4,11,2,22,37,27,42,16,9,7,31,10,13,38,25,15,2,34,1,45,2}

    Returns: 204509162766336

  59. {22,42,21,47,20,23,22,1,43,29,11,2,42,9,8,34,32,0,20,1,32,46,7,34,31,29,4,14,32,24,41,44,2,32,36,31,8,31,8,0,41,11,1,31,9,48,20,36,24}

    Returns: 439804651110400

  60. {15,12,13,11,2,0,0,11,5,14,6,7,0,10,5,17,7,5,12}

    Returns: 499712

  61. {28,37,36,30,39,40,42,40,34,40,40,36,27,25,4,23,24,11,7,28,33,0,32,11,1,35,12,33,44,33,29,24,29,9,27,30,8,22,45,42,8,25,27,21,14,42}

    Returns: 70326331375616

  62. {19,14,17,8,3,1,17,1,11,5,14,19,19,3,13,0,17,15,15,6}

    Returns: 1016320

  63. {32,23,4,4,25,14,30,25,18,13,31,6,9,29,31,24,36,18,26,7,2,1,6,3,5,33,7,14,16,33,19,12,13,36,0,16,11}

    Returns: 137376038912

  64. {34,8,15,31,13,2,28,11,26,24,6,17,37,29,36,34,31,29,32,26,13,11,15,29,17,0,12,36,31,7,26,2,35,23,40,20,17,25,25,33,21}

    Returns: 2190567538688

  65. {24,32,25,48,10,30,13,45,44,0,42,37,29,21,20,28,11,39,7,49,47,16,27,46,31,17,33,6,2,5,36,19,18,3,41,15,8,34,43,38,22,14,12,4,26,35,9,23,40,1}

    Returns: 1125899906842624

  66. {1,2,0,2,3,3,2,6,6,2,3,4,2,4,7,0,7,3,7,9,1,6,5,16,9,18,1,17,8,26,2,7,8,13,11,30,21,5,20,37,35,1,13,3,20,32,17,1,44,23}

    Returns: 1125899906842624

  67. {1,0,0,2,3,4,5,6,0,2,0,5,9,3,11,3,2,2,10,4,18,20,3,14,21,14,13,18,21,24,28,28,13,26,10,11,19,29,15,38,0,15,26,4,5,10,35,35,40,1}

    Returns: 1125899906842624

  68. {9,10,15,16,11,2,7,3,12,8,13,5,6,0,4,1,14,10,15,8,8,1,13,15,12,2,7,24,21,21,9,5,27,13,15,0,25,12,4,3,33,15,3,37,42,2,16,18,42,13}

    Returns: 1125899906842624

  69. {10,9,3,5,0,6,7,11,12,13,8,4,15,14,2,1,15,9,4,11,5,14,21,5,1,24,17,0,22,23,0,11,13,20,17,26,13,20,5,31,34,38,7,40,39,30,43,40,17,26}

    Returns: 1125899906842624

  70. {1,0,0,1,1,0,2,5,4,4,6,0,4,6,5,0,6,0,7,7,1,3,15,22,13,10,18,22,19,28,24,21,29,3,11,25,3,27,9,18,12,10,16,16,0,31,36,35,6,8}

    Returns: 1125899906842624

  71. {1, 0 }

    Returns: 4

  72. {2, 3, 0, 1, 5, 4, 7, 6, 9, 8 }

    Returns: 576

  73. {2, 3, 0, 1, 5, 4 }

    Returns: 36

  74. {9, 3, 8, 0, 2, 4, 8, 3, 9, 0 }

    Returns: 832

  75. {2, 7, 5, 2, 3, 4, 3, 6, 9, 8 }

    Returns: 992

  76. {2, 3, 1, 4, 3, 6, 5 }

    Returns: 116

  77. {2, 21, 4, 11, 42, 10, 15, 37, 39, 4, 45, 45, 34, 26, 30, 18, 35, 33, 6, 12, 41, 49, 11, 37, 34, 14, 9, 38, 6, 44, 17, 17, 47, 42, 4, 40, 13, 8, 46, 9, 27, 31, 36, 8, 10, 43, 30, 45, 16, 30 }

    Returns: 1121364421378048

  78. {4, 5, 0, 1, 0, 1 }

    Returns: 36

  79. {2, 4, 3, 2, 5, 4, 7, 6 }

    Returns: 196

  80. {9, 6, 6, 8, 7, 3, 4, 8, 2, 8 }

    Returns: 1008

  81. {27, 15, 16, 8, 0, 15, 38, 3, 26, 20, 22, 0, 43, 34, 5, 48, 42, 35, 46, 11, 8, 28, 36, 11, 11, 19, 36, 28, 35, 46, 35, 6, 42, 17, 39, 11, 7, 38, 15, 43, 28, 45, 35, 8, 1, 5, 38, 23, 21, 23 }

    Returns: 1092914558009344

  82. {1, 0, 1, 1 }

    Returns: 16

  83. {6, 3, 4, 6, 5, 11, 11, 11, 0, 0, 7, 4, 2, 0 }

    Returns: 15872

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: