Connection Status:
Competition Arena > PilingRectsDiv1

PilingRectsDiv1

SRM 602 · 2013-11-22 · by snuke

SRM 602 · 2013-11-22 · by snuke · Greedy, Sorting
Class Name: PilingRectsDiv1
Return Type: long
Method Name: getmax
Arg Types: (int, vector<int>, vector<int>, int, int, int, int, int, int)
Problem Statement

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 < (length of XS); i++) {
    X[i] = XS[i];
    Y[i] = YS[i];
}
for (i = (length of XS); i < 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.

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

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

2)
3
{5,6,9,10,4,7}
{9,5,8,6,8,7}
0
0
1
0
0
1
Returns: 69
3)
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.

4)
1
{1}
{1}
1
1
1
1
1
1
Returns: 2

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

Coding Area

Language: C++17 · define a public class PilingRectsDiv1 with a public method long long getmax(int N, vector<int> XS, vector<int> YS, int XA, int XB, int XC, int YA, int YB, int YC) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous