SmallRectangles | Topcoder Archive

Problem Statement

We are given two int[]s A and B, with AL and BL elements, respectively. These describe how to cut a rectangle

The whole rectangle has dimensions sum(A) times sum(B). It is cut into AL times BL smaller rectangles by making AL-1 cuts orthogonal to the side of length sum(A) and BL-1 cuts orthogonal to the other side.

The elements of A are the lengths of the segments into which the cuts divide the side of length sum(A). Similarly, the elements of B are the lengths of the segments into which the other side of the rectangle is divided. Hence, A and B are the side lengths of the smaller rectangles that are produced by cutting the large one into pieces.

For example, if A = {2, 2} and B = {3, 4, 3}, we have a 4x10 rectangle that is cut into four 2x3 and two 2x4 rectangles as follows:


   +---+---+---+---+---+---+---+---+---+---+
   |           |               |           |
 2 +   +   +   +   +   +   +   +   +   +   +
   |           |               |           |
   +---+---+---+---+---+---+---+---+---+---+
   |           |               |           |
 2 +   +   +   +   +   +   +   +   +   +   +
   |           |               |           |
   +---+---+---+---+---+---+---+---+---+---+
         3             4             3

Two small rectangles are the same if one of them can be rotated to obtain the other. For example, 2x3 and 3x2 is the same rectangle.

Given A and B, return the number of distinct types of small rectangles produced by cutting the large rectangle.

In order to keep the input small, the arrays A and B are pseudorandom. Please use the following pseudocode to generate them.


function generate_array(prefix, L, M):
    # note that this function accesses and modifies the global variable "state"
    new_array = an array of length L
    P = length(prefix)
    for i = 0 to P-1:
        new_array[i] = prefix[i]
    for i = P to L-1:
        state = (state * 1103515245 + 12345) modulo 2^31
        new_array[i] = 1 + (state modulo M)
    return new_array

state = seed
A = generate_array(Aprefix, AL, AM)
B = generate_array(Bprefix, BL, BM)

Definition

Class:: SmallRectangles
Method:: count
Parameters:: int[], int[], int, int, int, int, int
Returns:: long
Method signature:: long count(int[] Aprefix, int[] Bprefix, int AL, int BL, int AM, int BM, int seed)
(be sure your method is public)

Notes

The pseudocode guarantees that all elements of A will be between 1 and AM, inclusive, and all elements of B will be between 1 and BM, inclusive.
Watch out for integer overflow when generating the arrays A and B. We recommend using 64-bit integer variables when implementing the pseudocode.
The reference solution does not depend on the input being pseudorandom. It would correctly solve any input of the given size.

Constraints

AL will be between 1 and 200,000, inclusive.
AM will be between 1 and 10^9, inclusive.
Aprefix will have between 0 and min(AL, 200) elements, inclusive.
Each element of Aprefix will be between 1 and AM, inclusive.
BL, BM, and Bprefix will satisfy the same constraints as AL, AM, and Aprefix, respectively. (In particular, Bprefix will have at most min(BL, 200) elements.)
seed will be between 0 and 2^31 - 1, inclusive.

Examples

```
{2, 2}
```
```
{3, 4, 3}
```
```
2
```
```
3
```
```
1000
```
```
1000
```
```
0
```
```
Returns: 2
```
The example from the problem statement: A = {2, 2} and B = {3, 4, 3}. There are two rectangle types: 2x3 and 2x4.
```
{2, 3}
```
```
{2, 3}
```
```
2
```
```
2
```
```
1000
```
```
1000
```
```
0
```
```
Returns: 3
```
Here, A = B = {2, 3}. The cut rectangle looks as follows: +---+---+---+---+---+ | | | 2 + + + + + + | | | +---+---+---+---+---+ | | | + + + + + + 3 | | | + + + + + + | | | +---+---+---+---+---+ 2 3 There are four small rectangles, but two of them (2x3 and 3x2) look the same, so there are only three distinct rectangle types.
```
{4}
```
```
{7, 3}
```
```
5
```
```
7
```
```
10
```
```
20
```
```
47
```
```
Returns: 28
```
By following the given pseudocode you should generate the following arrays: A = { 4, 9, 6, 9, 2 } B = { 7, 3, 9, 14, 11, 8, 17 } (You can use this example to test whether you implemented the pseudocode to generate A and B correctly.)
```
{}
```
```
{}
```
```
51000
```
```
45000
```
```
999999973
```
```
999999978
```
```
4247
```
```
Returns: 2295000000
```
In this example the 51000*45000 small rectangles are all mutually distinct. (Note that the correct answer for this test case overflows a signed 32-bit integer.)
```
{}
```
```
{}
```
```
1
```
```
1
```
```
100
```
```
100
```
```
100
```
```
Returns: 1
```
We have A = {98} and B = {11}. Thus, the original rectangle has dimensions 98 x 11. As AL = BL = 1, there are no cuts and the result is that there is exactly one small rectangle: the original 98 x 11 rectangle.
```
{}
```
```
{}
```
```
12
```
```
34
```
```
3
```
```
3
```
```
13124
```
```
Returns: 6
```
The six distinct rectangle types here are the 1x1, 1x2, 1x3, 2x2, 2x3, and 3x3 rectangle. (Some of the pieces are 2x1, 3x1, and 3x2 rectangles but those can be rotated to produce rectangles we already listed.)

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.