PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal
DIFFICULTY -
Medium
PREREQUISITES -
Basic math
PROBLEM -
Given a grid with N line segments which are either horizontal or vertical. You have to minimise the maximum time taken by the line segments to attain a configuration in which all the line segments pairwise intersect each other. In one second a line segment moves one unit in horizontal or vertical direction.
QUICK EXPLANATION -
It can be proven that all the line segments should have a common intersection point if we want to satisfy the condition of intersection of all line segments pairwise.
Because the size of the grid is small, so we can iterate over all the cells and calculate the movement required by the line segments if that cell is considered as the intersection point.
EXPLANATION -
There are 2 cases possible in this problem, we will prove the fact that a common intersection point is there of all the line segments for the 2 cases seperately.
Case 1 - All the lines are only of one type, i.e either horizontal or vertical.
We will prove for horizontal lines here, similar logic can be extended for vertical lines by the reader.
If all the lines are horizontal we can clearly see, that they should have the same Y coordinate, let it be y. So now the question is reduced to this -
Given N line segments from x1_{i} to x2_{i}, prove that if they have to pairwise intersect, then they will all cover a point X in common.
This can be proved inductively, let there be a point X be in common for the first N - 1 line segments, now when we add the N_{th} line segment, we need to move it such that it intersects will all the previous N - 1 line segments. Let us arbitrarily assume that this line segment lies entirely to the left of X coordinate from a to b where b < X but still intersects with all the line segments. This means that it will not be able to intersect with any line segment which lies completely to the right of the coordinate X - 1. Meaning, that there should be no line completely right of the X - 1 coordinate. This means that all the previous N - 1 line segments also intersect at the point X - 1. Now this logic can be extended further to prove that all the previous line segments should also intersect at X - 2, X - 3, ... upto b. Therefore the new X for N line segments is b. Similar logic can be used in case we assume that the new line segment lies entirely to the right of X, i.e X < a
Case 2 - There are both the types of lines, horizontal as well as vertical.
Assume that you have the optimal configuration, then pick one horizontal and one vertical line arbitrarily from this configuration and let them be \alpha and \beta respectively. Let the intersection of these 2 lines, i.e. \alpha and \beta be at point A. Now we can carefully observe that the remaining horizontal lines in this configuration, i.e. except \alpha, should be intersecting with \alpha as well as \beta. These horizontal lines will have the same X coordinate as \alpha and if they do not pass through point A, then they cannot intersect with \beta, which contradicts the fact that this is an optimal configuration. Similarly, all the vertical lines should also pass through point A.
So now the solution is to simply try to fix each point as the common intersection point and calculate the cost of moving each line segment such that it coincides this common intersection point. And the maximum of all the costs for the different line segments will be the answer for that particular intersection point.
Calculating the cost to move a line segment so that it coincides with a particular point is pretty easy. In case of a horizontal line segment we first move it to the same Y coordinate, and then if the X coordinate of the intersection point lies outside the range of the line segment then we move the line segment such that corner point of the line segment which is nearer to the intersection point coincides with it. This can be done with basic math in O(1)
You can refer to this C++ code for more details -
#include "bits/stdc++.h"
using namespace std;
const int N = 55;
int n;
int X1[N], X2[N], Y1[N], Y2[N];
int calc2(int x, int x1, int x2){
if(x1 > x2) swap(x1, x2);
if(x >= x1 and x <= x2) return 0;
else return min(abs(x - x1), abs(x - x2));
}
int calc1(int x, int y){
int dist = 0;
for(int i = 1; i <= n; i++){
if(X1[i] == X2[i]){
dist = max(dist, abs(x - X1[i]) + calc2(y, Y1[i], Y2[i]));
}
else{
dist = max(dist, abs(y - Y1[i]) + calc2(x, X1[i], X2[i]));
}
}
return dist;
}
void solve(){
cin>>n;
for(int i = 1; i <= n; i++){
cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
}
int ans = INT_MAX;
for(int i = 1; i <= 50; i++){
for(int j = 1; j <= 50; j++){
ans = min(ans, calc1(i, j));
}
}
cout<<ans<<endl;
}
int main(){
int t;
cin>>t;
while(t--) solve();
}
Time Complexity -
The time complexity of the solution per test case is O(50 * 50 * N) , where N is the no. of line segments. Therefore the total time complexity is O(T * 50 * 50 * N) , which is roughly 50^{4}
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555