rng_58's blog

The hardest problem I've ever seen

By rng_58, 8 days ago, In English.

Hello. Today I want to tell you about the hardest problem I've ever seen.

I found the problem four years ago when I entered a university. The problem was used in Japanese Domestic Contest of ICPC. When I checked previous year's problemset before my first domestic contest, I found one problem that looked very scary: statement.

I doubted my eyes. What does it say? Tighten Up??? Does it really ask us to tighten up a string on a computer??? Can you come up with a solution that works in finite time? The problem looks extremely scary even if we ignore the time limit. This problem was used in a 3-hour contest. You don't have time to go to "Tokyu Hands" (a famous Japanese shop that sells various kind of things) and buy strings and pins to simulate it manually! (I've heard a horrible rumor that someone solved this problem by actually simulating the process by a program...)

By the way, yesterday I participated in a Russian contest called Open Cup with wrong and EnumerativeCombinatorics. It was an interesting experience — we participated in the contest from Makuhari Parking Area (a small shopping mall attached next to a highway). The food court was a good place to participate in the contest. You can check the statement here and the standings here.

Please check problem B. In short, this problem is equivalent to "You are given a string (unlike Japanese problem, this time this is a closed polyline) and pins. Check whether you can shrink the polyline into a very small circle that doesn't contain pins." If you want to try these problems by yourself, please stop reading this post. I'll describe solutions of these problems.

First let's try to solve the Open Cup's problem. At first we thought the problem was easy (but our initial attempt turned out to be wrong). The solution is "Yes" if and only if the closed polyline contains at least one of the pins. (Here "contain" means — You can compute the angle of rotation around each pin. This is always a multiple of 2 * PI. If this value is 0, the polyline doesn't contain the pin, otherwise the polyline contains the pin.) Can you find counter examples to this solution? We constructed a counter example by using PET bottles and a rope.

The correct solution looks as follows: Assume that no two points share the same x-coordinates (Otherwise you can rotate the entire shape). Let N be the number of pins. Let's draw N vertical lines that pass through one of pins. You can find 2N half-lines in total ("upper" part and "lower" part for each line). The polyline crosses these half-lines in some order. The picture on the top shows the initial configuration. The polyline crosses half-lines in the order . After "shrinking", the polyline will look like the picture on the bottom, and the sequence of crossings will become .

By "shrinking" the rope, we can erase two adjacent equal numbers. This process can be easily simulated by a stack. The answer is "Yes" if the stack becomes empty.

This is a big hint for "the hardest problem". When we fix the positions of the pins, two positions of strings are topologically equivalent if and only if the crossing sequences are same (after removing two consecutive equal numbers repeatedly). For example, let's solve the case on the picture on the top. The crossing sequence is . After removing equal numbers, the sequence becomes . Now we want to find the shortest possible length of the string that has this crossing sequence (picture on the bottom). This is a straightforward DP problem (The complexity is O(n2m2), but turned out to be fast enough). Finally we solved "the hardest problem" without being crazy.

I uploaded my solution of this problem to ideone. See you!

note: the above blog is originally shared by rng_58 and cached.