PointErasing
SRM 522 · 2011-05-25 · by lyrically
SRM 522 · 2011-05-25 · by lyrically · Dynamic Programming
Problem Statement
Problem Statement
You are given a int[] y of length N.
The values in y describe N points in the plane:
for each x = 0, 1, ..., N - 1 there is a point at coordinates (x, y[x]).
Krolik is going to perform the following operation repeatedly:int[] containing all possible values of the number Krolik can write down, in ascending order.
Krolik is going to perform the following operation repeatedly:
- Choose two of the remaining (i.e. not yet erased) points, say A and B, with different y-coordinates.
- Consider the rectangle with sides parallel to coordinate axes and points A and B in two opposite corners.
- Erase all points strictly inside the rectangle.
Notes
- A point is strictly inside a rectangle if it is inside the rectangle and does not lie on the border of the rectangle.
Constraints
- y will contain between 1 and 50 elements, inclusive.
- Each element of y will be between 0 and 1,000,000,000, inclusive.
Examples
0)
{ 1, 2, 1, 1, 0, 4, 3 }
Returns: {4, 6 }
Krolik will end with 4 points if Krolik takes the following steps: Choose (1, 2) and (4, 0) to erase (2, 1) and (3, 1). Choose (0, 1) and (5, 4) to erase (1, 2). If Krolik first chooses (0, 1) and (5, 4) to erase (1, 2), 6 points remain and there are no valid moves left.
1)
{ 0, 0, 4, 4, 8, 8, 4, 4 }
Returns: {6 }
2)
{ 522 }
Returns: {1 }
3)
{ 19, 19, 19, 19, 19, 19 }
Returns: {6 }
4)
{ 0, 1, 2, 3, 4 }
Returns: {2 }
9)
{5, 5, 4, 4, 5, 8, 5, 5, 5, 5, 5, 9, 2, 0, 9, 4, 5, 5, 3, 4, 4, 4, 4, 7, 4, 5, 5, 4, 4, 5, 8, 5, 5, 5, 5, 5, 9, 2, 0, 9, 4, 5, 5, 3, 4, 4, 4, 4, 7, 4}
Returns: {9, 10, 11, 13, 14, 15, 16, 18, 19, 20 }
just two copies of #7 glued together
Submissions are judged against all 101 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PointErasing with a public method vector<int> getOutcomes(vector<int> y) · 101 test cases · 2 s / 256 MB per case