FencingPenguins

SRM 566 · 2012-12-13 · by tehqin

SRM 566 · 2012-12-13 · by tehqin · Dynamic Programming, Geometry

Show categories

Class Name: FencingPenguins

Return Type: int

Method Name: countWays

Arg Types: (int, int, vector<int>, vector<int>, string)

Problem Statement

Paco collects penguins. His penguins like to play and run around on the ice where he lives. In order to keep his penguins safe he decided to construct fences to keep danger out.

Paco's penguins have fallen asleep. Acting quickly Paco placed numPosts posts in a circular configuration on the ice. Each post is placed radius meters from location (0,0). The posts are equally spaced with the first post being placed at location (radius, 0).

To construct the fencing, Paco will connect some pairs of fence posts using straight fences. No two segments of the fence are allowed to cross. In the resulting fencing, each fence post will either be unused, or it will be connected to exactly two other fence posts. The fences will create some enclosed areas. In order to avoid wasting resources, Paco requires that each of the enclosed areas has to contain at least one penguin.

Paco's penguins come in many different colors. Penguins of the same color often like to play together. As a result, Paco would like to keep all penguins of the same color in the same enclosure. Two penguins are considered in the same enclosure if they can walk to each other without crossing some fence.

Paco would like to keep all his penguins safe so he would also like to guarantee that each penguin is in some enclosure.

You are given two ints numPosts and radius. You are also given two int[]s x and y representing the (x,y) location of each of the sleeping penguins. Each penguin is small enough to be considered a point. You are also given a String color. The i-th character of color is an uppercase or lowercase alphabetic character representing the color of the i-th penguin. Compute and return the number of fencings that Paco can use to keep his penguins safe. If it is not possible to create any enclosure that meets all the requirements return 0. Two fencings are considered different if two posts are connected in one fencing but not in the other. As the number of fencings can be quite large, please return the result modulo 100,007.

Notes

Here are some examples of invalid fencings:

Constraints

numPosts will be between 3 and 222, inclusive.
radius will be between 5 and 100,000, inclusive.
x will contain between 1 and 50 elements, inclusive.
y will contain the same number of elements as x.
color will contain the same number of characters as elements in x.
Each element in x will be between -100,000 and 100,000, inclusive.
Each element in y will be between -100,000 and 100,000, inclusive.
Each character of color will be an uppercase or lowercase letter.
No penguin will come within 10^-6 of any potential fencing.
No two penguins will occupy the same location.

Examples

4
10
{2}
{1}
"R"
Returns: 3

If the posts are numbered starting from 0 at (radius, 0) and increasing in the counter-clockwise direction. The 3 resulting answers would be: {(0,1,2)} {(0,1,3)} {(0,1,2,3)}

4
10
{2,-2}
{1,-1}
"RR"
Returns: 1

The only way to satisfy all the requirements is to connect all the fence posts. {(0,1,2,3)}

8
10
{8,-8,-8,8}
{1,-1,1,-1}
"BBBB"
Returns: 25

There are 25 ways to form a single fence around the penguins.

8
10
{8,-8,-8,8}
{1,-1,1,-1}
"RGBY"
Returns: 50

6
5
{0,0}
{-4,4}
"rB"
Returns: 6

There are the six possible ways to fence these two penguins: {(0,1,2,3,4,5)} {(0,1,2,4,5)} {(1,2,3,4,5)} {(1,2,4,5)} {(1,2,3),(0,4,5)} {(0,1,2),(3,4,5)}

Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FencingPenguins with a public method int countWays(int numPosts, int radius, vector<int> x, vector<int> y, string color) · 108 test cases · 2 s / 256 MB per case