In the last week of preparation for the ICPC, one of the problems I solved was particularly challenging. It reminded me of the way that sliding window works in Slotted Aloha protocol, but this is misleading, as the challenge is something else entirely. Because I love problems with this type of trickery, I'm going to write it up! I hope you all think that it's interesting as well.
Problem Statement
This problem is taken straight from the ICPC contest for 2012, in the East Central Region. This is Problem F. The text below is not my own, but copied from the ACM website.
Don and Jan spend a lot of time together on the road. To pass the time, they’ve invented various games they can play, many of which involve license plates and road signs. One of their favorites is Road Series. The object is to find the number 1 on some sign, then 2, then 3, and so on. When they get to two digit numbers the two digits must appear directly next to each other on the sign or license plate, and any sign or license plate can provide multiple answers. For example, if they see a sign with the characters “678-43 15”, they can use the numbers 67, 78, 43 and 15 but not 84 (dash between the two digits) or 31 (space between the two digits). They could also use the individual digits 6, 7, 8, 4, 3, 1 and 5 as well as the three digit number 678 (if they got up that high)
When they first started playing the game, they had very strict rules about when you could find a number, namely you weren’t allowed to find a number n until all the numbers 1 through n − 1 were already found. They soon found that this made the game REALLY slow, so they modified the game as follows. First, they called a number n the last complete number if it was the highest number such that all the numbers from 1 to n had been found. (Initially, 0 is the last complete number.)
Given this, Don and Jan allowed themselves to keep track of having seen some numbers beyond the last complete number n, so long they weren’t too much bigger than n. More precisely, they can keep track of which numbers they’ve seen in a window of size w beyond n. This allows them to remember any number they’ve seen up to n + w.
For example, suppose w = 4 and and the last complete number Don and Jan have seen is 19. When they see the following sign:
“Show time at 8:25, no one under 21 admitted”they can use the 21, but not the 25 (since it’s not in the window). If this sign is followed by the sign:
“The FleaBag Hotel, phone 555-2520”they can use the 20, which now makes 21 the last complete number, and thus can also use the 25, since it’s now in the window.
For each testcase, the maximum window length 100, the maximum number of signs seen is 1000, and the maximum sign length is 1000.
Analysis and Solution
At first, this seems like basic slotted Aloha with a sliding window. The implementation is a bit tricky and bug-prone, but it seems like it would be easy. So what's the catch? The problem is that the given string may be of length 1000, and good luck storing a 1000-digit number in memory.
This means we need a trick: when we look through the string, look at only subsequences of a given length, which are within the window size, and disregard the other subsequences. We do this until the the maximum number seen has stopped growing, so we know there is nothing more to be found on the given sign.
So the twist is pretty basic, but really quite clever. As always, you can find the solution on github here.
