LA 3531

From Algorithmist
Jump to navigation Jump to search

LA 3531 - Word Rings[edit]


Given is a set of words. A word ring is a sequence of words such that each word begins with the last two letters of the previous one (and the first word begins with the last two letters of the last word).

Find the maximal average word length a valid word ring can have.


Consider a graph where vertices correspond to pairs of letters. Each word corresponds to a weighted directed edge in this graph.

We will use binary search on the interval [0, maximum word length] to find the answer.

We need to be able to answer the following question: "Does our graph contain a cycle with average edge length greater than W?".

This can be checked as follows: Modify each edge length from (say) x to W-x. Now we want to check whether our graph contains a negative cycle. This can be done using the Bellman-Ford algorithm. (Add a new "source" vertex v, connect it to all other vertices and check for negative cycles reachable from v.)


The solution presented above is not optimal, but it was enough to get accepted in the contest. A solution checking for negative cycles using the Floyd-Warshall algorithm timed out.

For a faster algorithm, see Exercise 24-5 (page 617) in Introduction to Algorithms by CLRS (2nd Edition).