TopCoder problem "Polygons2" used in SRM 443 (Division II Level Three)



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

0)
    
{1,1,1,1}
3
Returns: 4
A nondegenerate triangle can be built using any triple from the given segments.
1)
    
{2,3,4,5}
3
Returns: 3
Any triple except {2,3,5} will do.
2)
    
{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.
3)
    
{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}.
4)
    
{3310,1660,211,1260,160,213,884,539,17212,2025,105,120,5510}
7
Returns: 532

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9995

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13751&pm=9995

Writer:

gojira_tc

Testers:

PabloGilberto , Yarin , ivan_metelsky

Problem categories:

Dynamic Programming, Simple Math