SNDISCUS - Editorial

basic-math
editorial
greedy
proof
snckpb17
sndiscus

#1

PROBLEM LINK:

Practice
Contest

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* == X2*){
			dist = max(dist, abs(x - X1*) + calc2(y, Y1*, Y2*));
		}
		else{
			dist = max(dist, abs(y - Y1*) + calc2(x, X1*, X2*));
		}
	}
	return dist;
}

void solve(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>X1*>>Y1*>>X2*>>Y2*;
	}

	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


#2

This problem can be solved with complete search on the 2-d coordinate, for values of x,y between 1<=x,y<=50.

Link to my solution:-

https://www.codechef.com/viewsolution/13971636

PS:- I have no karma.


#3

I’ve implemented this differently and it correctly solves the sample questions and anything I could come up with on paper, but was marked as wrong following submission.

My solution is here: https://www.codechef.com/viewsolution/13960271

Could you please inform me of a test case that produces the incorrect output?

@tony_hager has provided an test case which my program fails. Thank you!


#4

I have implemented in similar way. But I am getting wrong submission.
My code: https://www.codechef.com/viewsolution/13972948

Could you please tell me where I am going wrong?


#5

Try this test case if you get WA:

1
3
36  18  47  18
29  33  29  6
49  12  19  12

My program answers 4, which is wrong. The right answer is 5.


#6

Is the grid infinite in this question?


#7

@prakhar_26 The grid is infinite in the question. But since the position of snakes lies between (1x1 to 50x50)
as in the constraints its given 1 <= x <= 50 and 1 <= y <= 50, where x and y denote the position of head/tail of a snake, it stands to reason that the common point of all the snakes (with minimum time to reach there) will lie inside 1x1 to 50x50.
So you only need to check within the bounds 1 to 50. A 1-50 brute force checking will work perfectly fine here.
You can make it more efficient by doing the loops from minX to maxX and minY to maxY instead of 1 to 50.

My sol:


[1]


  [1]: https://www.codechef.com/viewsolution/13969410

#8

Just asking – Can this problem be solved using line sweep algorithm??


#9

I misread the problem the first time. Thought all snakes have to be connected as one component and not pairwise connected. Anyone can tell how to solve if thats the case ??


#10

you deserve…


#11

I was asking because I was thinking of some other non-brute force solution.


#12

Maybe a two-way binary search would work. Choose a point P( (maxX-minX)/2, (maxY-minY)/2 )

Find the minimum neighbor (get the time taken for this cell), if this minimum is equal to your current (time taken for current cell), then you’ve arrived at the minimum point. Else move to the corresponding cell using binary search.

111
101
111
  1. if you’re at 0, and min is at bottom right, new minX would be (maxX-currX)/2 and new minY would be (maxY-currY)/2.
  2. if min is on the right, minY & maxY would remain same, but minX will change.
    I haven’t tried this, but this should work.

#13

@arvindpunk Are you sure binary search will work ?? Cost space may not be strictly increasing or decreasing . I think 2 way ternary search may work.