), частичные суммы строк треугольника Паскаля.

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

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

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

 ripper23415 янв. 2011 г., 11:37
Это может быть перенесено в Алгоритмы, как только это будет:area51.stackexchange.com/proposals/5120/...
 Mark Byers15 янв. 2011 г., 11:29
Объяснение алгоритма кажется мне подходящим вопросом для StackOverflow.
 Peter Taylor17 янв. 2011 г., 09:09
Если вы видите мое последнее обновление моего ответа, я могу сделать лучше, чем O (n lg n).
 Nikita Rybak15 янв. 2011 г., 12:49
Если этот алгоритм былO(n*logn) (независимо от того, какую из трех переменных вы обозначаетеn), это все равно будет слишком медленно.n до10^9.

Ответы на вопрос(2)

Сильно отредактировано из-за исправления вопроса

Рассмотрим функцию f (x, y), которая дает количество этажей, которые вы можете протестировать с ограничением x бросков и y смертей. Если первый бросок приводит к смерти, у вас есть броски x-1 и оставшиеся смерти y-1, так что вы можете проверить f (x-1, y-1) этажей. Если первый бросок не приводит к смерти, у вас есть x-1 бросков и y смертельных случаев, так что вы можете проверить f (x-1, y) этажей выше того, из которого вы бросили. Следовательно, мы имеем рецидив f (x, y) = f (x-1, y-1) + f (x-1, y) + 1. Базовые условия: f (x, 0) = 0 (потому что если Вы делаете даже один бросок, рискуете смертью, поэтому вы не можете делать броски и даже не можете проверить первый этаж), и f (1, x) = 1, где x> 0 (вы должны сделать единственный бросок из первый этаж, потому что если вы бросите с верхнего этажа и получите смерть, у вас не будет результата).

Теперь рассмотрим функцию g (x, y) = SUM 1 <= r <= yxCr, (Это биномиальный коэффициент, х выберите г. Я не думаю, что нотация TeX поддерживается на этом сайте). Утверждение состоит в том, что f (x, y) = g (x, y). Чтобы проверить базовые случаи, рассмотрим, что g (x, 0) является суммой по 0 элементам, так что это соответствует; и g (1, y) где y> 0 дает1C1 = 1. Так что осталось только проверить, что g удовлетворяет рекуррентности.

g (x-1, y-1) + g (x-1, y) + 1, = СУММА 1 <= r <= y-1х-1Cr + СУММА 1 <= r <= yх-1Cr + 1

g (x-1, y-1) + g (x-1, y) + 1 = SUM 2 <= r <= yх-1Cг-1 + СУММА 1 <= r <= yх-1Cr + 1

g (x-1, y-1) + g (x-1, y) + 1 = SUM 2 <= r <= yх-1Cг-1 + СУММА 1 <= r <= yх-1Cr + х-1C0

g (x-1, y-1) + g (x-1, y) + 1 = СУММА 1 <= r <= yх-1Cг-1 + СУММА 1 <= r <= yх-1Cr

g (x-1, y-1) + g (x-1, y) + 1 = СУММА 1 <= r <= y (х-1Cг-1 + х-1Cr)

g (x-1, y-1) + g (x-1, y) + 1 = СУММА 1 <= r <= y (xCr)

g (x-1, y-1) + g (x-1, y) + 1 = g (x, y)

QED

Фактически это может быть получено непосредственно, рассматривая это как комбинаторную проблему. Если мы в полной мере используем каждый бит полученной информации, то каждая возможная последовательность выживания или смерти соответствует разному максимальному полу. Например. для трех бросков одна допустимая смерть, возможна смерть; Выживание смерть; выживание выживание смерть; или выживание-выживание-выживание. Тем не менее, мы должны игнорировать случай, когда нет смертельных случаев, потому что в этом случае мы не определили пол. Таким образом, если у нас есть x бросков и y разрешенных смертей, у нас может быть фактическое количество смертей r от 1 до y, и для каждого из них мы имеемxCr возможные последовательности. (Если r = y, то любые «пережитки» после yго смерть на самом деле "не бросил" с).

Решение jdmetz для F состоит в оценке g (D, B). Это нельзя сделать за время, превышающее O (min (D, B)), поскольку для этой суммы не существует замкнутой гипергеометрической формы (этот факт можно доказать с помощью алгоритма Госпера).

добавление Фактически, все три части исходной задачи могут быть выполнены за линейное время (предполагая, что умножение и арифметика являются операциями с постоянным временем, что у нас пока - не правда, но мы оставим это в стороне). Операция O (n lg n) в решении jdmetz находит наименьший D такой, что f (D, B)> = F.

Если мы объединим наше первоначальное повторение f (D, B) = f (D-1, B-1) + f (D-1, B) + 1 с термином, отличным от вида g, f (D, B) = f (D, B-1) +DCB получаем f (D, B) = 2 * f (D-1, B) + 1 -Д-1CB, Затем мы можем использоватьaCb = а-1Cb * a / (a ​​- b), чтобы перебрать D из 1.

    private static int d_opt(final long f, final int b)
    {
        int d = 0, dCb = 0;
        long f_db = 0;
        while (f_db < f)
        {
            dCb = (d == b) ? 1 : d * dCb / (d-b);
            f_db = 2 * f_db + 1 - dCb;
            d++;
        }
        return d;
    }
 ripper23415 янв. 2011 г., 12:21
Извините, я смотрел не на тот файл. Взгляните на решение jdmetz - это O (n) для getMaxF () и getMinB (). getMinD () реализован с использованием бинарного поиска getMaxF () - всего O (n log n)
 Peter Taylor15 янв. 2011 г., 12:51
Я думал, что F может быть связан с треугольником Паскаля, и теперь я вижу, что был прав. Все еще не доказал это, но это то, что делает код jdmetz. Первое наблюдение: если j> i, то F [i] [j] = F [i] [i], потому что вы не можете иметь больше смертей, чем брошенные кошки. Поэтому мы можем рассматривать только треугольник, образованный с i> = 0, 0 <= j <= i. Если мы сделаем индексирование строки i, F [i] [j] + 1 образует треугольник Бернулли (oeis.org/wiki/Bernoulli%27s_triangle ), частичные суммы строк треугольника Паскаля.
Решение Вопроса

O(D*B) (используя терминологию проблемы), но автор заметил, что для большинстваD а такжеB ответ будет больше, чем2^32 и поэтому-1 могут быть возвращены.
Итак, он вводитmaxn равно 1100 - максимумD а такжеF за что имеет смысл рассчитывать.
ЗаD, B = 10000 он сразу же возвращает -1. ЗаD, B = 100 ниже используется рекурсивная формула Только для некоторых «угловых значений», таких какD = 10000, B = 2используется прямая формула. (см. его комментарии для деталей о «прямой формуле»)

ЗаD, B < maxnАвтор предоставляет формулу в комментариях:f(d,b) = f(d-1,b)+f(d-1,b-1)+1, функцияf здесь возвращает максимальное количество этажей, для которых вы можете определить «точку останова», используя не болееd попыток и не болееb яйца.
Сама формула должна быть очевидна: независимо от того, на каком этаже мы бросаем первое яйцо, есть два результата. Это может сломаться, тогда мы можем проверить доf(d-1, b-1) этажей ниже. Или он может «выжить», тогда мы можем проверить доf(d-1, b) этажей выше. С текущим полом это делаетf(d-1,b)+f(d-1,b-1)+1 общее количество.

Теперь его можно легко закодировать как DP (динамическое программирование). Если вы покидаете бесконечность (2^32) проверяет, становится довольно чисто.

    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + 1;
        }
    }

Когда у нас есть массивf[D][B] сохраняя эти результаты, находяD' а такжеB' это бинарный поиск. (так как функцияf растет монотонно обоимиd а такжеb)

PS Хотя я и сказал, что в ответе на проблему «кошек» есть более быстрое решение, на самом деле это круче, чем я имел в виду :) Спасибо вам иSCLO (Автор)!

 Peter Taylor15 янв. 2011 г., 20:50
Это не отвечает на (измененный) вопрос, который был изменен, чтобы отразить решение jdmetz.
 ripper23415 янв. 2011 г., 14:34
Это все еще недостаточно хорошо, но может быть изменено. Я реализовал эти несколько оптимизаций: 1. Итерация только с b = 2, а не с b = 1. 2. Остановите итерацию, как только вы переполните maxint, и сохраните карту maxBForD (для данного D максимальный B, который не переполняется). 3. Сохраните maxDForB2 (max D, который не переполняется при B> = 2). Наконец, это работает :) Код, доступный на github:github.com/ripper234/Basic/blob/master/java/src/main/java/org/...

Ваш ответ на вопрос