Задача о вершинном покрытии

[Paul Ivanov]

решаю уже закончившийся яндекс контест (тренируюсь для поступления в яндекс ШАД) и у меня затык со второй задачей.
Предоставляю ссылки на полные снимки задачи, чтобы не быть косноязычным.
Собственно алгоритмически код верный, завал получается из-за его неэффективности - 16-й тест не проходит, так как превышен лимит времени 2.086 s (должно быть не больше 2 секунд). Я пробовал задавать разные алгоритмы, из всех мною перепробованных представленный ниже на мой взгляд самый эффективный.
Кратко описать принцип моего алгоритма можно так: я ищу все такие варианты удалить элементы из главной цепи, что никакие два из удаляемых не стоят рядом, попутно вычитая из накопленной суммы соответствующие удаляемым вершинам смежные кратности. В финале каждого варианта вершинного покрытия я просто беру накопленную степень двойки (уже вычисленную по нужному модулю в массиве P) и добавляю её в G.
Собственно, мне по крайней мере интуитивно понятно, что с допустим 100000-элементной цепью со смежной кратностью 100 у каждой вершины моя рекурсия не должна справиться, так как даже если говорить о просто изменении G, то этих изменений колоссальное количество. По-моему тут даже цикловая реализация не поможет.
Так что же всё-таки не так? Может я не вижу какой-то чисто математической фишки? И возможно ли вообще удовлетворить всем требованиям задачи на все (даже крайние-длинные) случаи?
https://ibb.co/LtC97wc
https://ibb.co/Phwc34M
https://ibb.co/D7JyGXN

Используется синтаксис C

//#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
//#include <cstdlib>
#define Nr 10000001  // размера массива всех возможных степеней двойки по модулю Nm
typedef unsigned int uint;
const uint Nm = 1000000007; // модуль по которому требуется ответ

uint G; //глобальный накопитель
uint sum(uint a, uint b) { 
        return (a + b) % Nm;
}

void analyze(uint S, uint K, uint L, uint* M, uint* P) { // S - накопленная сумма на данном уровне рекурсии 
        for (uint i = K + 2; i < L; i++) analyze(S - M[i], i, L, M, P); //K - номер последней дырки
        G = sum(G, P[S]);
}

int main() {
        uint* P=(uint*)malloc(Nr*sizeof(uint)); // P - массив степеней двойки
        P[0] = 1;
        for (int i = 1; i < Nr; i++) P[i] = (P[i - 1] << 1) % Nm;

        uint L; // L - длина цепи
        scanf("%u", &L);
        uint* M = (uint*)malloc(L * sizeof(uint)); //M - массив смежных кратностей вершин цепи 
        for (uint i = 0; i < L; i++) scanf("%u", &M[i]);

        uint big = 0; // big - максимально возможная степень двойки
        for (uint i = 0; i < L; i++) big += M[i]; // определение big
        G = P[big]; // вручную добавляем P[big] к G, чтобы учесть тот случай, когда дырок нет 
        for (uint i = 0; i < L; i++) analyze(big - M[i], i, L, M, P); // вручную запускаем все варианты того, какая дырка будет первой

        printf("%u", G);
        free(M);
        free(P);
}

Lia: название темы изменено на более содержательное.
Большая просьба писать текст задач здесь, хотя бы помимо скринов, а лучше вместо. Наиболее оптимально: текст+ картинка, если она есть в условии.

[12d3]

Это задачка на динамическое программирование. Подумайте, как можно решить ее с таким подходом. Если ничего не придумаете, подскажу дальше.

[worm2]

В задачу не вникал, но если чуть-чуть не хватает, то, возможно, вот этот вызов:

Используется синтаксис C

G = sum(G, P[S]);

достаточно будет просто заменить на inline-реализацию:

Используется синтаксис C

(G += P[S]) %= Nm;

[Sender]

Используется синтаксис C

uint sum(uint a, uint b) {
        return (a + b) % Nm;
}

Может, деление замедляет? Что, если попробовать что-то в духе

Используется синтаксис C

uint sum(uint a, uint b) {
        uint s = a + b;
        return (s < Nm) ? s : (s - Nm);
}

-- Чт фев 18, 2021 13:54:41 --

Или даже совместить с идеей worm2.

[Dmitriy40]

А я бы ещё и вот отсюда убрал деление, заменив его на условное вычитание, а то 10млн делений займут до 300млн тактов, что может потребовать 0.1..0.2с:

Используется синтаксис C

for (int i = 1; i < Nr; i++) P[i] = (P[i - 1] << 1) % Nm;

[mihaild]

Никакие локальные оптимизации тут не помогут, асимптотика экспоненциальная. С мемоизацией можно получить квадрат, но это тоже слишком медленно. Правильный алгоритм будет работать за линию, и тут уже константа будет не особо важна.

worm2 в сообщении #1505559 писал(а):

достаточно будет просто заменить на inline-реализацию

Компилятор должен с этим справиться сам.

[Sender]

По-моему, хаскель прямо-таки напрашивается.

Используется синтаксис Haskell

f :: [Int] -> Int 
f [] = 1 
f [x] = x + 1
f (x:y:xs) = mod ((x*f(y:xs))+y*f(xs)) 1000000007
main = do 
print (f (map (2^) [0,3,0,1,2,1,3,1,0]))

[EUgeneUS]

Несколько утверждений на уровне гипотез.

del
Гипотеза оказалась неверной.

[EUgeneUS]

Если цеплять к "гусенице" по одному звену, то получается довольно простая рекуррентная формула для вычисления числа покрытий.
То есть алгоритм является линейным.

[EUgeneUS]

Оценил сложность получившегося алгоритма.

1. Так как длина гусеницы может быть большой (до $100000$ включительно), а количество ног на одном узле небольшое (до $100$ включительно), то имеет смысл посчитать остатки от степеней двойки заранее. Это займет $99$ дешевых умножений на $2$ и $99$ вычислений остатков.
2. Сам алгоритм использует одно умножение, одно сложение и два вычисления остатков на шаге.
Понятно, что с такой сложностью на любых "гусеницах", которые возможны по условию, считаться будет "за миллисекунды".

[Paul Ivanov]

Всем спасибо за советы и участие!
Я почитал немного про динамическое программирование и до меня допёрло.
Собственно мой итоговый алгоритм (который в итоге прошёл все тесты), если не вдаваясь в подробности, похож на эффективное вычисление числа фибоначчи (когда по циклу перезаписываешь две переменные и достигаешь нужного результата за линейное время), только вместо последовательности чисел фибоначчи последовательность вложенных фрагментов цепи и плюс ещё слагаемые надо домножать на соответствующую степень двойки. Наверное, вы мне подсказывали что-то подобное.

[EUgeneUS]

Paul Ivanov
Ага. У меня подобный алгоритм получился.
На каждом шаге лучше сразу использовать модульную арифметику, чтобы огромные числа не перемножать.