Statistics

Problem Statement for "PolygonSet"

Problem Statement

We call a set X good if:
  • |X| >= 3.
  • There exist a postive area polygon such that each side has a different length, and the set of lengths of sides is X.
You are given a set S, return the number of subsets that is good.

Definition

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

Constraints

  • S will contain between 3 and 50 elements, inclusive.
  • Each number in S will be between 1 and 100, inclusive.
  • Numbers in S will be distinct.

Examples

  1. {1,2,3,4}

    Returns: 2

    We have 2 good sets: {2,3,4} and {1,2,3,4}. Note that {1,2,3} is not good since the triangle will have an area equals to 0.

  2. {90,91,92,93,94,95,96,97,98,99}

    Returns: 968

    Any subset with size at least 3 is good, so we have 2^10 - 1 - 10 - 10*9/2 = 968 good sets.

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

    Returns: 402

  4. {11,12,13,14,15,91,92,93,94,95}

    Returns: 838

  5. {1,2,3}

    Returns: 0

  6. {13, 53, 87, 84}

    Returns: 3

  7. {15, 17, 78, 65, 46, 85, 1, 99, 67, 57, 70, 54, 34, 61, 84, 59, 32, 26, 82, 4, 88, 7, 72, 45, 97, 92, 16, 21, 22, 48, 29}

    Returns: 2147464268

  8. {14, 60, 78, 7, 56, 42, 28, 59, 90, 17, 19, 23, 54, 25, 35, 44, 75, 89, 18, 12, 52, 50, 77, 65, 45, 33, 16, 67, 8, 22, 2, 99, 30}

    Returns: 8589896282

  9. {7, 1, 31, 27, 84, 91, 54, 85, 69, 28, 3, 50, 38, 9, 24, 99, 98, 44}

    Returns: 258853

  10. {100, 42, 82, 91, 43, 64, 70, 63, 11, 26, 79, 76, 94, 98, 28, 80, 23, 49, 78, 65, 73, 54, 7, 55, 32, 87, 61, 3, 17}

    Returns: 536865223

  11. {88, 55, 81, 3, 66, 85, 15, 57, 100, 46, 69, 93, 92, 40, 26, 70, 20, 52, 83, 65}

    Returns: 1047661

  12. {44, 80, 48, 30, 50, 43, 58}

    Returns: 95

  13. {10, 9, 40, 71, 1, 82, 78, 43, 99, 32, 44, 51, 90, 3, 86}

    Returns: 31702

  14. {85, 46, 67, 57, 9, 44, 31, 30, 56, 79, 92, 76, 81, 62, 8, 97, 77, 86, 12, 20, 27, 95, 93, 40, 25, 1, 23, 100, 43, 29, 60}

    Returns: 2147468705

  15. {30, 22, 82, 71, 100, 87, 67}

    Returns: 91

  16. {88, 98, 56, 82}

    Returns: 5

  17. {19, 44, 42, 17, 69, 97, 65, 31, 27, 70, 35, 25}

    Returns: 3855

  18. {58, 57, 90, 22, 71, 52, 96, 65, 38, 6, 76, 29, 51, 78}

    Returns: 16117

  19. {39, 98, 16, 86, 36, 24, 93, 11, 60, 97, 67, 46, 20, 78, 44, 55, 49, 88, 34, 73, 81, 64, 14, 94, 96, 85}

    Returns: 67106171

  20. {46, 66, 9, 95, 90, 62, 79, 14, 45, 28, 74, 97, 78, 13, 63, 64, 22, 42}

    Returns: 261240

  21. {44, 80, 11, 36, 84, 52, 82, 94, 50}

    Returns: 438

  22. {9, 71, 2, 39, 7, 97, 42, 89, 3, 53, 99, 34, 35, 80, 29, 65, 86, 76, 64, 51, 17, 8, 91, 40, 67, 93, 66, 27, 1, 46, 31}

    Returns: 2147445927

  23. {91, 51, 76, 70, 94, 67, 81, 35, 60, 57, 85, 32, 7, 6, 96, 89, 28, 78, 21, 5, 97, 26, 93, 45, 52, 63, 38, 36, 79, 3, 56, 43, 77, 80, 69, 90, 8}

    Returns: 137438927593

  24. {92, 81, 70, 62, 85, 11, 33, 72}

    Returns: 204

  25. {67, 80, 95, 76, 39, 58, 83, 35, 2, 91, 70, 46, 25, 5, 22, 93, 24, 96, 17, 11, 31, 50, 40, 36, 62, 57, 37, 94, 78, 66, 74, 89, 54, 97, 47, 13, 98}

    Returns: 137438931174

  26. {3, 75, 18, 45, 86, 33, 57, 19, 34, 61, 1}

    Returns: 1712

  27. {53, 40, 93, 66, 70, 82, 100, 79, 25, 65, 29, 67, 98, 37, 1, 55, 60, 26, 27, 2, 6, 10, 47, 9, 4, 39, 13, 81, 96, 16, 89, 41, 95}

    Returns: 8589861924

  28. {70, 95, 37, 73, 39, 66, 86, 43, 45, 30, 50, 72, 65, 54, 98, 27, 71, 57, 34, 58, 94}

    Returns: 2096700

  29. {65, 62, 49, 75, 25, 97, 76, 72, 79, 54, 59, 34, 99, 95, 5, 73, 98, 43, 26, 53, 18, 16, 20, 88, 31, 64, 41, 80, 90}

    Returns: 536866992

  30. {20, 31, 93, 53, 6, 58, 45, 47, 74, 51, 48, 9}

    Returns: 3844

  31. {47, 44, 11, 75, 54, 67, 25, 100, 53, 34, 59, 77, 21, 89, 97, 87, 98, 18, 39, 6, 43, 14, 13, 24, 29, 46, 2, 60, 70, 72, 20, 32, 55, 85, 93, 79, 30, 48, 56}

    Returns: 549755772515

  32. {33, 35, 15, 17, 32, 88, 20, 31, 40, 56, 60, 11, 47, 82, 61, 5, 68}

    Returns: 129954

  33. {62, 55, 63, 3, 21, 10, 22, 27, 23, 76, 37, 77, 100}

    Returns: 7635

  34. {37, 3, 46, 83, 29, 62, 10, 56, 72, 35, 34, 61, 16, 81, 75, 89, 69, 85, 88, 80, 96, 14, 8, 54, 74, 93, 42, 94, 30, 68, 67, 82, 99, 24, 60, 38, 55, 32, 4, 13}

    Returns: 1099511584072

  35. {16, 39, 56, 87, 34, 11, 54, 26, 23, 80, 35, 76, 33, 97, 62, 12, 17, 48, 24, 1, 71, 84, 69, 47, 77, 22, 13, 64, 89, 93, 32, 42, 49, 82, 73, 30, 86, 65, 94, 92, 44, 67, 66, 88, 20, 96, 59}

    Returns: 140737488297048

  36. {74, 28, 26, 85, 51, 18, 36, 6, 59, 10, 83, 4, 70, 47, 31, 46}

    Returns: 64447

  37. {81, 57, 45, 60, 35, 86, 71, 94, 65, 23, 2, 6, 13, 19, 1, 40, 76, 72, 26, 24, 98, 21, 33, 64, 15, 38}

    Returns: 67094150

  38. {42, 32, 64, 20, 87, 91, 33, 94, 11, 100, 97, 35, 73, 78}

    Returns: 16044

  39. {90, 50, 92, 83, 98}

    Returns: 16

  40. {76, 53, 94, 87, 57, 79, 45, 40, 69, 85, 52, 62, 59, 88, 82, 3, 21, 81, 41, 91, 67, 78, 24, 51, 16, 65, 100, 14, 38, 4, 25, 50, 71, 75, 20, 77}

    Returns: 68719465211

  41. {16, 56, 7, 97, 43, 83, 67, 65, 34, 85, 11, 40, 91, 94, 54, 77, 55, 66, 68, 44, 35, 60}

    Returns: 4193125

  42. {9, 61, 23, 92, 8, 91, 31, 89, 7, 87, 13, 80, 83, 62}

    Returns: 15680

  43. {86, 34, 23, 96, 26, 97, 58, 7, 87, 68, 25, 42, 33, 88, 64, 21, 1, 77, 60, 40, 37, 2, 41, 80, 61, 14, 79, 36, 75, 70, 83, 11, 57}

    Returns: 8589911978

  44. {17, 61, 91, 15, 30, 25, 13, 80, 33, 26, 84}

    Returns: 1736

  45. {53, 97, 25, 56, 20, 93, 5, 9, 49, 65, 10, 62, 29, 64, 70, 80, 59, 71, 63, 58, 31, 85, 1, 33, 51, 69, 60, 90, 57, 89, 100, 37, 96, 27, 38, 45}

    Returns: 68719460514

  46. {87, 13, 10, 45, 35, 50, 42, 65, 82, 86, 69, 63, 2, 28, 79, 94, 20, 88, 21}

    Returns: 522563

  47. {59, 19, 42, 40, 6, 82, 99, 8, 31, 18, 22, 36, 33, 50, 7, 49, 97, 95, 90, 84, 60, 44, 21, 26, 56, 75, 38, 91, 61, 35, 53, 16}

    Returns: 4294948644

  48. {67, 15, 91, 28, 60, 23, 24, 22, 74, 4, 16, 49, 61}

    Returns: 7662

  49. {98, 2, 39, 29, 32, 24}

    Returns: 14

  50. {49, 67, 10}

    Returns: 0

  51. {45, 95, 63, 15, 64, 36, 8, 14, 75, 6, 22, 12, 87, 3, 59, 90, 83, 94, 24, 11}

    Returns: 1041393

  52. {24, 46, 31, 77, 54, 2, 85, 37, 29, 22, 7, 30, 73, 67, 21, 65, 58, 48, 26, 66, 100, 76, 3, 53}

    Returns: 16772274

  53. {43, 21, 79}

    Returns: 0

  54. {49, 84, 82, 12, 76, 53, 40, 60, 17, 83, 26, 80, 28, 85, 38, 68, 70, 56, 100, 1, 59, 63, 66, 11, 45, 75, 22, 91, 72, 52, 19, 69, 15, 4, 78, 55, 14, 23, 43, 54, 67, 73}

    Returns: 4398046467840

  55. {37, 83, 47, 49, 82, 7, 30, 68, 87, 13, 12, 15, 36, 72, 57, 26, 11, 52, 41, 93, 24, 79, 39, 27, 56, 9, 32, 67, 33, 100, 38, 69, 80, 66, 18}

    Returns: 34359714653

  56. {41, 64, 70, 96, 36}

    Returns: 15

  57. {63, 74, 22, 18, 56, 55, 64, 42, 3, 31, 85, 30, 60, 73, 76, 88, 86, 89, 94, 100, 7, 28, 46, 19, 21, 8, 92, 61, 96, 9, 45, 25, 1, 39, 13, 75, 50, 97, 5, 27, 34, 95, 59, 68, 90, 41, 70}

    Returns: 140737488086227

  58. {6, 33, 84, 42, 86, 100, 78, 9, 65, 58, 18, 59, 72, 35}

    Returns: 15939

  59. {26, 17, 23, 16, 8, 42, 5, 45, 30, 29, 88, 82, 35}

    Returns: 7473

  60. {82, 81, 6, 12, 94, 44, 4, 26, 1, 97, 95, 91, 8, 68, 84, 43}

    Returns: 63706

  61. {24, 89, 17, 76, 38, 55, 36, 28, 83, 39, 10, 62, 74, 70, 63, 22, 31, 14, 23, 11, 29, 46, 25, 87, 20, 49, 33, 84, 75, 97, 18, 53, 8, 1, 72, 98, 6, 67, 79}

    Returns: 549755716751

  62. {37, 61, 43, 57, 29, 56, 74, 62, 85, 17, 2, 14}

    Returns: 3832

  63. {87, 94, 54, 91, 31, 65, 27, 25, 96, 57, 2, 71, 9, 29, 30, 15, 63, 43, 36, 21, 93, 99, 41, 1, 59, 8, 83, 26, 18, 62, 73, 68, 22, 32, 7, 10, 34, 37, 97, 17}

    Returns: 1099511407707

  64. {12, 51, 69, 76, 33, 99, 87, 55, 83, 57, 26, 68, 4, 9, 59, 42, 24, 79}

    Returns: 261042

  65. {33, 84, 47, 59, 50, 89, 76, 60, 27, 49, 70, 4, 87, 44, 96, 20, 69, 52, 39, 28, 41, 51, 71, 29, 85, 7, 91, 3, 35, 17, 21, 37, 81}

    Returns: 8589921002

  66. {94, 67, 21, 100, 52, 14, 5, 35, 25, 69, 9, 13, 79, 43, 99, 8, 7, 40, 39, 87, 18, 88, 73, 30, 84, 96, 54, 44, 82, 31, 22, 36, 62, 74, 81, 60, 37, 71, 58, 68, 17, 63, 92, 27, 19, 89, 48, 28, 53, 41}

    Returns: 1125899906685120

  67. {92, 19, 24, 60, 91, 43, 80, 51, 5, 45, 15, 49, 56, 68, 2, 72, 48, 4, 36, 99, 76, 14, 53, 8, 33, 75, 20, 29, 52, 6, 34}

    Returns: 2147444367

  68. {86, 2, 100, 19, 40, 91, 95, 90, 65, 35, 17, 3, 79, 26, 87, 15, 66, 51, 49, 82, 53, 44, 64, 68, 70, 56, 58, 16, 41}

    Returns: 536863322

  69. {85, 5, 47, 2, 58}

    Returns: 4

  70. {20, 46, 21, 92, 19, 26, 7, 53, 63, 91, 79, 24, 23, 62, 71}

    Returns: 32038

  71. {60, 45, 56, 90, 34, 53, 59, 82, 85, 50, 29, 17, 7, 76, 18}

    Returns: 32341

  72. {53, 90, 23, 7, 43, 81, 54, 89, 99, 82, 70, 65, 19, 8, 74, 34, 20, 27, 91, 77, 79, 67, 28, 14, 21, 52, 24, 16, 95, 100, 40, 46, 18, 56, 41, 22, 9, 50, 51, 78, 26, 84, 37, 31}

    Returns: 17592185966205

  73. {86, 28, 34, 30, 50, 54, 44, 16, 45, 95, 24, 96, 97, 90, 52, 88, 92, 25, 38, 4, 55, 26, 53, 77, 48, 32, 2, 9, 58, 43, 82}

    Returns: 2147470471

  74. {30, 52, 4, 19, 22, 65, 21, 29, 35}

    Returns: 400

  75. {36, 25, 60, 41, 38, 24, 30, 63, 61, 87, 18, 12, 10, 43, 31, 56, 65, 11}

    Returns: 261110

  76. {1,2,3,4,5,6,7,8,9,100}

    Returns: 402

  77. {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: 562949953199072

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: