Polygons2
SRM 443 · 2009-06-23 · by gojira_tc
SRM 443 · 2009-06-23 · by gojira_tc · Dynamic Programming, Simple Math
Problem Statement
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.
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.
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
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Polygons2 with a public method long long number(vector<int> segments, int K) · 107 test cases · 2 s / 256 MB per case