2007 North American Computational Linguistics Olympiad

Solution to the problem

a) It is more efficient to leave the phone book open because searches for consecutive words in the dictionary would take you to consecutive positions in the phone book. More precisely, because both lists are arranged alphabetically, later words in the dictionary will also appear later in the phone book.Closing the phone book throws away the last searched position, which is a lower bound on the position of the next word, and usually a tight one.
Additionally, with the phone book open, you could perform reverse look-up to skip sections of the dictionary. After searching for Brooks in the dictionary, for example, you could look at the next name in the phone book. If it were Brown, for example, you could skip forward to brown in the dictionary. This saves looking uo all the dictionary words between "brooks" and "brown".

b) The best solution is as follows: One of you starts with 'A', working forward, and the other with 'Z', working backward. In order to avoid frequent checks, agree on an approximate half-way point before starting. When one of you reaches that half-point, announce it, and settle on a new half-point for the remaining portion. Repeart until no words are left.
One starting at 'A' and the other one at 'N', both working forward, is another solution, but not quite as good because you might run out of words in your half before your friend has finished and have to move to a different part of the dictionary/phone book.

c) The second approach in b) generalizes. Decide in a division into three parts of approximately equal size. When one of you finished the assigned section, divide the remaining work and repeat.