Почему возникает Memory Limit Exceed?

Question

В контесте нужно решить следующую задачу:

На вершине лесенки, содержащей n ступенек, сидит кузнечик, который хочет спуститься вниз, к основанию. Кузнечик умеет прыгать на следующую ступеньку, на ступеньку через одну или через две. Например, если кузнечик сидит на 6-ой ступеньке, то он может прыгнуть на 3-ую, 4-ую или 5-ую ступеньку. Кузнечик всегда прыгает только вниз.

Ваша задача - посчитать количество всевозможных маршрутов кузнечика для спуска с последней ступеньки до основания.

Так как количество маршрутов может быть очень большим, Вам необходимо вывести ответ как остаток от деления результата на (10^9 + 7).

Решил с помощью массива значений:

public static BigInteger fooBI2(int n) {
    BigInteger[] vars = new BigInteger[3];
    vars[0] = BigInteger.valueOf(1L);
    vars[1] = BigInteger.valueOf(2L);
    vars[2] = BigInteger.valueOf(4L);
    for (int i = 3; i < n; i++) {
        vars[i%3] = vars[0].add(vars[1]).add(vars[2]);
    }
    return vars[(n-1)%3].mod(BigInteger.valueOf((long) (Math.pow(10, 9) + 7)));
}

Но почему-то на одном из тестов проваливается в MLE. Который час не могу понять, почему. Нужна подсказка или помощь.

Answer 1

Собственно, намек был сделан в самой задаче —

Так как количество маршрутов может быть очень большим, Вам необходимо вывести ответ как остаток от деления результата на (10^9 + 7).

Чтобы вы не пытались работать с очень большими числами, а работали с остатками.

Тут самое время вспомнить, что

(a+b) mod с == (a mod с + b mod c) mod c

и переписать ваш код (помня о том, что сумма трех чисел около миллиарда уже может выпрыгнуть за рамки int):

public static int fooBI3(int n) {
    int p = 1000000007;
    int[] vars = new int[3];
    vars[0] = 1;
    vars[1] = 2;
    vars[2] = 4;
    for (int i = 3; i < n; i++) {
        vars[i%3] = ((vars[0] + vars[1])%p +vars[2])%p;
    }
    return vars[(n-1)%3];
}

Answer 2

Число маршрутов кузнечика равно g(n) = tribonacci(n + 2). Последовательность tribonacci устроена точно также как g: следующее значение - сумма трёх предыдущих. Надо только подобрать смещение. Трибоначчи отстаёт на два индекса:

g:  1  1  2  4  7 13 24
T:  0  0  1  1  2  4  7 13 24

Числа трибоначчи можно считать быстрым возведением в степень:

                     n
/ T_n   \   / 0 1 0 \  / 0 \
| T_n+1 | = | 0 0 1 |  | 0 |
\ T_n+2 /   \ 1 1 1 /  \ 1 /

Код:

public class Grasshopper {

    private static class Triple {
        private final int a;
        private final int b;
        private final int c;

        Triple(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    };

    private static final int MODULO = 1_000_000_007;

    private static int add(int a, int b) {
        return (int)Math.floorMod(a + b, MODULO);
    }

    private static int add(int a, int b, int c) {
        return add(add(a, b), c);
    }

    private static int mul(int a, int b) {
        return (int)Math.floorMod((long)a * b, MODULO);
    }

    private static final Triple UNIT = new Triple(0, 0, 1);

    private static Triple mul(Triple t1, Triple t2) {
        return new Triple(
            add(mul(t1.a, add(t2.c, -t2.b, -t2.a)), mul(add(t1.c, -t1.b), t2.a), mul(t1.b, t2.b)),
            add(mul(t1.a, t2.a                   ), mul(add(t1.c, -t1.b), t2.b), mul(t1.b, t2.c)),
            add(mul(t1.b, t2.a                   ), mul(add(t1.a,  t1.b), t2.b), mul(t1.c, t2.c))
        );
    }

    private static Triple fast_pow(Triple t, long n) {
        if (n == 0) {
            return UNIT;
        }
        if (n % 2 == 0) {
            Triple sqrt = fast_pow(t, n / 2);
            return mul(sqrt, sqrt);
        }
        return mul(t, fast_pow(t, n - 1));
    }

    private static long tribonacci(long n) {
        return fast_pow(new Triple(0, 1, 1), n).a;
    }

    public static void main(String... args) {
        for (String arg : args) {
            long n = Long.parseLong(arg);
            System.out.println(tribonacci(n + 2));
        }
    }
}

$ javac Grasshopper.java

$ time java Grasshopper 0 1 2 3 4 5 6 7 8 9 10 9223372036854775805
g(0) = 1
g(1) = 1
g(2) = 2
g(3) = 4
g(4) = 7
g(5) = 13
g(6) = 24
g(7) = 44
g(8) = 81
g(9) = 149
g(10) = 274
g(9223372036854775805) = 495578506

real  0m0.055s
user  0m0.052s
sys   0m0.004s

P.S. Длина лестницы ограничена типом long. Если его заменить на BigInteger, программа будет работать для любых лестниц за время пропорциональное количеству цифр в числе.

БЛОГ НА HUSL

Почему возникает Memory Limit Exceed?

Ответы (2 шт):