Chains1 | Topcoder Archive

Problem Statement

All problems in this problem set are about "chains": collections of nested ranges of integers. All problems are independent, but use the same definitions. Each problem statement contains the definitions it needs. If a term appears in multiple problems, the definition is always identical.

Definitions follow. The defined term is always in uppercase.

An INTERVAL [x,y) with x <= y is the set of integers that are greater than or equal to x, and strictly less than y.
There is only one EMPTY INTERVAL but it has multiple equivalent notations. For example, [0,0) and [3,3) both denote the empty interval. Note that [3,0) is not a valid interval, because an interval [x,y) must have x <= y.
An interval I₁ is called a PROPER SUBSET of an interval I₂ if I₂ contains all elements of I₁ and at least one other element.
A CHAIN is a nonempty sequence of intervals such that each interval (except for the last one) is a proper subset of the next interval.
A CHAIN OF ORDER n is any chain such that the last interval in the chain is either the interval [0,n) or its proper subset.
The LENGTH OF A CHAIN is the number of intervals that form it. (I.e., a chain is a sequence of objects, and when we talk about its length, we mean the length of that sequence.)
A MAXIMAL CHAIN OF ORDER n is any chain such that no other chain of order n has a greater length.

You are given the int n. Compute and return the number of maximal chains of order n.

Definition

Class:: Chains1
Method:: countMaximalChains
Parameters:: int
Returns:: long
Method signature:: long countMaximalChains(int n)
(be sure your method is public)

Notes

For the given constraints it is guaranteed that the correct return value fits into a long.

Constraints

n will be between 1 and 50, inclusive.

Examples

```
2
```
```
Returns: 2
```
The two maximal chains of order 2 are the following: [0,0), [0,1), [0,2) [0,0), [1,2), [0,2) Note that the chain [1,1), [0,1), [0,2) is the same chain as the first chain listed above. This is because [0,0) and [1,1) are two equivalent ways of writing the empty interval. In other words, the two maximal chains of order 2 are: the empty interval, [0,1), [0,2) the empty interval, [1,2), [0,2)

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.