## J: Worms

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.

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.