Statistics

Problem Statement for "MaximalTriangle"

Problem Statement

You are given ints n and z. We have a regular n-gon: a convex polygon with n sides, in which all sides have the same length and all internal angles are equal. We want to draw (n-3) non-intersecting diagonals in some way. Once we do that, we will have the polygon divided into exactly (n-2) triangles. We want to produce a situation in which one of these (n-2) triangles has a strictly larger area than each of the remaining (n-3).

The vertices of the polygon are labeled 1 through n in clockwise order. Two sets of diagonals are different if one of them contains a diagonal that is not present in the other one. Count all sets of (n-3) non-intersecting diagonals that produce an arrangement with the above property. Return that count modulo z.

Definition

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

Constraints

  • n will be between 3 and 444, inclusive.
  • z will be between 1 and 1,000,000,000 (10^9), inclusive.

Examples

  1. 4

    1000000000

    Returns: 0

    There are two ways how to select a diagonal in a square. Each of them produces two triangles of equal size.

  2. 5

    100

    Returns: 5

    There are five ways how to select two non-intersecting diagonals in a regular pentagon. Each of them produces an arrangement in which one triangle has a larger area than each of the other two.

  3. 6

    1000003

    Returns: 2

    For a regular hexagon, some sets of diagonals produce a good set of triangles, and some do not.

  4. 10

    1000000000

    Returns: 1010

  5. 15

    1000000000

    Returns: 714340

  6. 443

    999999999

    Returns: 293730061

  7. 442

    999999998

    Returns: 504849616

  8. 441

    999999997

    Returns: 737824348

  9. 7

    100

    Returns: 42

  10. 8

    1

    Returns: 0

  11. 101

    1

    Returns: 0

  12. 444

    1

    Returns: 0

  13. 400

    1000003

    Returns: 543714

  14. 400

    1000000000

    Returns: 697280800

  15. 428

    900000005

    Returns: 180276168

  16. 400

    536870912

    Returns: 462616864

  17. 119

    12

    Returns: 4

  18. 179

    2

    Returns: 0

  19. 77

    1

    Returns: 0

  20. 362

    362362362

    Returns: 266860970

  21. 277

    1000003

    Returns: 539042

  22. 89

    1000000000

    Returns: 545362956

  23. 414

    414414414

    Returns: 381243078

  24. 444

    111

    Returns: 0

  25. 444

    12124142

    Returns: 4963244

  26. 195

    195195159

    Returns: 194222559

  27. 100

    987654321

    Returns: 308571232

  28. 3

    1

    Returns: 0

  29. 444

    1000000000

    Returns: 877420096

  30. 444

    999999777

    Returns: 8725155

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: