CHEFSQUA-Editorial

[djdolls]

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

ad-hoc, basic geometry

PROBLEM:

Given a set of lattice points, find the minimum number of points that should be added to this set such that there exist at least one square with vertices on the points of the extended set.

EXPLANATION:

Even though it is not mentioned in the problem statement that all points of the set are distinct, and we are only interested in non-degenerate square (square with non-zero size), the test cases had only distinct set of points. Nevertheless, allowing degenerate square does not make the problem any harder. We can compute the minimum number of addendum points to create a degenerate and non-degenerate square, and then take the minimum of the two.

Degenerate Squares:

A degenerate square will have all four vertices at the same location. Hence, we just need to find the frequency of the point that occurs most number of times in the set. If the frequency x is >= 4, then we already have a degenerate square and the answer should be zero, otherwise we need to add (4 - x) copies of this point to get a degenerate square.

Non-Degenerate Squares:

Now, we can assume that all points in the set are distinct. We can first consider some basic cases:

1. If the set is empty, then we need to add 4 points.
2. If the set has only one point, then we need to add 3 points to make a square
3. If the set has only two points then we can add two more points to make a square.

The only interesting case is when we have 3 or more points, in which case the answer should be 0, 1, or 2. We only need to check, if there is already an square in the set (in which case the answer should be zero), or if there are three vertices of a square present in the set (in which case the answer should be 1). If none of the two cases hold, then the answer must be 2, as we can always pick two points from the set and add two more points to make a square (explained in the next section).

Extend Square with Two Points:

Suppose we have two points A (x1, y1) and B (x2, y2), and we want to create a square whose edge is the line segment joining the two points. Let us call this square ABCD, so we need to find the co-ordinates of C and D.

In a complex plane, the ray segment AB can be represented as
AB = (x2 - x1) + i (y2 - y1)

Since the length of AB and AD is the same and the angle between them is 90 degrees, the ray segment AD can be obtained by rotating AB to 90 degrees. In other words
AD = AB * (cos 90 + i sin 90)
AD = -(y2 - y1) + i (x2 - x1)

which can be used to compute the co-ordinate of D, i.e.,
D = (x1 - (y2 - y1), y1 + (x2 - x1))

Also note that the ray segment AD and BC are the same in the complex plane, hence we can use the same to compute the co-ordinates of C, i.e.,
C = (x2 - (y2 - y1), y2 + (x2 - x1))

Note that, in the above explanation we rotated AB to clockwise by 90 degrees. On the other hand, if we rotate AB anti-clockwise by 90 degrees, we will find a different square.

Check if Three/Four Vertices of Square Exist in the Set:

If there are three or more vertices of the square are present in the set, then two of these points would be the consecutive vertices of the underlying square. Hence, we can iterate through all pair of points in the set, create a square with the two points making an edge of the square, and check how many of the remaining vertices (which we can compute as explained in the previous section) of the square exist in the set. If for any pair, we have both remaining points in the set, then we already have a square. If for any pair, we have one of the remaining points in the set, then we have three vertices of the square.

Note that, one must consider both squares that can be formed by considering the line segment joining the two points as an edge.

In order to test the membership of a point in the set, one could use a set (which has O (lg N) query time), or a hash table with a properly chosen hash function (which will have O (1) amortized query time).

Time Complexity:

O (N²)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

[abcdexter24]

I first saw this problem, it was not that hard but the thought of brute-forcing at (N^4) would give tle. It then hit me that iterations were O(N^2).

Initially I was implementing a hashmap using vectors : vector<vector > points( num ,vector( num , 0)); SIG-ABRT solution where num is size.

But then I thought of putting points as pair<int,int> with O(logN ) retrieval using either MAP or SET. I used set as it was easier to implement in this case.
And overall complexity was O(N^2 logN), after runtime errors and countless wa ( All tries ) I succeeded

http://www.codechef.com/viewsolution/5142562 ACed solution

[pranjalranjan]

I did the searching using a hashtable. http://www.codechef.com/viewsolution/5105263

[abcdexter24]

great, you made a class and struct to implement hashtable. You could have use a map of int to int for the same

[shiva1k95_10]

Hey, I also did the O(N^2) approach with the hash table, but i still got TLE, can someone please tell me why?? http://www.codechef.com/viewsolution/5139376

oh, and I aslo used make_pair for hash table with two keys, could that be the reason for TLE??

[pranjalranjan]

Yes that thought struck me later. After i solved the problem so just took it easy

[kihsuak]

Can someone help me find what’s wrong with this approach ?

[avinash235]

I considered each pair of points to be the end points of a diagonal and then tried to find out the other two points. Sourced from [here][1]. Can any one explain how my approach was different from the above given approach?
I got AC for my

[2]


  [1]: http://math.stackexchange.com/questions/506785/given-two-diagonally-opposite-points-on-a-square-how-to-calculate-the-other-two
  [2]: http://www.codechef.com/viewsolution/5050170

[shiva1k95_10]

Here, each edge i.e. each pair of points was considered, note that for one line as an edge, there can be two possible squares, using vector algebra, the coordinates of the “supposed to be squares” were calculated, and then checked whether they were present via a hash table

[pranjalranjan]

Actually the above approach considers the two points to be the edge of a square and then finds out the remaining two using rotation theorem. You must understand that there can be many possible ways to solve a problem. Even i solved it by considering them to be diagonal points as its easier and eliminates unnecessary searches. So just that!

[damn_me]

@djdolls The practice link above links to the contest problem.

[damn_me]

Can someone please tell the mistake with this one. The code is giving TLE. I am using a map which maps pair of coordinates to a boolean value which checks for the existence.

Also, the problem can be solved this manner: coordinates can be generated using distance formula as the sides are equal and since the sides are perpendicular we can find the points using slope i.e. product slopes of any two perpendicular lines is -1. However, we’ll need to check for the possible points out of the four points we’ll get in the end by this method.

[damn_me]

Solved my problem from here http://discuss.codechef.com/questions/53029/tle-in-chefsqua .
Never knew even this [] and insert difference can change a TLE to AC!! Nice and easy question…

[thezodiac1994]

O(2nlogn + 2n^2 * log n) using Binary search after sorting gave TLE on my implementation. So I used 3 hash tables (to avoid collisions - though one good/unique hash funcn is enough) to get AC with O(n^2 + 3n). IMO, this should have been tagged easy-med.

[nisargshah95]

I agree the ‘easy’ difficulty does not justify the problem.

[grv95]

I followed a quite naive procedure to discover two line segments of equal lengths sharing a common end point and then checked if they are perpendicular or not.

If they are then see if the vertex that forms a square with the above line segments exists or not.

I really expected a TLE on the solution but somehow got AC in the first go.

my solution

[rushilpaul]

I tried 2 different solutions using both a set and a hashtable and used exactly the same logic give above. Both were taking more time than expected!

[shivam1511]

It was sad to see wrong answers being accepted.

Many accepted solution gave answer 2 for the following test case-

4

0 1

1 0

0 -1

-1 0

The answer is obviously 0. My ac solution this gives 2!

[cauchy]

Thanks!!I also even don’t knew [] and find can change a TLE to AC!!

[ma5termind]

Hello coders,

Hope you all are doing well.

I solved this problem during the contest but still wants to ask something .

I divide the problem in the following two cases.

1 . When the selected points are on the same axis (either on axis parallel to y axis or on axis parallel to x axis). This case was very easy to handle.

2. Now, when the points are not on the same axis . I thought there will only exist a square if the two points are diagonally related it means that there are on the axis which is at 45 degree to the X axis or Y axis. I worked out this for number of example and finds that the observation is correct. Is this ??

I also want to ask you that suppose we have a set containing these two points (1,1) , (2,3) then any one can tell me rest two points with which these two points can form a square.(I think real points were not allowed. Am i missing somewhere Please help!!).