Nestable | Topcoder Archive

Problem Statement

We make cardboard boxes. We manufacture a variety of sizes and are concerned that storing them and transporting them will be a problem unless we can nest them into a reasonable number of nested stacks. Each box is a rectangular solid and thus has three side lengths. We say that Box A can be nested in Box B if its smallest length is strictly less than B's smallest length, its 2nd smallest length is strictly less than B's 2nd smallest length, and its largest length is strictly less than B's largest length. No diagonal nesting is allowed.

We have automated the manufacturing process so that random sized boxes are produced. We specify values a, p, and n and the machine produces n boxes with dimensions:

(a,a^2,a^3) (a^4,a^5,a^6) (a^7,a^8,a^9) ... (a^(3n-2),a^(3n-1),a^(3n))

where a^j denotes (a to the jth power) mod p.

Create a class Nestable that contains a method maxCount that is given the positive integer values a, p, and n and that returns the size of the largest nestable collection of boxes, where a collection is nestable if every pair of boxes from the collection can be nested.

The sequence of boxes can be generated by
    int length=1;
    for(int i=0; i<n; i++){
        length = (length*a)%p; int x=length;
        length = (length*a)%p; int y=length;
        length = (length*a)%p; int z=length;
        //process this box, which has dimensions x,y,z
    }

Definition

Class:: Nestable
Method:: maxCount
Parameters:: int, int, int
Returns:: int
Method signature:: int maxCount(int a, int p, int n)
(be sure your method is public)

Constraints

p is between 2 and 2,000,000,000 inclusive
a is between 1 and p-1 inclusive
no power of a is divisible by p
a*p is less than or equal to 2,000,000,000
n is between 1 and 50,000 inclusive

Examples

```
10
```
```
15
```
```
3
```
```
Returns: 1
```
The random generator produces 10, (10*10)%15=10, 10*10%15=10, ... so the three boxes are (10,10,10) (10,10,10) (10,10,10). No pair of boxes is nestable, so the largest nestable collection has size 1.
```
10
```
```
17
```
```
4
```
```
Returns: 2
```
The sequence is 10, 100%17=15, 150%17=14, 140%17=4, 40%17=6, ... so the 4 boxes are (10,15,14) (4,6,9) (5,16,7) (2,3,13). (4,6,9) nests inside (5,16,7) and there are many other pairs that nest, but there is no sequence of three boxes that can be nested inside each other.
```
10
```
```
100000007
```
```
40000
```
```
Returns: 1299
```
```
93
```
```
21505374
```
```
40000
```
```
Returns: 151
```
```
7
```
```
22
```
```
8
```
```
Returns: 3
```

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.