Codeforces Round #102 Problem E

Been a while since the last time I did a writeup. As it has been a relatively long while since the last time I looked into this problem I expected this post to be short in length, but it turned out to be a lengthy one.

The problem is solved only by few. I thought I may at least explain my solution so that whoever tries to solve the problem may, from now on, come by and read this post if they face some difficulty.

As mentioned below, my solution is not, theoretically speaking, a flawless one. Still, it passed the test cases at Codeforces.

Problem Statement

The problem statement introduces us to Greg the Dwarf, who is trying to walk on the surface of a cone. We are asked to find the length of the shortest path between two points A and B on the surface of the cone within an error range of 10-6. The problem has a twist, though. Greg the Dwarf is also able to go on the base of the cone. So we are to find the shortest path not only considering the lateral surface of the cone, but also its base.

Solution Idea

The idea to my solution is pretty straightforward, and is also the approach described by the problemsetter in contest's editorial. We should print the minimum of the shortest path going through the base of the cone, and the lateral-only shortest path alternative. Validity of this approach becomes apparent once we notice that there are three possible cases to one of which all possible inputs belong.

The first case is having both points A and B on the base of the cone. The minimum distance is just the Euclidean distance between the endpoints. The second case is having only one of the endpoints on the base of the cone, and one on the lateral surface. In this case the shortest path has to go through a point where lateral surface and the base of the cone intersect. (i.e. outer rim of the base) The solution in this case finds the optimal point of intersection for the shortest path to go through and calculates the resulting path length accordingly. The third case is having no endpoints on the base of the cone. In this case the shortest path is either lateral-only, or it intersects the base of the cone. (i.e. crossing two points on the outer rim of the base of the cone) In the latter case, the solution again tries finding two optimal points for the shortest path to go through and computes the resulting length of the path accordingly.

Implementation

There are a few points to clarify regarding the implementation of the solution mentioned above. The first thing is how one may compute the lateral-only shortest distance of two points on the lateral surface of a cone. Finding the optimal points on the outer rim for the shortest path to go through is also important.

Shortest Path on Lateral Surface

In essence, cone is a shape made out of a base circle and a sector of a circle radius of which is equal to the slant height of the cone. Considering the cone in this, unwrapped fashion helps quite a bit.

If we can transform the coordinates from the XOY coordinate system, in which points A and B are given to us, to a 2D coordinate system of the unwrapped version of the cone, points A and B just become two points on a circular sector. Then computing shortest path between the two just becomes computing two points on a plane. It is obviously possible to do this. While implementing this, I considered that circular sector was placed on the 2D plane in such a way that its centered on the origin and covers an area in counterclockwise direction starting from x-axis. I then computed the polar coordinates of the points A and B, considering it is easier to put those points on our new, 2D coordinate system using their polar coordinates. After the transformation of polar coordinates to the 2D plane of the circular sector, knowing the new coordinates of A and B, the problem is just that of finding their Euclidean distance.

There is an important case to cover, though. Let's say that circular sector of the cone spans Q degrees such that 180° < Q < 270°. Now, if A has a polar angle less than 45° and B has one larger than 225°, than drawing a straight line from one another that still stays within the sector is impossible. Considering that, in such cases where the shortest Euclidean distance actually steps off of the circular segment that corresponds to the lateral surface of the cone the shortest distance becomes the sum of the shortest distance between point A and the center of the circular sector (i.e. origin of our 2D coordinate system) and the shortest distance between the center of the sector and point B. I am not going to provide any mathematical proofs as to why this yields the optimal result. Still, an intuitive explanation to this method is considering that we are trying to bend the shortest path we initially found so that it stays within the area covered by the circular segment and still has the shortest length possible. You may also visualize this in 3D as Greg the Dwarf climbing to the top of the cone and then going downhill.

Single and Double Optimal Intersection Point

As mentioned above in the section Solution Idea, if only one of the points A and B given as input is on the base and the other on the lateral surface, then the shortest path goes through lateral surface until it reaches some point C at which it crosses from the lateral surface to the base.(i.e. where lateral surface and base of the cone intersect) If we could find such an optimal point C, we could compute the shortest path by summing the lateral surface distance between C and the point, say A, on the lateral surface, and the Euclidean distance between points C and B.

The method I used to find such an ideal point C is binary search. In terms of implementation, I basically considered the polar angle of point C and checked 360 angles around the outer rim of the base for a minimal value. Then, I took the angle Q that yielded the least distance, and did binary search on the interval [Q-1, Q+1] to find the minimum distance.

Why Binary Search Works

Just visualize points A and B on the cone. Now consider the outer rim of the base circle of the cone on which point C is located. On that outer rim there also must be a point D such that length of an optimal path from A to B which goes through D is the largest. (i.e. compared to all the other optimal paths going through other points on that outer rim) The intuitive notion is that the values of the length of such an optimal path from A to B gets smaller as we shift the point intersected on the outer rim from D, towards C. In other words, they are sorted in a way that lets us yield continuously decreasing results for optimal paths as we get close to C, which is why binary search works.

If both of A and B are on the lateral surface, the shortest path connecting them is either exclusively on the lateral surface, or at some point it crosses two points P and R at which the lateral surface and base of the cone intersect. We simply take the minimum out of these two cases. However, computing the second case is a bit hard, as finding optimal coordinates for two intersection points are a bit different than finding a single optimal point. I used binary search to find the two optimal intersection points, as well, but I had to implement it differently as I was looking for two points now.

My implementation of binary search for finding two optimal intersection points was based on doing a binary search on one of the points, say P, and then acting as if I was looking for a single optimal point of intersection R between a point on the base(P) and one on the lateral surface. It was basically doing another binary search within the binary search. Sadly, introducing this sort of nested binary searches caused one side-effect: local minimums.

As explaining why binary search worked I mentioned a continuous and decreasing progression of shortest path values as we get close to the optimal intersection point C. However, if we do a nested binary search, in the interior binary search we may get an entirely different ideal point R for each point P we check during out outer binary search. This prevents the continuous progression of shortest path values, and consequently we can not find a minimal range to apply binary search by simply traversing all 360 angles as we did for the single point of intersection. So how do we find an appropriate range on which we may do a nested binary search so that we may not be dealing with local minimums?

The answer is that we do not. At this step, I used a different approach, and used what is referred to as Monte Carlo method. I basically repeatedly applied the nested binary search on a range endpoints of which I slightly expanded each time. I then considered the minimum value this process yields as the length of the shortest path.

I assigned the initial endpoints of the range I expanded as [N-1, N+1], N being the polar angle of A on XY plane of the 3D coordinate system used in the input. It seems intuitively correct that point P should have a polar angle that is close to one of the points A and B as it would not possibly be shortest if both P and R were far away from both A and B.

Code

I did view all three of my successful submissions to this problem on Codeforces after two months of submitting them, and all of them seemed messy, which is why I am not putting on here. It would only serve to deconstruct the relatively clear explanation of the problem I took this far.

You may still go and check it out for yourselves on Codeforces, though. (the username to look for is, surprisingly, ilim)

In a few days I may put a sanitized version of one of those successful submissions on here, but it is quite unlikely that I will find the time to do so.

Conclusion

This problem was fairly hard for me to solve. It took me a long time to understand why the nested binary search was not working. Also, even though Monte Carlo method is, in many cases, a sound numerical analysis approach to take, I still think it is not the proper way to solve this problem and that there probably is a solution on Codeforces which finds the shortest path with a more solid approach than just repetitively applying binary search on overlapping intervals to get rid of local minima.

I wish I had the time or the eagerness to look into them and tell you about their approaches as well, but unfortunately I do not. I'm also aware that I did not do well in explaining some of the details such as why I assigned intial endpoints of the range (i.e. the one on which I applied repetitive nested binary searches) the way I did. As I mentioned in the beginning, it has been about two months since the last time I looked into this problem, which is why some of the details are not as clear to me as they used to be. Do let me know if you have a better alternative to such portions of this writeup, though, so that others after you may understand it better.

That is the whole point of these writeups, after all.