m e
n com um algoritmo que tem tempo de execução proporcional a
mn. Lembremos que n é o número de pessoas e que
executamos cada m-ésima pessoa ainda viva.
O desafio, valendo meia-dúzia de Toblerones, é encontrar um algoritmo
com tempo de execução proporcional a n log n (em particular, isto
é independente de m). Note que, por exemplo, se m é
algo como raiz quadrada do número de pessoas, este algoritmo é muito mais
rápido que aquele visto em sala, pelo menos para um número grande de
pessoas.
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Mon Mar 1 02:45:48 EST 1999