TopCoder Statistics - Problem Statement

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
5

10

40000

Returns: 1
1394

92008

40000

Returns: 6
1394

92011

40000

Returns: 22
2

101

12

Returns: 9

Why isn't the maximum nesting sequence 9? 1. 2, 4, 8 2. 10, 20, 40 3. 11, 22, 44 4. 14, 28, 56 5. 16, 32, 64 6. 34, 35, 68 7. 39, 70, 78 8. 49, 75, 88 9. 89, 95, 98 The other three boxes are unused. 5,53,77 7,27,54 17,59,80
1394

92008

20

Returns: 6
1394

92008

200

Returns: 6
93

21505374

40000

Returns: 151
101

19801979

40000

Returns: 158
91

21978021

40000

Returns: 152
91

21978021

40000

Returns: 152
2

536870909

40000

Returns: 17249

*** very large return value ***
7

22

8

Returns: 3
2

536870909

10003

Returns: 4370
28037

53609

35946

Returns: 136
28037

53609

35945

Returns: 135
101

19801979

50000

Returns: 172
91

21978021

50000

Returns: 167
2

536870909

50000

Returns: 21649

Statistics

Problem Statement for "Nestable"

Problem Statement

Definition

Constraints

Examples