2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача о вершинном покрытии
Сообщение18.02.2021, 12:14 


23/04/18
135
решаю уже закончившийся яндекс контест (тренируюсь для поступления в яндекс ШАД) и у меня затык со второй задачей.
Предоставляю ссылки на полные снимки задачи, чтобы не быть косноязычным.
Собственно алгоритмически код верный, завал получается из-за его неэффективности - 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);
}


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

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 12:43 
Заслуженный участник


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

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 12:50 
Заслуженный участник
Аватара пользователя


01/08/06
2826
Уфа
В задачу не вникал, но если чуть-чуть не хватает, то, возможно, вот этот вызов:
Используется синтаксис C
G = sum(G, P[S]);

достаточно будет просто заменить на inline-реализацию:
Используется синтаксис C
(G += P[S]) %= Nm;

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 13:52 


14/01/11
2547
Используется синтаксис 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.

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 14:42 
Заслуженный участник


20/08/14
7919
Россия, Москва
А я бы ещё и вот отсюда убрал деление, заменив его на условное вычитание, а то 10млн делений займут до 300млн тактов, что может потребовать 0.1..0.2с:
Используется синтаксис C
for (int i = 1; i < Nr; i++) P[i] = (P[i - 1] << 1) % Nm;

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 14:47 
Заслуженный участник
Аватара пользователя


16/07/14
4882
Москва
Никакие локальные оптимизации тут не помогут, асимптотика экспоненциальная. С мемоизацией можно получить квадрат, но это тоже слишком медленно. Правильный алгоритм будет работать за линию, и тут уже константа будет не особо важна.
worm2 в сообщении #1505559 писал(а):
достаточно будет просто заменить на inline-реализацию
Компилятор должен с этим справиться сам.

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 15:13 


14/01/11
2547
По-моему, хаскель прямо-таки напрашивается. :-)
Используется синтаксис 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]))

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 15:24 
Аватара пользователя


11/12/16
9074
уездный город Н
Несколько утверждений на уровне гипотез.

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

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение18.02.2021, 16:25 
Аватара пользователя


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

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение19.02.2021, 08:26 
Аватара пользователя


11/12/16
9074
уездный город Н
Оценил сложность получившегося алгоритма.

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

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение19.02.2021, 20:49 


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

 Профиль  
                  
 
 Re: олимпиадная задача по программированию
Сообщение19.02.2021, 20:58 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group