Chains2 | 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.

You are given a sequence of valid intervals. More precisely, you are given two int[]s: x and y. It is guaranteed that for each valid i, [ x[i], y[i] ) is a valid interval.

If the given sequence of intervals is a chain. return R, where R is the smallest nonnegative integer such that the chain is a chain of order R.

If the given sequence of intervals is not a chain, return (-T), where T is the largest positive integer such that the first T-1 intervals of the input sequence still do form a valid chain.

Definition

Class:: Chains2
Method:: validate
Parameters:: int[], int[]
Returns:: int
Method signature:: int validate(int[] x, int[] y)
(be sure your method is public)

Constraints

n will be between 1 and 30, inclusive.
Each of x and y will have exactly n elements.
For each valid i, 0 <= x[i] <= y[i] < 2^30.

Examples

```
{0, 0, 0}
```
```
{0, 1, 3}
```
```
Returns: 3
```
```
{1, 4, 4}
```
```
{1, 7, 8}
```
```
Returns: 8
```
Note that the first interval in this chain is the empty interval. The empty interval is a proper subset of the interval [4,7) so everything is in order.
```
{4, 4, 3}
```
```
{5, 7, 6}
```
```
Returns: -3
```
[4,5), [4,7) is a valid chain but [4,5), [4,7), [3,6) isn't.
```
{4, 4}
```
```
{7, 7}
```
```
Returns: -2
```
Each interval must be a proper subset of the next one.
```
{3}
```
```
{3}
```
```
Returns: 0
```
This valid chain consists of one interval. That interval happens to be the empty interval. Thus, this is a valid chain of order 0.

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.