Polygons2 | Topcoder Archive

Problem Statement

You are given N line segments numbered 1 to N. The lengths of these segments are given in the int[] segments. Compose a convex K-sided polygon, where each side is one of the given segments. Each segment can only be used once in the polygon.

Return the number of different polygons you can compose. Two polygons are considered different if there exists a segment i such that one of the polygons contains segment i but the other polygon does not.

Definition

Class:: Polygons2
Method:: number
Parameters:: int[], int
Returns:: long
Method signature:: long number(int[] segments, int K)
(be sure your method is public)

Notes

A convex polygon can be constructed from a set of segments if the length of each segment from this set is strictly less than the sum of lengths of the remaining segments.

Constraints

segments will contain between 1 and 50 elements, inclusive.
K will be between 3 and 10, inclusive.
Each element of segments will be between 1 and 50,000, inclusive.

Examples

```
{1,1,1,1}
```
```
3
```
```
Returns: 4
```
A nondegenerate triangle can be built using any triple from the given segments.
```
{2,3,4,5}
```
```
3
```
```
Returns: 3
```
Any triple except {2,3,5} will do.
```
{4,4,4,2,2,2}
```
```
3
```
```
Returns: 11
```
You can a make nondegenerate triangle using three segments of length 2, or three segments of length 4, or any two segments of length 4 with any segment of length 2.
```
{10,1,4,9,20}
```
```
4
```
```
Returns: 2
```
One can build a convex quadrangle using segments {10,1,4,9} or {10,4,9,20}.

{3310,1660,211,1260,160,213,884,539,17212,2025,105,120,5510}

Returns: 532

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.