A 26x26 week

First of all, let's come back to the Grand Prix of Southern Caucasus which rounded up the 2015-16 season of the Open Cup on the week before the last one but had results published only last week (results, top 5 on the left). Team Havka-papstvo ended the season on the highest possible note, solving all problems except the most difficult one, and doing it almost without bugs — great job!

I still have no idea how to solve the aforementioned most difficult problem B — maybe the readers of this blog can help? The problem statement is extremely simple: you are given two strings of the same length consisting of lowercase English letters, and want to transform the first string into the second one. You are allowed operations of two kinds: changing one character into another takes 1 second, and changing all occurrences of some letter into some other letter (the same for all occurrences) takes C seconds. What is the fastest way to do the required transformation?

The strings have at most one million characters, but that's not really important since what matters is how many times each of 26x26 (old letter, new letter) pairs appears.

Since this was the last round of the Open Cup season, the final standings of the cup are now finalized (results, top 5 on the left). Unlike last year, most (7 out of 10) top finishers are coming to the ACM ICPC World Finals in Phuket, which looks to be very exciting!

TopCoder Open 2016 Round 1C on Wednesday presented the last opportunity to qualify for Round 2 and stay in contention for the finals in Washington, DC (problems, results, top 5 on the left). Four top competitors on the scoreboard have solved all three problems, but krijgertje was much faster in doing so — congratulations!

Codeforces Round 349 offered an opportunity to start the weekend competitively on Friday night (problems, results, top 5 on the left, analysis). Problem D was a nice exercise about implementing a problem with many possible cases in such a way that (almost) no case analysis is present in the solution. It went like this: you are given four points on the plane. You can shift each point either horizontally or vertically, but not in both directions. Different points can be moved in different directions — for example, three points can be moved vertically and the fourth one horizontally. Your goal is to get the points to become the corners of an axis-parallel square, while minimizing the maximum distance traveled by one of the points.

Finally, Google Code Jam 2016 Round 1B on Saturday allowed those who failed a problem in Round 1A a second chance (problems, results, top 5 on the left, analysis). ikatanic shared the first place with rng..58, but he has also appeared in the top 5 in another contest this week, so he wins by tie-breaking :) Congratulations to both!

In my previous summary, I've mentioned the 0.636 problem: you are given 2n points on the plane, no three points on the same line, and a matching between them – n segments connecting the points to each other in such a way that each point is the endpoint of exactly one segment. Your goal is to find another matching with an additional property: the segments must not intersect. That would be a classical problem, but here there’s an extra constraint that changes the problem completely: the total length of the segments in your matching must be at least 0.636 (zero point six three six) times the total length of the segments in the given matching. n is at most 100.

The first step in solving this problem is figuring out where does the strange number 0.636 come from. It's funny that just googling that constant yields the answer: this number is slightly less than 2/π, and that, in turn, is the expected length of a projection of a segment of length 1 onto a random line.

This leads us to the first step of the solution: if we pick a random line, and project our matching onto that line, then the expected total length of the projection will be 2/π times the total length of the original matching. Because of this, we can try several random lines and quickly find a line L with projection that's at least 0.636 times the total length of the original matching.

How does this help? Our goal now will be to find a non-intersecting matching with total length greater than or equal to the total length of this projection. Since the total length of a matching is greater than or equal to the total length of its projection, it is enough to find a non-intersecting matching with a projection to the same line L that it greater than or equal in length to the projection of the original matching. And for that, in turn, it is enough to find a non-intersecting matching with a projection to the same line L that has the maximum possible total length.

Which matchings between 2n points on a line have maximum possible total length? This is a reasonably easy question: it's those matchings where the left end of each segment is among the n leftmost points on the line, and the right end of each segment is among the n rightmost points on the line. Moreover, any such matching has this largest possible total length!

Which reduces our problem to the following: we have 2n points on the plane, n of them colored blue (the ones with n leftmost projections on L) and the remaining n colored red, and need to find any non-intersecting matching connecting those points, which is a well-known task with many possible solutions. One solution starts with any matching and then "flipping" intersecting segments until there are none (this will end in finite time since the total length constantly decreases); another takes advantage of the fact that the groups of n blue and n red points are separated from each other in our case, and thus we can find a common tangent to their convex hulls, pair the corresponding red and blue points, and repeat.

Thanks for reading, and check back next week!