HarmoniousGarden | Topcoder Archive

Problem Statement

Fox Ciel wants to build a garden. In this task, a garden consists of some pavilions and some paths. Each path is bidirectional and connects two different pavilions. Each pair of pavilions can be directly connected by at most one path.

A simple cycle is a sequence (x1, x2, ..., xm) of three or more mutually distinct pavilions such that the garden contains all of the following paths: (x1, x2), (x2, x3), ..., (xm-1, xm), and also (xm, x1). The length of a simple cycle is the number of pavilions it contains.

Two cycles are considered the same if we can rotate and/or flip one of them to get the other. For example, (x1, x2, x3, x4), (x2, x3, x4, x1), and (x4, x3, x2, x1) are all the same cycle, but (x1, x3, x2, x4) is another cycle that is not the same as the first three.

You are given the ints n, k, and L. Fox Ciel wants to build a garden with exactly n pavilions. The garden should contain exactly k distinct simple cycles. Additionally, each of those simple cycles must have length exactly L.

Return "Possible" (quotes for clarity) if such a garden exists, or "Impossible" if there is no such garden.

Definition

Class:: HarmoniousGarden
Method:: isPossible
Parameters:: int, int, int
Returns:: String
Method signature:: String isPossible(int n, int k, int L)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
k will be between 1 and 50, inclusive.
L will be between 3 and 50, inclusive.

Examples

```
8
```
```
2
```
```
4
```
```
Returns: "Possible"
```
We want a garden with 8 pavilions. The garden must contain exactly 2 simple cycles, and each simple cycle in the garden must have length 4. This is possible. One such garden is shown below. Note that the garden is not required to be connected. #-# #-# | | | | #-# #-#
```
3
```
```
2
```
```
3
```
```
Returns: "Impossible"
```
We can show that any garden with 3 pavilions can have at most one simple cycle.
```
5
```
```
2
```
```
3
```
```
Returns: "Possible"
```
One of the solutions is: # # |\ /| | # | |/ \| # #
```
50
```
```
1
```
```
47
```
```
Returns: "Possible"
```
```
50
```
```
2
```
```
47
```
```
Returns: "Impossible"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.