PilingRectsDiv2
SRM 602 · 2013-11-22 · by snuke
SRM 602 · 2013-11-22 · by snuke · Greedy, Search
Problem Statement
Problem Statement
Snake Snuke has N rectangles cut out of paper.
The rectangles are labeled 0 through N-1.
You are given int[] s X and Y with N elements each.
For each i, the sides of rectangle i have lengths X[i] and Y[i].
Snake Snuke will choose some of his rectangles and place them onto a table, one rectangle at a time, in any order he likes. Each rectangle (except for the first one) must overlap the immediately previous one, so at the end Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but once placed, the sides of each rectangle must be parallel to the sides of the table. (I.e., he may only swap the width and height of some rectangles he places.) After placing all the rectangles, Snuke computes the area that is covered by all N rectangles. (Formally, the area of their intersection.)
You are also given anint limit.
The area computed by Snuke must be greater than or equal to limit.
Return the largest positive R such that Snuke can select some R of his rectangles and place them in such a way that the area of their intersection is at least limit. If there is no such R, return -1 instead.
Snake Snuke will choose some of his rectangles and place them onto a table, one rectangle at a time, in any order he likes. Each rectangle (except for the first one) must overlap the immediately previous one, so at the end Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but once placed, the sides of each rectangle must be parallel to the sides of the table. (I.e., he may only swap the width and height of some rectangles he places.) After placing all the rectangles, Snuke computes the area that is covered by all N rectangles. (Formally, the area of their intersection.)
You are also given an
Return the largest positive R such that Snuke can select some R of his rectangles and place them in such a way that the area of their intersection is at least limit. If there is no such R, return -1 instead.
Constraints
- X and Y will contain between 1 and 50 elements, inclusive.
- X and Y will contain the same number of elements.
- Each element of X and Y will be between 1 and 200, inclusive.
- limit will be between 1 and 40000, inclusive.
Examples
0)
{1,2,3,1}
{3,2,4,4}
3
Returns: 3
He can choose rectangles 0, 2, and 3. These three rectangles can then be placed in such a way that both rectangle 2 and rectangle 3 cover rectangle 0 completely. For this placement, the area of their intersection will be exactly 3.
1)
{4,7}
{7,4}
25
Returns: 2
Note that he can rotate rectangles.
2)
{10}
{10}
9999
Returns: -1
There is no possible choice.
3)
{10}
{3}
30
Returns: 1
4)
{3,6,5,8,2,9,14}
{14,6,13,8,15,6,3}
27
Returns: 4
Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PilingRectsDiv2 with a public method int getmax(vector<int> X, vector<int> Y, int limit) · 117 test cases · 2 s / 256 MB per case