*n*<=2000 points on the plane such that no three points lie on the same line. Each point has an integer label between 1 and

*n*, and all labels are distinct. Your goal is to rearrange the labels in such a way that the

*i*-th point has label

*i*. You are allowed to take any two points and swap their labels, but when you do that you must draw a straight line segment connecting those two points. The segments you draw must not intersect except at their endpoints (in particular, you are not allowed to draw the same segment twice).

The key trick to make progress in the problem is to find a less general, but still non-trivial case which we can solve. It turns out that such case is the one when the initial labeling of points forms a single cycle, for example: point 1 has label 2, point 2 has label 3, and so on, until point *n* which has label 1. In this case we can solve the problem using only the swaps that include point 1, and therefore their segments will not intersect: we start with labels 234...*n*1. We swap the labels of points 1 and 2, and we get 324...*n*1. We swap the labels of points 1 and 3, and we get 423...*n*1. We continue with swapping the labels of points 1 and 4, and so on, and eventually we get *n*234...(*n*-1)1, and finally we swap the labels of the first and last points to get the identity permutation. Note that our choice of point 1 as the "pivot" of all swaps was arbitrary, and we could do the same with any other point.

*before*using the above approach to make sure they do! More specifically, let's assume our points are sorted by angle with respect to point 1. The above solution will only draw segments between point 1 and other points. Therefore we are free to swap the labels between adjacent points in this sorted order, as those segments will not intersect each other and the segments to point 1.

The initial permutation has some number of cycles, and whenever we swap two elements from different cycles they merge into one. While we have more than one cycle, we can find two adjacent points in the sorted order that belong to different cycles, and swap them to merge those cycles. We repeat this until we have just one cycle remaining, and then apply the single-cycle solution.

There are some additional small details to be figured out, which you can find in the official editorial. I could not solve this problem myself, in part because the space of possible approaches is so vast, and yet most of them do not seem to work. I've checked the solutions for this problem from the top finishers, and they all seem to use this approach. In fact, I'm really curious: is some fundamentally different solution possible here? If not, does there exist some intuition why?

Thanks for reading, and check back next week.

I'm the one who ask you the meaning of titles in the last two blogs. Today I can finally get the meaning of it without asking again :)

ReplyDeleteYour blog is really attractive and meaningful. Thanks very much for sharing it to the community.

Yayyy the legend is back. Thanks for the blog and super hard problem.

ReplyDeleteJod

ReplyDeletePetr, you created SHIBA2？https://twitter.com/PetrMitrechev.

ReplyDeleteNo, not related to me in any way.

Delete