роблема (Сколько кошек нужно выбросить из здания, чтобы определить максимальный этаж, на котором такая кошка выживет. На самом деле довольно жестокий), имеет принятый ответ со сложностью O (n ^ 3). Проблема эквивалентна этомуGoogle Code Jam, который должен быть разрешен для N = 2000000000.

Похоже, что решение O (n ^ 3) недостаточно для его решения. От глядяна странице решенийРешение jdmetz (# 2) выглядит как O (n log n). Я не совсем понимаю алгоритм. Может кто-нибудь объяснить это?

редактировать