PolygonSet
2016 TCO India Regional · 2016-03-24 · by cgy4ever
2016 TCO India Regional · 2016-03-24 · by cgy4ever · Dynamic Programming
Problem Statement
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.
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
0)
{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.
1)
{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.
2)
{2,5,8,7,4,3,9,1,6}
Returns: 402
3)
{11,12,13,14,15,91,92,93,94,95}
Returns: 838
4)
{1,2,3}
Returns: 0
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PolygonSet with a public method long long count(vector<int> S) · 77 test cases · 2 s / 256 MB per case