Connection Status:
Competition Arena > Nestable

Nestable

TCO '03 Finals · 2003-10-07 · by dgoodman

TCO '03 Finals · 2003-10-07 · by dgoodman · Sorting
Class Name: Nestable
Return Type: int
Method Name: maxCount
Arg Types: (int, int, int)
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
    }

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
0)
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.

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.

2)
10
100000007
40000
Returns: 1299
3)
5
10
40000
Returns: 1
4)
1394
92008
40000
Returns: 6
6)
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

13)
2
536870909
40000
Returns: 17249

*** very large return value ***

Submissions are judged against all 21 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Nestable with a public method int maxCount(int a, int p, int n) · 21 test cases · 2 s / 256 MB per case

Submitting as anonymous