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

You are given a collection of intervals. Use them to build a collection of valid chains. Minimize the number of chains. Return that minimal number of chains.

The first few intervals are given in the int[]s x and y: for each valid i, you have an interval [ x[i], y[i] ).

The remaining intervals will be generated pseudorandomly as follows:

while you have fewer than n intervals in your collection:
    seed = (a * seed + b) mod c
    newx = seed mod m
    seed = (a * seed + b) mod c
    newy = seed mod m
    if newx &gt; newy:
        swap( newx, newy )
    add the interval [newx, newy) to your collection

Definition

Class:: Chains5
Method:: construct
Parameters:: int[], int[], int, int, int, int, int, int
Returns:: int
Method signature:: int construct(int[] x, int[] y, int n, int seed, int a, int b, int c, int m)
(be sure your method is public)

Notes

The collection may contain multiple copies of the same interval. In that case, exactly that many copies of that interval must appear in the collection of chains you'll construct.
The reference solution works for any input of the given size, it does not depend on any properties of the pseudorandom generator.
Watch out for integer overflow when generating your input.

Constraints

g will be between 0 and 200, inclusive.
Each of x and y will have exactly g elements.
For each valid i, 0 <= x[i] <= y[i] < 2^30.
n will be between g and 100,000, inclusive.
c will be between 1 and 2^30, inclusive.
m will be between 1 and c, inclusive.
seed, a, and b will be between 0 and c-1, inclusive.

Examples

```
{1, 2, 1}
```
```
{7, 4, 10}
```
```
3
```
```
0
```
```
0
```
```
0
```
```
1
```
```
1
```
```
Returns: 1
```
We can form one chain using all three intervals: [2,4), [1,7), [1,10).
```
{1, 2}
```
```
{7, 14}
```
```
2
```
```
0
```
```
0
```
```
0
```
```
1
```
```
1
```
```
Returns: 2
```
We need two separate chains, each consisting of a single interval.
```
{1, 2, 3, 3, 0}
```
```
{2, 3, 4, 4, 9}
```
```
5
```
```
0
```
```
0
```
```
0
```
```
1
```
```
1
```
```
Returns: 4
```
One optimal solution is to have one chain [2,3), [0,9) and three one-interval chains.
```
{}
```
```
{}
```
```
0
```
```
0
```
```
0
```
```
0
```
```
1
```
```
1
```
```
Returns: 0
```
An empty collection of intervals means that an empty collection of chains is enough.
```
{10}
```
```
{20}
```
```
7
```
```
47
```
```
100
```
```
1
```
```
1073741824
```
```
1000000
```
```
Returns: 4
```
You should generate the following collection of intervals: [10,20), [4701,470101), [10101,42805), [213557,833013), [784309,813557), [217717,721781), [95285,924405).

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.