Statistics

Problem Statement for "PolygonColors"

Problem Statement

Consider a regular polygon with N sides. A diagonal is defined to be a line segment drawn that connects two non-adjacent vertices of the polygon (with the two vertices as its endpoints). A set of diagonals is said to be safe if no two diagonals cross one another, except for possibly at the polygon's vertices.

A coloring of a polygon is a mapping of the non-negative integers, or colors, to the vertices of the polygon. Given a set of safe diagonals, a valid coloring of a polygon is a coloring of the polygon such that no two vertices which are connected by a diagonal or share a side have the same color.

Two diagonals are distinct if at least one of their endpoints is different, and two sets of diagonals are distinct if one set contains some diagonal not contained in the other.

You're given a coloring of a polygon with N sides, where the coloring is given by a int[] colors and N is described by a int. Here, the ith element of colors is the color of the ith vertex. Return how many distinct sets of safe diagonals may be assigned to the polygon such that the coloring is valid. As this result may be very large, return the answer modulo 100000007.

Definition

Class:
PolygonColors
Method:
getWays
Parameters:
int, int[]
Returns:
int
Method signature:
int getWays(int N, int[] colors)
(be sure your method is public)

Constraints

  • N will be between 3 and 50, inclusive.
  • colors will have exactly N elements.
  • Each element of colors will be between 0 and N-1, inclusive.

Examples

  1. 3

    {1, 2, 0}

    Returns: 1

    There are no diagonals we can add to a triangle, so the empty set is the only possibility.

  2. 4

    {1, 2, 3, 0}

    Returns: 3

    We can either add 0 or 1 diagonals, and there are two ways to add a diagonal.

  3. 4

    {0, 1, 0, 1}

    Returns: 1

    We can't add any diagonals here.

  4. 5

    {0, 1, 1, 1, 1}

    Returns: 0

    Here we have vertices that share sides, but have the same color. Even if we choose not to add any diagonals, there are no safe sets here.

  5. 4

    {0, 0, 0, 1}

    Returns: 0

  6. 5

    {0,1,2,3,4}

    Returns: 11

  7. 50

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

    Returns: 34248574

  8. 4

    {1,0,1,0}

    Returns: 1

  9. 33

    {6,16,4,14,3,11,20,8,1,14,9,5,31,10,16,0,9,0,0,26,27,14,6,9,11,6,4,21,16,30,19,19,26}

    Returns: 0

  10. 35

    {14,22,15,0,21,14,33,1,33,26,19,34,4,31,3,29,30,11,0,4,0,8,30,14,21,18,16,19,15,32,11,13,32,5,6}

    Returns: 72589011

  11. 12

    {7,1,2,4,2,9,3,10,8,3,11,0}

    Returns: 366268

  12. 9

    {6,2,5,8,5,7,2,0,1}

    Returns: 3002

  13. 12

    {4,9,11,4,1,7,10,1,11,3,11,5}

    Returns: 269640

  14. 49

    {40,18,30,13,10,48,21,29,20,22,4,40,9,21,46,3,40,21,5,46,19,34,23,19,36,20,25,26,39,21,15,14,27,5,41,16,1,14,24,38,20,40,32,40,37,13,41,33,25}

    Returns: 92301720

  15. 48

    {42,29,18,22,6,16,10,44,25,1,32,15,20,38,44,2,17,46,21,10,26,30,23,6,45,39,28,13,11,0,33,4,40,12,25,28,45,0,24,34,20,10,40,12,5,36,9,3}

    Returns: 85640278

  16. 5

    {4,3,4,0,4}

    Returns: 0

  17. 30

    {24,7,25,13,4,2,6,13,18,9,25,2,5,14,19,28,5,7,26,12,3,8,0,10,16,0,28,24,19,24}

    Returns: 0

  18. 10

    {2,9,6,8,1,6,3,4,8,0}

    Returns: 16059

  19. 31

    {8,26,10,18,2,22,18,27,4,11,2,14,8,10,16,18,8,30,5,1,11,16,15,27,4,6,24,7,11,16,1}

    Returns: 97638588

  20. 16

    {0,1,2,6,4,5,6,7,1,9,10,11,12,13,14,10}

    Returns: 96791474

  21. 33

    {0,27,13,0,22,17,25,10,16,32,9,10,18,3,22,9,2,24,18,14,7,4,15,5,12,28,0,14,6,19,2,11,30}

    Returns: 64030619

  22. 35

    {15,31,20,24,25,20,28,22,28,17,20,31,30,27,26,6,32,7,34,3,1,21,1,15,8,23,31,5,16,6,23,26,2,16,18}

    Returns: 77919775

  23. 20

    {16,19,4,13,18,17,5,8,19,5,10,6,0,1,3,5,11,8,5,16}

    Returns: 0

  24. 19

    {18,2,5,13,16,0,11,17,11,5,17,2,12,10,8,4,1,11,7}

    Returns: 43756738

  25. 42

    {32,13,22,30,39,14,12,15,0,25,1,3,22,10,32,34,26,17,1,32,30,18,5,35,38,24,0,4,17,24,17,6,40,20,0,17,13,3,34,31,10,12}

    Returns: 65373672

  26. 29

    {19,2,11,8,11,2,21,23,20,9,7,9,14,0,21,7,15,18,10,13,4,1,0,13,26,15,16,11,3}

    Returns: 58515592

  27. 9

    {4,5,7,3,5,8,5,0,1}

    Returns: 2612

  28. 31

    {18,13,8,5,10,13,11,22,10,0,18,22,17,2,29,24,22,16,11,25,30,11,17,19,10,28,20,26,1,23,25}

    Returns: 37280404

  29. 21

    {20,3,18,4,7,9,5,1,15,8,3,6,10,16,14,8,12,18,8,12,15}

    Returns: 21268930

  30. 44

    {1,27,3,31,3,11,6,34,0,43,18,35,29,25,9,20,22,33,43,1,26,19,40,11,16,31,22,20,23,34,32,34,1,9,28,21,9,24,33,15,11,26,34,40}

    Returns: 74758197

  31. 20

    {0,6,3,4,3,14,13,8,15,5,8,16,2,13,8,9,6,0,14,6}

    Returns: 1716511

  32. 48

    {24,1,23,12,44,37,19,47,29,46,44,23,5,16,34,13,26,12,16,45,17,34,27,36,7,21,31,20,44,8,9,31,11,16,32,18,15,45,34,24,2,10,41,14,29,24,32,18}

    Returns: 6248512

  33. 21

    {20,1,13,2,18,12,2,18,13,3,16,3,16,0,19,18,12,6,7,3,9}

    Returns: 56866335

  34. 34

    {20,28,10,20,17,4,10,18,2,11,20,28,18,19,27,7,19,20,27,9,29,24,12,13,20,12,29,31,11,3,30,20,26,23}

    Returns: 17435211

  35. 23

    {20,3,9,1,8,5,15,17,18,20,0,18,19,16,0,6,21,19,14,0,15,21,18}

    Returns: 84494550

  36. 37

    {19,30,11,9,21,8,32,33,27,35,31,7,0,21,15,32,5,13,22,3,5,18,23,3,25,9,18,26,1,7,31,17,35,23,13,36,29}

    Returns: 89015864

  37. 44

    {29,23,14,26,7,18,19,8,36,2,20,41,32,36,10,30,16,27,29,28,30,39,8,32,43,41,0,37,27,36,6,7,6,18,35,0,14,30,21,36,27,11,29,22}

    Returns: 61568834

  38. 28

    {25,3,14,10,5,21,27,12,13,10,0,2,3,13,17,26,1,13,2,8,27,13,5,6,24,18,5,23}

    Returns: 98287997

  39. 37

    {23,5,27,13,34,15,14,25,32,19,11,18,6,13,14,17,21,36,0,21,6,13,25,1,15,4,11,1,22,21,7,27,26,21,32,33,17}

    Returns: 21369320

  40. 37

    {22,11,3,20,8,33,7,24,28,20,13,24,35,27,23,34,35,9,14,18,15,11,0,35,29,1,21,10,8,26,25,10,30,35,8,1,22}

    Returns: 0

  41. 36

    {20,18,32,11,5,12,5,1,33,20,25,5,8,26,7,15,8,30,32,21,6,10,17,3,29,21,16,31,9,18,25,33,4,30,4,34}

    Returns: 21279739

  42. 19

    {11,13,0,12,16,13,3,8,4,2,15,13,8,18,15,0,10,17,16}

    Returns: 65601719

  43. 24

    {9,19,1,4,5,0,8,17,18,0,3,6,4,5,7,2,9,4,16,10,5,1,21,4}

    Returns: 8660474

  44. 8

    {4,1,3,5,0,5,4,1}

    Returns: 402

  45. 22

    {15,19,18,2,8,16,5,9,4,1,13,2,20,12,9,6,8,19,8,4,7,21}

    Returns: 46903947

  46. 17

    {16,8,12,2,16,5,14,3,14,6,13,8,7,10,3,0,16}

    Returns: 0

  47. 46

    {38,4,26,8,9,6,26,36,20,38,26,4,5,12,23,10,37,3,26,32,5,32,14,35,30,32,25,11,29,15,2,44,15,25,32,40,43,25,26,25,37,24,1,44,16,13}

    Returns: 5705874

  48. 11

    {6,1,5,8,3,1,9,6,5,8,5}

    Returns: 45498

  49. 4

    {1,3,0,3}

    Returns: 2

  50. 32

    {11,2,10,16,18,3,4,22,3,15,22,6,9,7,15,14,29,28,17,21,11,30,29,8,9,14,16,22,9,26,11,7}

    Returns: 70270746

  51. 29

    {24,17,19,14,16,23,12,22,17,3,20,1,17,2,23,24,6,24,2,0,25,28,22,25,6,26,6,10,21}

    Returns: 28907421

  52. 48

    {25,32,26,47,21,31,7,35,6,7,6,44,13,38,39,23,28,40,25,40,23,16,23,45,26,42,29,11,16,28,15,29,27,10,44,0,45,36,17,27,38,13,16,19,28,18,36,23}

    Returns: 76712977

  53. 6

    {2,4,5,4,1,2}

    Returns: 0

  54. 34

    {22,16,20,15,12,23,13,7,29,12,5,7,20,1,11,9,4,29,12,24,28,30,18,9,6,33,26,18,1,18,13,11,9,31}

    Returns: 69949640

  55. 22

    {9,12,10,3,13,21,13,10,8,6,7,2,1,18,21,0,18,11,1,12,11,14}

    Returns: 63409775

  56. 22

    {17,15,8,12,21,1,19,0,19,21,4,20,11,2,20,4,20,11,17,15,2,8}

    Returns: 85525683

  57. 40

    {8,0,28,17,20,6,4,28,17,36,3,24,27,32,21,8,10,28,16,27,19,13,29,32,1,22,18,24,13,32,37,4,31,24,19,32,25,12,17,38}

    Returns: 41929254

  58. 13

    {9,2,3,12,4,11,8,2,4,12,11,10,12}

    Returns: 1526476

  59. 50

    {10,22,38,44,49,25,27,9,34,44,5,19,15,10,17,28,42,22,4,5,37,41,30,33,32,34,49,42,17,47,36,25,16,29,37,12,33,39,12,42,32,31,34,11,6,49,41,10,19,33}

    Returns: 86451739

  60. 50

    {25,19,9,4,40,2,24,39,38,15,43,1,9,22,0,30,21,6,0,11,15,43,47,46,15,42,17,13,25,10,21,44,17,2,46,18,43,4,45,13,17,48,21,13,40,49,48,12,43,27}

    Returns: 78191361

  61. 50

    {15,39,16,39,33,24,13,17,16,27,8,17,29,0,30,18,19,39,8,30,49,15,39,33,11,31,14,39,21,42,4,1,3,22,41,19,29,5,34,0,19,34,39,35,33,29,36,45,15,36}

    Returns: 5002103

  62. 50

    {29,41,8,20,35,49,30,36,39,10,2,32,28,2,1,11,22,31,15,13,24,43,25,20,3,15,13,14,8,5,33,28,23,34,1,41,32,2,16,24,6,24,38,32,2,13,19,44,41,13}

    Returns: 13152657

  63. 50

    {27,4,21,25,42,38,13,2,3,43,33,17,26,3,32,22,31,35,28,17,22,5,9,38,3,46,32,19,10,13,16,39,10,45,20,5,25,12,29,38,6,10,2,9,34,10,36,23,20,39}

    Returns: 70122410

  64. 50

    {37,47,18,34,36,25,47,34,31,44,41,8,10,20,34,22,21,18,38,32,22,46,6,49,10,28,29,24,0,48,18,2,16,20,1,33,43,34,25,49,39,49,44,14,13,39,4,3,47,21}

    Returns: 70386992

  65. 50

    {43,16,27,31,11,33,47,14,6,27,36,38,5,46,45,43,14,1,19,43,47,5,33,10,31,17,16,39,2,28,13,30,19,1,46,8,44,3,45,21,30,37,7,3,32,5,3,33,17,14}

    Returns: 56299248

  66. 50

    {32,31,27,39,22,3,5,26,21,5,13,25,10,12,37,6,0,5,43,7,37,4,42,44,4,31,4,7,36,40,15,18,42,4,25,45,19,2,8,37,29,9,12,27,10,47,12,35,17,25}

    Returns: 27409175

  67. 50

    {7,17,15,46,19,22,19,24,13,19,44,12,24,17,10,16,18,29,28,35,15,5,39,8,1,47,8,30,15,10,42,43,5,17,5,49,1,42,9,47,34,3,30,13,15,4,17,29,15,42}

    Returns: 4623416

  68. 50

    {29,47,29,6,0,37,14,9,39,32,18,16,12,26,29,37,27,49,7,10,25,36,45,22,5,24,45,31,47,0,18,1,4,29,14,29,14,39,19,41,12,3,24,13,24,19,22,27,40,38}

    Returns: 41296453

  69. 5

    {0,1,0,1,0}

    Returns: 0

  70. 5

    {0,1,0,1,2}

    Returns: 5

  71. 6

    {0,1,0,1,0,1}

    Returns: 4

  72. 50

    {0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1}

    Returns: 51505424

  73. 3

    {1,0,1}

    Returns: 0

  74. 16

    {0, 1, 2, 6, 4, 5, 6, 7, 1, 9, 10, 11, 12, 13, 14, 10 }

    Returns: 96791474

  75. 4

    {1, 2, 3, 0 }

    Returns: 3

  76. 17

    {0, 1, 2, 6, 4, 5, 6, 7, 1, 9, 10, 11, 12, 13, 14, 10, 6 }

    Returns: 90050325

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: