Update: Read my explanation of my solution at https://codeforces.com/blog/entry/75726
I finally solved Reverse from IOI 2003! Here’s a brief summary of what the problem is about:
You have an ancient computer that has 9 registers and 2 operations. Each register can hold an integer from 0 to 255. An
S operation in the form
S A B sets
register[B] = register[A] + 1. A
P operation in the form
P A simply prints
register[B]. You may choose the 9 starting values of the registers.
Your task is, for a given
N, print out
N - 1, …,
0 using as few consecutive
S operations as possible.
This problem was pretty nice in both concept and implementation… if you were fine with 88 points. If you wanted 100 points though, you had to be a lot more creative.
The first major hurdle was the fact that the editorial only described a solution that got 88 points. This meant that you couldn’t even just copy the implementation from the editorial.
The next major hurdle was the fact that Yandex had decreased the limit of consecutive
S operations for one test case (
N = 97) because some IOI 2003 contestant had found a
MAX = 2 solution (the official solution was a
MAX = 3 solution). Other than that, only the
MAX = 4 cases failed for the 88-point solution.
The last major hurdle was how few people had actually solved this problem. Prior to me solving it, only 1 person (Noam Gutterman) had 100 points for it on Yandex. In fact, grandmasters on Codeforces were even doubting the existence of a 100 point solution. Luckily though, I know Noam and was able to ask him for help.
I don’t have the willpower to explain my solution, but it’s a relatively simple extension of the 88-point solution. Here’s my code if you want to decipher it: