Judging the Southeast Region

This was another of the World-Finals-Hard problems (along with Teleport and Lawrence), and another that wasn’t solved by any team.

You can check out the Judge Input, the Judge Output, the main Solving Program, a C++ solution, and another in C++.

Check out the spoiler for a solution outline.

[spoiler]
There’s a lot of words in this problem, but when you pick through them all, it boils down to a highly recursive algorithm with memoizing to keep it reasonable.

Look at the input cell structure of the worm as an array of characters. In C or C++, that’s natural. In Java, it might be easier to deal with it as a char[] rather than a String. Now, write a method fastest( i, j, ch ) which will tell you the least number of days it would take to generate the cells in the array from index i to index j (inclusive) if you start with cell ch. If n is the number of cells in the input cell structure, then the minimum of fastest( 0, n-1, ch ) over all possible starting cells ch is the final answer. So what does fastest( i, j, ch ) look like?

Well, if i==j, then look at the i^th cell in the input structure. If that is equal to ch, then we’re there already – it takes 0 days. If it isn’t, then it’s impossible. We’ll use an unreasonably large number to signify this – say, 10000.

If i<j, then we’ve got to use a rule. We’ve got to look at all rules of the form ch ⇒ A B, and then we’ve got to look at all ways of splitting that substring from i to j in two, and see how long it takes to use A to generate the first part, and B to generate the second part. Since those can happen in parallel, we’ve got to look at the maximum of the two – and then add one, for the day that the ch ⇒ A B expansion happened. We’ll take the best (i.e. smallest) of all of those.

Here’s that idea in pseudocode:

fastest( i, j, ch )
Begin
    If i==j Then
        If structure[i]==ch Then
            result = 0
        Else
            result = 10000
        End If
    Else
        best = 10000
        For Every Rule of the form ch ⇒ A B
            For break = i to j-1 Do
                days = 1 + Maximum( fastest( i, break, A ), fastest( break+1, j, B ) )
                If days < best
                    best = days
                End If
            End For
        End For
        result = best
    End If
    Return result
End fastest

Of course, this is massively recursive - but we can use memoizing to reduce the burden. Create an array memo[i][j][ch] to store the results. Since the initial cell structure is at most 50 cells long, and there are at most 20 kinds of cells, that makes the array at most 50x50x20 in size, or 50000, which is easily tractable. That also means that there are at most 50000 values we need to compute, also tractable. Initialize this array to be all -1's - that will be our flag that the real value hasn't been computed yet. Then, modify fastest like this:

fastest( i, j, ch )
    If memo[i][j][ch] < 0 Then
        Do all that other stuff
        memo[i][j][ch] = result
    End If
    Return memo[i][j][ch]
End fastest

And, that's it. We won't go any further down in the recursion if the value has already been computed.
[/spoiler]