Hi all! I finally managed to code the solution of this tricky problem, I needed to read the editorial (very hard to follow) and make lot of hard work to get the trick of how to do it so now I want to share my conclusion of how it can be solved properly.↵
↵
The statement says you have a **list of points** with X and Y coordinates. However you need to define whether you will draw each one using its X coordinate or its Y. (and the other will be zero). Formally speaking you can draw each one on the (X,0) or in the (0,Y). The objective is to get the minimum **diameter** of the set of points, defined as the **longest distance between any of them** ↵
↵
We need to note the worst solution would be to check both coordinates for each point (two possibility for each one. This would delay around **2^N * (time to get longest distance in each chance**). As N is 100000 is impossible doing something like that.↵
↵
↵
Imagine then an optimal solution where we have points drawn on X axis. Think about the points that its X coordinate is between **at least** the X coordinate of two points drawn on X axis. Why would we take the risk of drawing these points on its Y coordinate when if we draw it on X coordinate then the diameter would not be affected (because of course the two points drawn on X axis surrounding this point (sorted by X coordinate) have a bigger distance) . So our conclusion if that in an optimal solution the points drawn on X coordinate must be consecutive if we sort points by X (the same applies to Y, if we sort points by Y then the points drawn on Y axis are also consecutive in this kind of sorting). We can express the solution as ↵
Y POINTS — X POINTS — Y POINTS (sorted by X coordinate).↵
or↵
X POINTS — Y POINTS — X POINTS (sorted by Y coordinate).↵
both are totally compatible, you can solve the problem once with any of them and you will get the **same result**.↵
↵
↵
So we need to get the best start point and the best end point for this consecutive points. (sorted by X). We could make an **O(N*N)** algorithm if we try every possibility of the endpoints, but there still is an issue, because imagine we've got two endpoints, x1 and x2, to calculate exact diameter we need a trick because it is impossible by default to get the maximum and the minimum Y coordinate of the other points in O(1) (We would need to do another iteration on the points not used). ↵
The trick, as editorial says, is pretty easy, before we start solving the problem we need to get all the maximum and minimum Y values for each prefix and suffix of the points (sorted by X). You can get it on O(N). So then for example if we have as endpoints point 3 and point 6, (N=10) then the the maximum Y value would be max( MAXIMUM Y VALUE 0 to 2, MAXIMUM Y VALUE 7 TO 9) and the minimum Y value would be min( MINIMUM Y VALUE 0 to 2, MINIMUM Y VALUE 7 TO 9).↵
↵
So this solution needs an O(N) precomputation (that gets on time) plus an O(N*N) algorithm to check every pair of endpoints (and getting the MAXY and MINY of each chance is instantly thanks to p recalculation). With the two X endpoints and the two Y endpoints (MAXY and MINY) we can easy and fast calculate the diameter for each chance.↵
↵
However as N=100000 then **O(N*N)** is not enough. Every problem with N>10000 suggest a logarithmic approach solution (of course with a 1-3 seconds time limit).↵
So there are two things I know that work on a logarithmic basic; segment tree and binary search. In this case we need to implement a **binary search approach** to increase performance to be enough to solve problem↵
↵
Now we'll change the angle of what we were thinking. Instead of thinking about trying pairs of points, we'll develop an algorithm that answers: **it is possible to make the points fit in M diameter**? And here is where the binary property applies. Because if it is possible to make points fit in a diameter of a M value (example=1000), then it is possible to fit them in any higher diameter than 1000. But if it not then it is not possible to make them fit on any diameter lower than 1000. So we need to implement a **binary search** that discovers the value of M were we start to be able to fit the points (The lower value of M that can fit the points).↵
As the problem ask for the square of the minimum diameter we won't make the binary search of the diameter but of the square of the diameter (In the contrary case we'll be obligated to do lots of sqrt() calculations that we know are too slow for this kind of contests and to deal with float numbers). so until now M is the square of the diameter and this does not change the behavior of the binary search.↵
For the lower bound of M we will use the -1 value because zero can be a solution (in case all points are in the same point drawn and 0^2=0) and the higher bound will be ↵
max(10^8*2,10^8*10^8), i don't know who is bigger and it is not important because as the binary search is really fast we can just use LLONG_MAX from <climits.h> or <bits/stdc++.h> and won't change practically the run-time. ↵
↵
So now we need to do the hardest part. How we'll calculate whether is it possible or not the calculate if we can fit the points in a squared diameter of M? (And to do this in better than O(N*N), otherwise the total complexity would be O(N*N*log(N), worse than the original O(N*N))↵
↵
To make things easier we we'll first check two border cases. We'll try to draw all points on X axis and to draw all of them on Y axis. In the first case the diameter would be the difference between first and last point (Remember, we decided to sort points according to X coordinate) and in the second the difference between MAXY and MINY (To get them we can use PREFIX UP TO N-1 or SUFFIX UP to 0, Remember we have precomputed them in a initial O(N) ). if the diameter value of any of those cases is lower than the M value we are trying to see is better then we answer yes, otherwise we need to check cases where some points lie on X axis and some others on Y axis to check whether it is possible. (of course as M is the square of diameter then to compare M and the diameter calculated we need to square diameter calculated rather than making the sqrt(M), DIA*DIA<=M)↵
So now we need to check the other cases. it can be done on O(N) using the famous two pointer technique or in a modest (O(N*LOG(N)) using another binary search that will also fit the time limit, and because it is easier I will develop that method. ↵
Remember that all points that lie on X axis (of course sorted by X) are together. So we'll need to check every **starting point** of the chain going from the point 0 to the point N-1 and then using a binary search calculate the **ending point** of the chain. But because this method will not get all ending points of the chain checked we'll need to also check every **ending point** of the chain and then we'll need to binary search to get its starting point to the left side.↵
↵
So we are checking a starting/ending point and now we need to get the other left/right endpoint to make sure the answer of diameter squared will not be bigger than the M value we are checking. If the point X coordinate distance is bigger than M then is easy to say we can not draw the point on X axis while maintaining diameter lower than M. So this point and all points farther away need to be drawn on Y axis. Also if the distance of this point to the (0,0) is bigger than the distance of the starting/ending point to (0,0) we'll decide to draw this point on Y axis (and so all father points than this one), because otherwise we risk about making the square distance between MAXY and the point or the distance between MINY and the point be bigger than M, and there is no way to make sure if it will or not, so any point that it X coordinate is far away than M from starting/ending point and its distance to (0,0) is bigger than the distance to (0,0) of starting point (shown in editorial as abs(X[point])>abs(X[s/e]) and any point farther than that won't be part of chain so it will be drawn on Y axis. In the contrary case if the point is nearer than M from the starting/ending point and abs(X[point])<=abs(X[s/e]) and any point between this point and starting/ending point will be drawn on X axis because we can to not take the risk of drawing it on Y axis.↵
So using the binary search we have just calculated the starting/finishing point from a finishing/starting point of a chain. All points inside this chain will be drawn on X axis while all others on Y axis. We have deducted that to calculate the diameter of this configuration we only need the endpoints (that its distance squared is lower than M as we avoided to assign two points farther than that in algorithm) and the MINY and MAXY. to calculate both MINY and MAXY of the points drawn on Y axis we'll use the PREFIXES and SUFFIXES max/min Y calculated. As I previously said, ↵
↵
↵
~~~~~↵
_`if we have as endpoints point 3 and point 6, (N=10) then the the maximum Y value would be max( MAXIMUM Y VALUE 0 to 2, MAXIMUM Y VALUE 7 TO 9) and the minimum Y value would be min( MINIMUM Y VALUE 0 to 2, MINIMUM Y VALUE 7 TO 9)._↵
~~~~~`↵
↵
So with endpoints and MAX/MINY we need to see if any squared distance is bigger than M. If for example MAXY-MINY squared is bigger than M then of course this chain possibility can not fit on M. Also if distance squared of starting/ending point (s/e,0) to (0,MAXY) or (0,MINY) is bigger than M then the chain is also **invalid**. The other two diagonals (that would be the endpoint we've just binary searched) does not matter because as abs(X[e2])<=abs(X[s/e]) then it size is equal or less than the other two diagonals we've just tested.↵
So if nothing of those conditions invalidate the M value then we've just found a valid chain that fits on M! **Congrats!** So we return in the function that checks if a squared value of diameter (M) is valid true. ↵
If in there is no solution in any chain (of the ones we checked on O(N(LOG(N)) that fits on M then the function should answer that it is not possible to find a combination of points that fits on squared diameter of M.↵
↵
So that's all we've the method to get the whether we can or not fit the points on squared diameter of M in **O(n(log(n))** and as we'll use it on a binary search between all posible values of squared diameter distances, then the total complexity will be (O(log(MAXDIS)*N*log(N))) plus a precomputation of **O(N)** to get the prefixes and suffixes.↵
↵
**pretty hard** I think haha the editorial was way too short. Ask any question and try to code it, you can also check my submission :) [submission:15849301]
↵
The statement says you have a **list of points** with X and Y coordinates. However you need to define whether you will draw each one using its X coordinate or its Y. (and the other will be zero). Formally speaking you can draw each one on the (X,0) or in the (0,Y). The objective is to get the minimum **diameter** of the set of points, defined as the **longest distance between any of them** ↵
↵
We need to note the worst solution would be to check both coordinates for each point (two possibility for each one. This would delay around **2^N * (time to get longest distance in each chance**). As N is 100000 is impossible doing something like that.↵
↵
↵
Imagine then an optimal solution where we have points drawn on X axis. Think about the points that its X coordinate is between **at least** the X coordinate of two points drawn on X axis. Why would we take the risk of drawing these points on its Y coordinate when if we draw it on X coordinate then the diameter would not be affected (because of course the two points drawn on X axis surrounding this point (sorted by X coordinate) have a bigger distance) . So our conclusion if that in an optimal solution the points drawn on X coordinate must be consecutive if we sort points by X (the same applies to Y, if we sort points by Y then the points drawn on Y axis are also consecutive in this kind of sorting). We can express the solution as ↵
Y POINTS — X POINTS — Y POINTS (sorted by X coordinate).↵
or↵
X POINTS — Y POINTS — X POINTS (sorted by Y coordinate).↵
both are totally compatible, you can solve the problem once with any of them and you will get the **same result**.↵
↵
↵
So we need to get the best start point and the best end point for this consecutive points. (sorted by X). We could make an **O(N*N)** algorithm if we try every possibility of the endpoints, but there still is an issue, because imagine we've got two endpoints, x1 and x2, to calculate exact diameter we need a trick because it is impossible by default to get the maximum and the minimum Y coordinate of the other points in O(1) (We would need to do another iteration on the points not used). ↵
The trick, as editorial says, is pretty easy, before we start solving the problem we need to get all the maximum and minimum Y values for each prefix and suffix of the points (sorted by X). You can get it on O(N). So then for example if we have as endpoints point 3 and point 6, (N=10) then the the maximum Y value would be max( MAXIMUM Y VALUE 0 to 2, MAXIMUM Y VALUE 7 TO 9) and the minimum Y value would be min( MINIMUM Y VALUE 0 to 2, MINIMUM Y VALUE 7 TO 9).↵
↵
So this solution needs an O(N) precomputation (that gets on time) plus an O(N*N) algorithm to check every pair of endpoints (and getting the MAXY and MINY of each chance is instantly thanks to p recalculation). With the two X endpoints and the two Y endpoints (MAXY and MINY) we can easy and fast calculate the diameter for each chance.↵
↵
However as N=100000 then **O(N*N)** is not enough. Every problem with N>10000 suggest a logarithmic approach solution (of course with a 1-3 seconds time limit).↵
So there are two things I know that work on a logarithmic basic; segment tree and binary search. In this case we need to implement a **binary search approach** to increase performance to be enough to solve problem↵
↵
Now we'll change the angle of what we were thinking. Instead of thinking about trying pairs of points, we'll develop an algorithm that answers: **it is possible to make the points fit in M diameter**? And here is where the binary property applies. Because if it is possible to make points fit in a diameter of a M value (example=1000), then it is possible to fit them in any higher diameter than 1000. But if it not then it is not possible to make them fit on any diameter lower than 1000. So we need to implement a **binary search** that discovers the value of M were we start to be able to fit the points (The lower value of M that can fit the points).↵
As the problem ask for the square of the minimum diameter we won't make the binary search of the diameter but of the square of the diameter (In the contrary case we'll be obligated to do lots of sqrt() calculations that we know are too slow for this kind of contests and to deal with float numbers). so until now M is the square of the diameter and this does not change the behavior of the binary search.↵
For the lower bound of M we will use the -1 value because zero can be a solution (in case all points are in the same point drawn and 0^2=0) and the higher bound will be ↵
max(10^8*2,10^8*10^8), i don't know who is bigger and it is not important because as the binary search is really fast we can just use LLONG_MAX from <climits.h> or <bits/stdc++.h> and won't change practically the run-time. ↵
↵
So now we need to do the hardest part. How we'll calculate whether is it possible or not the calculate if we can fit the points in a squared diameter of M? (And to do this in better than O(N*N), otherwise the total complexity would be O(N*N*log(N), worse than the original O(N*N))↵
↵
To make things easier we we'll first check two border cases. We'll try to draw all points on X axis and to draw all of them on Y axis. In the first case the diameter would be the difference between first and last point (Remember, we decided to sort points according to X coordinate) and in the second the difference between MAXY and MINY (To get them we can use PREFIX UP TO N-1 or SUFFIX UP to 0, Remember we have precomputed them in a initial O(N) ). if the diameter value of any of those cases is lower than the M value we are trying to see is better then we answer yes, otherwise we need to check cases where some points lie on X axis and some others on Y axis to check whether it is possible. (of course as M is the square of diameter then to compare M and the diameter calculated we need to square diameter calculated rather than making the sqrt(M), DIA*DIA<=M)↵
So now we need to check the other cases. it can be done on O(N) using the famous two pointer technique or in a modest (O(N*LOG(N)) using another binary search that will also fit the time limit, and because it is easier I will develop that method. ↵
Remember that all points that lie on X axis (of course sorted by X) are together. So we'll need to check every **starting point** of the chain going from the point 0 to the point N-1 and then using a binary search calculate the **ending point** of the chain. But because this method will not get all ending points of the chain checked we'll need to also check every **ending point** of the chain and then we'll need to binary search to get its starting point to the left side.↵
↵
So we are checking a starting/ending point and now we need to get the other left/right endpoint to make sure the answer of diameter squared will not be bigger than the M value we are checking. If the point X coordinate distance is bigger than M then is easy to say we can not draw the point on X axis while maintaining diameter lower than M. So this point and all points farther away need to be drawn on Y axis. Also if the distance of this point to the (0,0) is bigger than the distance of the starting/ending point to (0,0) we'll decide to draw this point on Y axis (and so all father points than this one), because otherwise we risk about making the square distance between MAXY and the point or the distance between MINY and the point be bigger than M, and there is no way to make sure if it will or not, so any point that it X coordinate is far away than M from starting/ending point and its distance to (0,0) is bigger than the distance to (0,0) of starting point (shown in editorial as abs(X[point])>abs(X[s/e]) and any point farther than that won't be part of chain so it will be drawn on Y axis. In the contrary case if the point is nearer than M from the starting/ending point and abs(X[point])<=abs(X[s/e]) and any point between this point and starting/ending point will be drawn on X axis because we can to not take the risk of drawing it on Y axis.↵
So using the binary search we have just calculated the starting/finishing point from a finishing/starting point of a chain. All points inside this chain will be drawn on X axis while all others on Y axis. We have deducted that to calculate the diameter of this configuration we only need the endpoints (that its distance squared is lower than M as we avoided to assign two points farther than that in algorithm) and the MINY and MAXY. to calculate both MINY and MAXY of the points drawn on Y axis we'll use the PREFIXES and SUFFIXES max/min Y calculated. As I previously said, ↵
↵
↵
_
↵
So with endpoints and MAX/MINY we need to see if any squared distance is bigger than M. If for example MAXY-MINY squared is bigger than M then of course this chain possibility can not fit on M. Also if distance squared of starting/ending point (s/e,0) to (0,MAXY) or (0,MINY) is bigger than M then the chain is also **invalid**. The other two diagonals (that would be the endpoint we've just binary searched) does not matter because as abs(X[e2])<=abs(X[s/e]) then it size is equal or less than the other two diagonals we've just tested.↵
So if nothing of those conditions invalidate the M value then we've just found a valid chain that fits on M! **Congrats!** So we return in the function that checks if a squared value of diameter (M) is valid true. ↵
If in there is no solution in any chain (of the ones we checked on O(N(LOG(N)) that fits on M then the function should answer that it is not possible to find a combination of points that fits on squared diameter of M.↵
↵
So that's all we've the method to get the whether we can or not fit the points on squared diameter of M in **O(n(log(n))** and as we'll use it on a binary search between all posible values of squared diameter distances, then the total complexity will be (O(log(MAXDIS)*N*log(N))) plus a precomputation of **O(N)** to get the prefixes and suffixes.↵
↵
**pretty hard** I think haha the editorial was way too short. Ask any question and try to code it, you can also check my submission :) [submission:15849301]
