Архив форума

Какая вычислительная сложность у сабджевой задачи? Получаю time limit на 18м тесте. Это означает неоптимальный алгоритм, или с тестами не повезло? (допустим, я ищу решение "сверху", а надо "снизу")

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

А сложность несложная :)

Идея решения
Введем множества X = {1..M} и X(L) – декартова степень L множества X
Искомый вектор обозначим Y. Он принадлежит X(L).
Введем множество R(L, q) = {y из X(L) : (y_1 + y_2 + ... + y_L)% K = q}
Введем обозначение P(L, q) = |R(L, q)|

Тогда P(L, q) - это количество векторов, длины L, сумма координат которых, при делении на K, даёт в остатке q. В частности P(L, 0) – это количество векторов, описывающих состояние АСМ.

Ответим на вопрос: сколько существует таких векторов, начинающихся с цифры a и имеющих длину L.
|{(a, y_2, ... y_L) из X(L): (a + y_2+y_3...+y_L) % K = 0}| =
|{(a, y_2, ... y_L) из X(L): (y_2+y_3...+y_L) % K = (0-a)K}| =
|{(y_2, ... y_L) из X(L-1): (y_2+y_3...+y_L) % K = (0-a)K }| = P(L-1, (0-a)K)
здесь (0-a)K – это вычитание по модулю K.

Зная это, можно определить вектор по его номеру таким образом:
Сначала определим 1-ую координату вектора. Для этого найдем минимальное число a из X такое, что выполняется неравенство:
P(L-1, (0-1)K) + P(L-1, (0-2) K)+ ... + P(L-1, (0-a)K) > N
здесь N – это номер вектора.
Число слева – это количество векторов, у которых первая координата не больше а. Тогда, очевидно, это число a и будет первой координатой искомого вектора.
Положим С = N - P(L-1, (0-1)K) + P(L-1, (0-2)K)+ ... + P(L-1, (0-(a-1))K)
Вторая координата вектора находится по такому же алгоритму:
найдем минимальное число b из X такое, что выполняется неравенство:
P(L-2, (0-a-1)K) + P(L-2, (0-a-2)K)+ ... + P(L-2, (0-a-b)K) > C
Число слева – это количество векторов, первая координата которых равна a, а вторая не больше b. Тогда, очевидно, b будет второй координатой искомого вектора.

И так далее пока не будут определены все координаты искомого вектора.

Расчет таблицы P(L, q)
Остался вопрос, как посчитать P(L, q). Это можно сделать динамическим программированием, с помощью рекуррентного соотношения:
P(0, 0) = 1;
P(0, I) = 0 (для всех I=1..K-1);
P(L, q) = P(L-1, (q-1)K) + P(L-1, (q-1)K) + ... P(L-1, (q-M)K)

Грубую верхнюю оценку количества десятичных цифр P(l, q) можно получить следующим образом:
P(0, I) <= 1;
P(L, I) <= M*P(L-1, I) <= 50*P(L-1, I) <= 50L * P(0, I) <= 50L <= 100L <= 102L
Поскольку по условию L <= 100, то есть количество цифр – не больше 200.

Оценка сложности алгоритма.
Заполнение таблицы P(L, q) происходит в тройном цикле (по длине L, по остатку q и еще один цикл суммирования членов от 1 до M) за L*K*M сложений. То есть за 200*L*K*M <= 200*100*50*50 = 50000000 простых операций.
Нахождение искомого вектора происходит в двойном цикле (для каждой координаты перебираются все ее значения) за L*M простых операций с длинными числами, то есть за 200*L*M <= 200*100*50 = 1000000 простых операций.

Оценка расхода памяти.
Требуется хранить таблицу размера L на K длинных чисел (по 200 цифр в каждом). Если на каждую цифру выделять по 1 байту, то получится 200*L*K <= 1Мб