Statistics

Problem Statement for "PolygonDecomposition"

Problem Statement

Determine the number of ways to cut a convex polygon with n sides if the only cuts allowed are from vertex to vertex, each cut divides exactly one polygon into exactly two polygons, and you must end up with exactly k polygons. Consider each vertex distinct. For example, there are three ways to cut a square - the two diagonals and not cutting at all - but only two ways to cut it to form 2 polygons, and only one way to cut it to form 1 polygon. The order of cuts does not matter. Since the number of ways is very large, you should return the number taken modulo 1000000000 (one billion). In other words, if the answer would have at least 10 digits, return only the 9 least significant. If there is no way to cut the polygon into k pieces, return -1.

Definition

Class:
PolygonDecomposition
Method:
howMany
Parameters:
int, int
Returns:
int
Method signature:
int howMany(int n, int k)
(be sure your method is public)

Notes

  • The vertices are distinct - there are 5 ways to cut a pentagon into 3 triangles, not just one way.
  • Only one polygon at a time may be cut - you cannot cut two triangles into four triangles with one cut.

Constraints

  • n is between 3 and 100, inclusive.
  • k is between 1 and 100, inclusive.

Examples

  1. 4

    2

    Returns: 2

    A quadrilateral can be cut into two triangles in two different ways, one for each diagonal.

  2. 100

    1

    Returns: 1

    Any polygon can be cut into one polygon by not cutting at all, but no other way.

  3. 6

    4

    Returns: 14

  4. 31

    20

    Returns: 956146480

    The actual number of ways is about 6.5 x 10^18, but we return only the final 9 digits.

  5. 3

    4

    Returns: -1

  6. 100

    70

    Returns: 483656000

  7. 100

    99

    Returns: -1

  8. 86

    54

    Returns: 878629120

  9. 20

    18

    Returns: 477638700

  10. 60

    40

    Returns: 824997600

  11. 49

    31

    Returns: 139054520

  12. 53

    49

    Returns: 542027500

  13. 59

    22

    Returns: 604428400

  14. 80

    15

    Returns: 744889600

  15. 5

    2

    Returns: 5

  16. 86

    47

    Returns: 870688000

  17. 94

    82

    Returns: 879228580

  18. 94

    48

    Returns: 27400000

  19. 81

    71

    Returns: 486930750

  20. 24

    8

    Returns: 590353000

  21. 97

    9

    Returns: 20783665

  22. 27

    9

    Returns: 706834676

  23. 93

    7

    Returns: 238039280

  24. 33

    23

    Returns: 931454125

  25. 22

    20

    Returns: 564120420

  26. 25

    3

    Returns: 25025

  27. 66

    16

    Returns: 14590075

  28. 71

    30

    Returns: 726145792

  29. 96

    22

    Returns: 851953200

  30. 25

    12

    Returns: 41757400

  31. 84

    57

    Returns: 523094720

  32. 75

    47

    Returns: 207033600

  33. 26

    14

    Returns: 323238824

  34. 21

    4

    Returns: 361284

  35. 51

    39

    Returns: 143531072

  36. 77

    66

    Returns: 964913990

  37. 68

    8

    Returns: 541304480

  38. 15

    64

    Returns: -1

  39. 59

    59

    Returns: -1

  40. 55

    99

    Returns: -1

  41. 51

    72

    Returns: -1

  42. 87

    94

    Returns: -1

  43. 5

    3

    Returns: 5

  44. 6

    3

    Returns: 21

  45. 7

    3

    Returns: 56

  46. 7

    4

    Returns: 84

  47. 7

    5

    Returns: 42

  48. 7

    6

    Returns: -1

  49. 4

    2

    Returns: 2

  50. 100

    69

    Returns: 522590000

  51. 99

    70

    Returns: 716292000

  52. 99

    69

    Returns: 626110000

  53. 100

    71

    Returns: 643593600

  54. 100

    72

    Returns: 257452000

  55. 100

    68

    Returns: 585228000

  56. 100

    66

    Returns: 540696700

  57. 99

    55

    Returns: 716928000

  58. 99

    56

    Returns: 636681600

  59. 95

    45

    Returns: 820040000

  60. 95

    55

    Returns: 646182400

  61. 100

    78

    Returns: 680016000

  62. 100

    50

    Returns: 545532000

  63. 41

    20

    Returns: 871076350

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: