LShape
SRM 768 · 2019-10-09 · by Errichto
Problem Statement
This problem is about points in a two-dimensional plane. We will deal with L-shapes: triples of points that resemble the letter L.
Three (not necessarily distinct) points form an L-shape if we can label them A, B, and C in such a way that points A and B have the same x-coordinate, and points B and C have the same y-coordinate. For example:
- The points (0, 3), (1, 9), (1, 3) form an L-shape. If we label them as C = (0, 3), A = (1, 9) and B = (1, 3), we have A.x = B.x and B.y = C.y.
- The points (5, 5), (5, 5), and (5, 5) also form an L-shape.
- The points (1, 9), (1, 9), and (7, 7) do not form an L-shape.
Let a step be an operation in which we change any one coordinate of any one point by 1. The L-score of a triple of points is defined as the smallest number of such steps needed to transform that triple of points into an L-shape.
You are given a set of N points in the plane: for each valid i, the coordinates of one point are (i, y[i]). No two points have same x-coordinate, and no two points have same y-coordinate. Compute and return the sum of L-scores over all N*(N-1)*(N-2)/6 triples of points.
Note that you don't actually move any of the N given points. The L-score calculations for different triples of points are completely independent.
Notes
- Note the unusual time limit.
Constraints
- N (the number of elements in y) will be between 3 and 3000, inclusive.
- Each element in y will be between 0 and 2999, inclusive.
- Elements in y will be distinct.
{4, 9, 3}
Returns: 2
We are given three points: (0, 4), (1, 9), and (2, 3). There is only one triple of points, and its L-score is 2. One way of changing this triple into an L-shape in two steps looks as follows: Move the first point from (0, 4) to (0, 3). Move the third point from (2, 3) to (1, 3). After these two steps we have the L-shape (0, 3), (1, 9), (1, 3). Another optimal strategy is to move the first point from (0, 4) to (1, 4) and then to (1, 3), yielding the L-shape (1, 3), (1, 9), (2, 3).
{0, 1, 2, 3}
Returns: 10
The given four points are (0, 0), (1, 1), (2, 2) and (3, 3). There are N*(N-1)*(N-2)/6 = 4*3*2/6 = 4 triples and their scores are 2, 3, 3, 2, so the total answer is 10. For example, a triple (0, 0), (2, 2), (3, 3) has score 3 and it's optimal to move the point (2, 2) to (0, 3) in 3 moves.
{0, 2, 1, 3}
Returns: 8
Each of four triples has score 2, so the answer is 8.
{6, 2, 3, 0, 1, 4, 7}
Returns: 107
{1400, 200, 1499, 0, 1, 500, 600, 700, 777, 1498}
Returns: 30708
Submissions are judged against all 40 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LShape with a public method long long sumL(vector<int> y) · 40 test cases · 2 s / 256 MB per case