PolygonDecomposition
SRM 264 · 2005-09-20 · by Enogipe
SRM 264 · 2005-09-20 · by Enogipe · Dynamic Programming
Problem Statement
Problem Statement
Determine the number of ways to cut a convex polygon with n sides if the only cuts allowed are from vertex to vertex, each cut divides exactly one polygon into exactly two polygons, and you must end up with exactly k polygons. Consider each vertex distinct. For example, there are three ways to cut a square - the two diagonals and not cutting at all - but only two ways to cut it to form 2 polygons, and only one way to cut it to form 1 polygon. The order of cuts does not matter. Since the number of ways is very large, you should return the number taken modulo 1000000000 (one billion). In other words, if the answer would have at least 10 digits, return only the 9 least significant. If there is no way to cut the polygon into k pieces, return -1.
Notes
- The vertices are distinct - there are 5 ways to cut a pentagon into 3 triangles, not just one way.
- Only one polygon at a time may be cut - you cannot cut two triangles into four triangles with one cut.
Constraints
- n is between 3 and 100, inclusive.
- k is between 1 and 100, inclusive.
Examples
0)
4 2 Returns: 2
A quadrilateral can be cut into two triangles in two different ways, one for each diagonal.
1)
100 1 Returns: 1
Any polygon can be cut into one polygon by not cutting at all, but no other way.
2)
6 4 Returns: 14
3)
31 20 Returns: 956146480
The actual number of ways is about 6.5 x 10^18, but we return only the final 9 digits.
4)
3 4 Returns: -1
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PolygonDecomposition with a public method int howMany(int n, int k) · 63 test cases · 2 s / 256 MB per case