Evolution in Parallel

First figure out how to determine whether one string can evolve into another. This is a caterpillar walk across both strings. If the letters at the indices at the two strings don't match, increment the pointer in the longer string until they do. If you get to the last letter of both and they match, you have an edge in your graph!

Naive solution:

1. Build whole graph using method above
2. Do some hand wavy graph analysis to find if there are two node-disjoint paths

You don't even need to figure out the wavy hand part to know this won't work. Building the graph takes n^2*l time, or 4000^3...too slow.

Smart solution: We know the graph has to go in length order...do it like that!

1. sort nodes by length
2. put current generation at top of tree
3. add two pointers to current generation: chain 1 and chain 2
4. take each node in sorted list
   • it has an edge to chain 1, add it to chain 1, and move the chain 1 pointer to the new node
   • if there is no edge to chain 1, check for an edge to chain 2. If there is, add to chain 2 and move pointer
   • if no edge to chain 2 either, evolution fails

Key intuition: Edges are transitive, that is, if A->B->C, then there MUST be an edge A->C. That being the case, there is no reason for the single branch we're allowed in the tree NOT to occur at the root. That means this

    *
   /
  *
 / \ 
*   *

can be translated into

   *
  / \
 *   *
 |
 *

So if we're going in order, and an edge doesn't go along the end of our current chain 1, it must go on chain 2, which can always start at the root.

Further, if a vertex fits into either chain, it doesn't matter which we assign it to, since again, due to the transitive property. We can remove a node in a valid chain and the remaining chain is still valid.

We do at max 2 comparisons for each vertex. therefore runtime is O(n*l)

Note: the official solution seems rather more complicated....so perhaps there is something i'm misunderstanding about the nature of the problem...