Este problema (Quantos gatos você precisa jogar fora de um prédio para determinar o piso máximo em que esse gato sobreviverá. Muito cruel, na verdade), tem uma resposta aceita com complexidade O (n ^ 3). O problema é equivalente a issoGoogle Code Jam, que deve ser solucionável por N = 2000000000.

Parece que a solução O (n ^ 3) não é boa o suficiente para resolvê-la. De olharna página de soluções, a solução de jdmetz (# 2) parece ser O (n log n). Eu não entendo bem o algoritmo. Alguém pode explicar isso?

Editar