RangeSquaredSubsets
SRM 521 · 2011-05-25 · by soul-net
Problem Statement
Given a real number n, a set of points P in the XY plane is called n-squared if it is not empty and there exists a square of side n in the XY plane with its sides parallel to the axes such that a point from the given set of points is in P if and only if it is contained within the square. A point lying on a side or a vertex of the square is considered to be contained in it.
You will be given two
Constraints
- nlow will be between 1 and 100000000 (10^8), inclusive.
- nhigh will be between nlow and 100000000 (10^8), inclusive.
- x and y will contain between 1 and 40 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x and y will be between -100000000 (-10^8) and 100000000 (10^8), inclusive.
- All described points will be different.
5
5
{-5,0,5}
{0,0,0}
Returns: 5
The following subsets are 5-squared: {(-5,0)}, {(0,0)}, {(5,0)}, {(-5,0),(0,0)}, {(0,0),(5,0)}.
10
10
{-5,0,5}
{0,0,0}
Returns: 5
The following subsets are 10-squared: {(-5,0)}, {(5,0)}, {(0,0),(5,0)}, {(-5,0),(0,0)}, {(-5,0),(0,0),(5,0)}.
1
100
{-5,0,5}
{0,0,0}
Returns: 6
{(-5,0),(5,0)} is not x-squared for any x. From the previous 2 examples you can infer that all other non-empty subsets are 5-squared or 10-squared.
3
100000000
{-1,-1,-1,0,1,1,1}
{-1,0,1,1,-1,0,1}
Returns: 21
64
108
{-56,-234,12,324,-12,53,0,234,1,12,72}
{6,34,2,235,234,234,342,324,234,234,234}
Returns: 26
Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RangeSquaredSubsets with a public method long long countSubsets(int nlow, int nhigh, vector<int> x, vector<int> y) · 120 test cases · 2 s / 256 MB per case