PROBLEM LINKS:
Author: Praveen Dhinwa
Primary Tester: Hasan Jaddouh
Editorialist: Aulene De
DIFFICULTY:
Easy
PREREQUISITES:
Plotting points on a 2d-grid
PROBLEM:
Given the starting and ending points of two snakes, determine if the two snakes form a connected component without having a vertex with degree greater than 2 at any point.
Let x11, y11, x12, y12 define the starting and ending points for the first sighting. Similarly, let x21, y21, x22, y22 define the same for the second sighting.
QUICK EXPLANATION:
All solutions lie under the following conditions -
- Same X-coordinates across all 4 points, overlapping Y-coordinates
- Same Y-coordinates across all 4 points, overlapping X-coordinates
- Overlapping end-points
EXPLANATION:
We start by sorting the points of each snake sighting by their X-coordinate and breaking ties with their Y-coordinates.
After that, we try to think of cases where our answer can be true. This part is probably where the problem gets a little easier: remember that little condition we put up there, the one that said “The degree of a vertex should not be greater than 2”? Well, that condition makes this problem simple, as senpai will show you now.
Now, why is this little condition so important? Well, try to think of some cases where this condition is false and plot them on a paper. Come on now, think!
Notice something? Well, if we do plot them on a graph, we can clearly see that the
case where the degree of a vertex is greater than three is when the two snake sightings are perpendicular to each other… something like this.
Right, so if the two snake sightings are perpendicular to each other and intersect at some vertex… the degree of that vertex will be 3. However, can we think of a case where the degree is 2?
Here’s a hint: What if the sightings are perpendicular to each other at the end-points?
Well, we do get a common vertex, but the degree is 2! Got it right? Awesome. Take this virtual chocolate chip cookie.
Okay, now what? Well, there is another case where the conditions given in the statement are fulfilled. What if both of the sightings are parallel to each other and have (an) overlapping vertex/vertices? Something like… this?
Notice something? There’s no vertex with a degree greater than 2, and all conditions for our graph to be valid are fulfilled.
Well, turns out, if there is an overlapping X-coordinate when the Y-coordinates of all points are the same, our solution is valid!
Could we use this to find another case? What if all 4 points have the same X-coordinates?
In this case, we just need to check if there are overlapping Y-coordinates. Outside of these 3, there will be no sightings that fulfil the conditions required for our graph to be valid.
Thus, to summarize, we have established 3 conditions under which all our possible solutions lie -
- Same X-coordinates across all 4 points, overlapping Y-coordinates
- Same Y-coordinates across all 4 points, overlapping X-coordinates
- Overlapping end-points
PS: Notice something? All three of the images I used were directly from the problem statement’s sample test data. A lot of the time, since problem-setters are very mischievous, they leave little tid-bits for you to munch on. Always be on the look-out for these.
PSEUDOCODE:
if y11 == y12 && x21 == x22
if x12 == x21 && (y11 == y21 || y11 == y22)
ans = 1
if x11 == x21 && (y11 == y21 || y11 == y22)
ans = 1
if y21 == y22 && x11 == x12
if x22 == x11 && (y21 == y11 || y21 == y12)
ans = 1
if x21 == x11 && (y21 == y11 || y21 == y12)
ans = 1
//Case 3: Row is the same (overlaps)
if y11 == y12 == y21== y22
if |x12 - x11| + |x21 - x22| + 2 > max ( |x22 - x11| , |x21 - x12| ) + 1
ans = 1
//Case 4: Column is the same (overlaps)
if x11 == x12 == x21 == x22
if |y12 - y11| + |y21 - y22| + 2 > max ( |y22 - y11|, |y21 - y12| ) + 1
ans = 1
SOLUTIONS:
Editorialist’s solution - https://pastebin.com/GkRsLWFz