google competion question...
ankit tuteja
Greenhorn
Posts: 7
posted 10 years ago
Hi,, as the compiteion is over..
but i am not able to get the language of question...can anybody please tell in easy language...the meaning of problem... what its asking and whats is all about... it will great for all of us to do that problem... i am encouraging others to solve that personally and take the problem as challange..
here it is..
** THE QUESTION IS POSTED HERE ONLY TO KNOW THE MEANING OF IT...
==========================================================
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. The boxes are rectangular, but they are open at the top so their heights don't matter. If we call the smaller horizontal dimension of a box its width and the other dimension its length, a box can be nested in another box if its width is less than the other's width, and its length is less than the other's 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^(2n1),a^(2n))
where a^j denotes (a to the j power) mod p.
Create a class UnNestable that contains a method maxCount that is given the positive integral values a, p, and n and that returns the size of the largest unnestable collection of boxes, where a collection is unnestable if no two boxes from the collection can be nested.
The sequence of boxes can be generated by
int rv=1;
for(int i=0; i<n; i++){
rv = (rv*a)%p; int x=rv;
rv = (rv*a)%p; int y=rv;
//process this box, which has dimensions x and y
}
Definition
Class:
UnNestable
Method:
maxCount
Parameters:
int, int, int
Returns:
int
Method signature:
int maxCount(int a, int p, int n)
(be sure your method is public)
Notes

The sequence may cycle, resulting in many boxes of the same dimensions. Duplicate boxes do count in the size of an unnestable collection
Constraints

p is between 2 and 2,000,000,000, inclusive.

a is between 1 and p1, 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 10,000 inclusive
Examples
0)
10
15
3
Returns: 3
The random generator produces 10, (10*10)%15=10, 10*10%15=10, ... so the The three boxes are (10,10), (10,10), and (10,10). The entire collection is unnestable.
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), (4, 14), (6, 9) and (5, 16). The nonnesting pairs are (10, 15) with (5, 16), (4, 14) with (6, 9), and (6, 9) with (5, 16). No collection of 3 of these boxes is pairwise unnestable.
2)
3
1000
3
Returns: 1
The boxes are (3,9), (27,81), and (243,729). The first one is nestable in both the others, and the second one is nestable in the third one. So there is no way to choose 2 of them which are unnestable. Of course, any collection of size one has the property that no two boxes from the collection can be nested.
3)
3
104729
10000
Returns: 9
but i am not able to get the language of question...can anybody please tell in easy language...the meaning of problem... what its asking and whats is all about... it will great for all of us to do that problem... i am encouraging others to solve that personally and take the problem as challange..
here it is..
** THE QUESTION IS POSTED HERE ONLY TO KNOW THE MEANING OF IT...
==========================================================
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. The boxes are rectangular, but they are open at the top so their heights don't matter. If we call the smaller horizontal dimension of a box its width and the other dimension its length, a box can be nested in another box if its width is less than the other's width, and its length is less than the other's 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^(2n1),a^(2n))
where a^j denotes (a to the j power) mod p.
Create a class UnNestable that contains a method maxCount that is given the positive integral values a, p, and n and that returns the size of the largest unnestable collection of boxes, where a collection is unnestable if no two boxes from the collection can be nested.
The sequence of boxes can be generated by
int rv=1;
for(int i=0; i<n; i++){
rv = (rv*a)%p; int x=rv;
rv = (rv*a)%p; int y=rv;
//process this box, which has dimensions x and y
}
Definition
Class:
UnNestable
Method:
maxCount
Parameters:
int, int, int
Returns:
int
Method signature:
int maxCount(int a, int p, int n)
(be sure your method is public)
Notes

The sequence may cycle, resulting in many boxes of the same dimensions. Duplicate boxes do count in the size of an unnestable collection
Constraints

p is between 2 and 2,000,000,000, inclusive.

a is between 1 and p1, 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 10,000 inclusive
Examples
0)
10
15
3
Returns: 3
The random generator produces 10, (10*10)%15=10, 10*10%15=10, ... so the The three boxes are (10,10), (10,10), and (10,10). The entire collection is unnestable.
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), (4, 14), (6, 9) and (5, 16). The nonnesting pairs are (10, 15) with (5, 16), (4, 14) with (6, 9), and (6, 9) with (5, 16). No collection of 3 of these boxes is pairwise unnestable.
2)
3
1000
3
Returns: 1
The boxes are (3,9), (27,81), and (243,729). The first one is nestable in both the others, and the second one is nestable in the third one. So there is no way to choose 2 of them which are unnestable. Of course, any collection of size one has the property that no two boxes from the collection can be nested.
3)
3
104729
10000
Returns: 9
Ryan McGuire
Ranch Hand
Posts: 1072
4
posted 10 years ago
The hypothetical company we're at makes corrugated carboard boxes. All the sides of each box is rectangular (a cuboid). The boxes have no tops. To save storage and transportation costs, it would be handy if we could "nest" some boxes inside of others. For example: since the boxes have no tops, a box that has a 18x25 footprint and is 30 tall can be nested in a box that has a 19x26 foot print and is only 10 tall. We enter values a, p and n and the machine will make n boxes with footprint sizes (a by (a^2)%p), ((a^3)%p by (a^4)%p), ... (a^(2n1))%p by (a ^ 2n)%p). 2 <= p <= 2,000,000,000; a < p; a*p < 2,000,000,000; 1 <= n <= 10,000 Your job is to create a Java class called UnNestable that contains a method called maxCount with a signature...
int maxCount(int a, int p, int n)maxCount should return the size of the largest collection of boxes that can NOT be nested within each other. (This will be the number of nests needed to store the group of boxes.)
examples:
if a=10, p=15 and n=3, maxcount() should return 3. Why? The 3 boxes produced will have foot prints 10x10, 10x10, and 10x10. No one box will fit inside any other. Therefore all three boxes will be sitting on the floor.
a=10, p=17, n=4
The produced will be 10x15, 4x14, 6x9 and 5x16. Put the 4x14 one in the 5x16 one. Put the 6x9 one in the 10x15 one. No other nesting is possible, so this collection of boxes needs at least 2 nests to be stored. maxCount returns 2.
Is it clear now? Did I use any terms or notation you don't know? (Footprint? 10x15? a^2n? Java ?)
[ March 21, 2006: Message edited by: Ryan McGuire ]
int maxCount(int a, int p, int n)
examples:
if a=10, p=15 and n=3, maxcount() should return 3. Why? The 3 boxes produced will have foot prints 10x10, 10x10, and 10x10. No one box will fit inside any other. Therefore all three boxes will be sitting on the floor.
a=10, p=17, n=4
The produced will be 10x15, 4x14, 6x9 and 5x16. Put the 4x14 one in the 5x16 one. Put the 6x9 one in the 10x15 one. No other nesting is possible, so this collection of boxes needs at least 2 nests to be stored. maxCount returns 2.
Is it clear now? Did I use any terms or notation you don't know? (Footprint? 10x15? a^2n? Java ?)
[ March 21, 2006: Message edited by: Ryan McGuire ]