Connection Status:
Competition Arena > SmallRectangles

SmallRectangles

SRM 842 · 2022-12-01 · by misof

SRM 842 · 2022-12-01 · by misof · Simple Math, Sorting
Class Name: SmallRectangles
Return Type: long
Method Name: count
Arg Types: (vector<int>, vector<int>, int, int, int, int, int)
Problem Statement

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)

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

1)
{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.

2)
{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.)

3)
{}
{}
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.)

4)
{1,2,3,4,5}
{6,7,8,9,10}
200000
200000
123456789
987654332
2352352
Returns: 39966001261
5)
{}
{}
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.

6)
{}
{}
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.)

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

Coding Area

Language: C++17 · define a public class SmallRectangles with a public method long long count(vector<int> Aprefix, vector<int> Bprefix, int AL, int BL, int AM, int BM, int seed) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous