PilingRectsDiv1 | Topcoder Archive

Problem Statement

Snake Snuke has 2N rectangles cut out of paper. The rectangles are labeled 0 through 2N-1. For each i, the side lengths of rectangle i will be denoted X[i] and Y[i].

The number N can be very large, therefore we will use a pseudorandom generator to define the values X[i] and Y[i]. You are given the following input:

The int N.
Two int[]s: XS and YS.
Six ints: XA, XB, XC, YA, YB, YC.

Use the following pseudocode to generate X and Y:

for (i = 0; i &lt; (length of XS); i++) {
    X[i] = XS[i];
    Y[i] = YS[i];
}
for (i = (length of XS); i &lt; 2 * N; i++) {
    X[i] = (X[i - 1] * XA + XB) % XC + 1;
    Y[i] = (Y[i - 1] * YA + YB) % YC + 1;
}

Snake Snuke will divide his 2N rectangles into two bags, each bag containing exactly N rectangles. Then he will process each bag separately.

When processing a bag, he will take all the rectangles out of the bag and he will place them onto a table, one rectangle at a time. Each rectangle (except for the first one) must overlap the immediately previous one, so at the end Snuke will have a pile of N rectangles. Snuke may rotate the rectangles, but once placed, the sides of each rectangle must be parallel with the sides of the table. (I.e., he may only swap the width and height of some rectangles.) After placing all the rectangles, Snuke computes the area that is covered by all N rectangles. (Formally, the area of their intersection.) That area is called the outcome of that bag.

Snuke wants to maximize the sum of the outcomes of his two bags. That is, he must first divide the rectangles into bags in an optimal way, and then process each bag in an optimal way. Return the maximal possible sum of the two outcomes.

Definition

Class:: PilingRectsDiv1
Method:: getmax
Parameters:: int, int[], int[], int, int, int, int, int, int
Returns:: long
Method signature:: long getmax(int N, int[] XS, int[] YS, int XA, int XB, int XC, int YA, int YB, int YC)
(be sure your method is public)

Constraints

N will be between 1 and 100,000, inclusive.
XS will contain between 1 and min{50, 2*N} elements, inclusive.
XS and YS will be contain the same number of elements, inclusive.
Each element of XS and YS will be between 1 and 1,000,000,000 (109), inclusive.
XA, XB, YA and YB will be between 0 and 1,000,000,000 (109), inclusive.
XC and YC will be between 1 and 1,000,000,000 (109), inclusive.

Examples

```
2
```
```
{1,2,3,4}
```
```
{10,5,3,5}
```
```
0
```
```
0
```
```
1
```
```
0
```
```
0
```
```
1
```
```
Returns: 14
```
Snuke should put rectangles 0 and 1 in one bag, and rectangles 2 and 3 into the other bag. He can then process the bags as shown in the picture below (where rectangle 0 is labeled as "first", and so on). The sum of the two areas is 14. There are other equally good solutions, but there is no better solution than 14.
```
2
```
```
{7,7}
```
```
{4,4}
```
```
9
```
```
0
```
```
10
```
```
2
```
```
7
```
```
9
```
```
Returns: 56
```
X is {7,7,4,7} and Y is {4,4,7,4}. Note that it is allowed to rotate the rectangles. Regardless of how Snuke divides the rectangles into bags, each bag will contain two 4x7 rectangles. When processing a bag, Snuke can align the two rectangles perfectly. Thus the answer is 28 + 28 = 56.

{5,6,9,10,4,7}

{9,5,8,6,8,7}

Returns: 69

```
10000
```
```
{1000000000}
```
```
{1000000000}
```
```
93827162
```
```
91238127
```
```
98231267
```
```
92138287
```
```
98563732
```
```
99381279
```
```
Returns: 1240119561532788
```
Use a 64-bit data type for generating the input data in order to avoid overflow. Also note that the return value is a long.

{375,571,973,896,460,930,583,530,657,590}

{284,37,994,699,941,745,166,884,270,708}

Returns: 420515

{898,579,465,665,875,391,583,901,326,133,656,562,701,707,492,617,455,441,382,952,689,656,334,877,120,318,497,25,569,962,845,562,632,898,882,498,595,889,382,507,791,548,810,606,105,869,569,970,322,974}

{83,18,492,27,339,622,851,915,464,347,287,210,282,166,976,167,968,769,14,383,454,983,319,165,185,315,795,851,124,287,846,745,19,639,894,828,540,420,147,452,501,670,466,554,166,1,446,808,508,172}

Returns: 10050

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.