Pranshu Kashyap Ответов: 2

Может ли кто - нибудь уменьшить сложность моего кода? Проблема е на Codeforces round113 див.2

Ссылка на проблему: https://codeforces.com/problemset/problem/166/E[^]

постановка задачи:

*Вам дан тетраэдр. Обозначим его вершины буквами A, B, C и D соответственно.

Муравей стоит в Вершине D тетраэдра. Муравей довольно активен, и он не будет сидеть сложа руки. В каждый момент времени он делает шаг от одной вершины к другой вдоль некоторого края тетраэдра. Муравей просто не может стоять на одном месте. Вам не нужно много делать, чтобы решить эту проблему: ваша задача состоит в том, чтобы подсчитать количество способов, которыми муравей может пройти от начальной вершины D к себе ровно за n шагов. Другими словами, вас просят узнать количество различных циклических путей длиной n от вершины D до самой себя. Поскольку число может быть довольно большим, вы должны вывести его по модулю 1000000007 (10e9 + 7).*

Ввод: Первая строка содержит единственное целое число n (1 ≤ n ≤ 107) — требуемую длину циклического пути.

Выход: Выведите единственное целое число — необходимое количество способов по модулю 1000000007 (10e9 + 7).

Пример: Вход n=2 , Выход: 3 Вход n=4, Выход: 21

Что я уже пробовал:

Мой подход к проблеме: Я написал рекурсивный код, который принимает два входных n и настоящий индекс, а затем путешествую и исследую все возможные комбинации.


#include<iostream>
using namespace std;
#define ll long long 
#define mod 10000000  
ll count_moves=0;
    ll count(ll n, int present)
    {   
        if(n==0 and present==0) count_moves+=1, count_moves%=mod;  //base_condition
        else if(n>1){                   //Generating All possible Combinations 
            count(n-1,(present+1)%4);
            count(n-1,(present+2)%4);
            count(n-1,(present+3)%4);
        }
        else if(n==1 and present) count(n-1,0);
    }
    int main()
    {
        ll n;  cin>>n;
        if(n==1) {  cout<<"0";  return;   } 
        count(n,0);
        cout<<count_moves%mod;
    }



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

2 Ответов

Рейтинг:
2

Patrice T

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

На этом сайте мы помогаем вам исправить ваш код, но ваш код не показывает никаких попыток использовать memoization, вы не описываете никакой конкретной проблемы.
Цитата:
Пожалуйста, кто-нибудь может подсказать мне, как я могу оптимизировать/запомнить свой код, чтобы уменьшить его сложность?

Чего вы не понимаете в принципе мемуаризации.
Запоминание-это запоминание предыдущих результатов, и вы постоянно пересчитываете одни и те же вещи.
Мемуаризация - Википедия[^]

Рейтинг:
1

OriginalGriff

Мы более чем готовы помочь тем, кто застрял, но это не значит, что мы здесь, чтобы сделать все это для вас! Идея этих испытаний состоит в том, чтобы проверить ваши знания, ваши способности. Чтобы дать вам шанс изменить то, как вы думаете о проблемах, и выработать различные решения - и это было бы совсем нечестно для нас, чтобы сделать все это для вас, так как это разрушило бы цель!

Поэтому нам нужно, чтобы вы сделали работу, и мы поможем вам, когда вы застряли. Это не значит, что мы дадим вам пошаговое решение, которое вы можете сдать!
Начните с того, что подумайте о своем существующем решении и о том, почему оно медленное. Затем начните думать о проблеме и о том, какие другие способы могут быть, чтобы сделать все это. Там могут быть короткие пути, которые уменьшают необходимость "грубой силы" , как вы это делаете.

Pranshu Kashyap

Я не знал, что этот сайт должен сказать вам, что если вы застряли в какой-либо проблеме, то расскажите о своих сомнениях своему наставнику, и он просто скажет: решите сами, мы здесь только для того, чтобы публиковать бессмысленные ответы.
Если бы я мог сам ответить на свой вопрос, зачем бы я спросил вас? Это не значит, что я не подошел к вопросу и не попросил у вас полного решения, и я не требую от вас пошагового решения. Просто я попросил вас дать мне подсказки, какой тип оптимизации я мог бы сделать, чтобы уменьшить временную сложность моего кода. Я знаю, что мой код медленный из-за экспоненциальной сложности, я ожидал, что смогу запомнить свой код. Я новичок, и мне нужна помощь на этом этапе, чтобы думать в правильном направлении, но hola wow!! этот сайт полон глупых людей, которые не могли этого понять.

Хотя Спасибо, что уделили мне свое драгоценное время. Я сам разрешу свои сомнения.

OriginalGriff

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