टीएलई एसपीओजे सबमिशन को रोकने के लिए मैं इस एल्गोरिदम को कैसे सुधार सकता हूं?

Question

मैं निम्नलिखित समस्या को हल करने की कोशिश कर रहा हूँ: http://www.spoj.pl/problems/TRIP/

मैं एक समाधान C++ में डी पी (गतिशील प्रोग्रामिंग) का उपयोग करते हुए (कोड के नीचे तैनात) लिखा था। लेकिन मुझे टीएलई मिलती है (समय सीमा समाप्त हो गई)। मैं अपना कोड कैसे अनुकूलित कर सकता हूं?

#include<iostream> 
#include<cstdio> 
#include<string> 
#include<cstring> 
#include<vector> 
#include<algorithm> 
#include<cmath> 

using namespace std; 
string a,b; 
vector<string> v; 
int dp[85][85]; 

void filldp() 
{ 
    for(int i = 0; i <= a.length(); i++) 
     dp[i][0] = 0; 
    for(int i = 0; i <= b.length(); i++) 
     dp[0][i] = 0; 

    for(int i = 1; i <= a.length(); i++) 
     for(int j = 1; j<= b.length(); j++) 
     if(a[i-1] == b[j-1]) 
      dp[i][j] = dp[i-1][j-1] + 1; 
     else 
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
} 

vector<string> fillv(int i, int j) 
{ 
    vector<string> returnset; 
    if(i == 0 || j == 0) 
    { returnset.push_back(""); 
     return returnset; 
    } 

    if(a[i-1] == b[j-1]) 
     { 
      vector<string> set1 = fillv(i-1,j-1); 
      for(int k = 0; k < set1.size(); k++) 
      { 
      returnset.push_back(set1[k] + a[i-1]); 
     } 
      return returnset; 
     } 

    else 
     { 
      if(dp[i][j-1] >= dp[i-1][j]) 
      { 
       vector<string> set1 = fillv(i,j-1); 
       returnset.insert(returnset.end(), set1.begin(), set1.end()); 
      } 

      if(dp[i-1][j] >= dp[i][j-1]) 
      { 
       vector<string> set2 = fillv(i-1,j); 
       returnset.insert(returnset.end(), set2.begin(), set2.end()); 
      } 

      return returnset; 

     }  

} 

void output() 
{ 
    sort(v.begin(), v.end()); 
    v.erase(unique(v.begin(), v.end()), v.end()); 
    for(int i = 0; i < v.size(); i++) 
     cout << v[i] << endl; 
    cout << endl;  
} 

int main() 
{ 
    int T; 
    cin >> T; 

    while(T--) 
    { 
     memset(dp,-1,sizeof(dp)); 
     v.clear(); 
     cin >> a >> b; 
     filldp(); 
     v = fillv(a.length(), b.length()); 
     output(); 
    } 
    return 0; 
} 

मेरे यहाँ अनुमान डेटा संरचनाओं जो बचा जा सकता है की चारों ओर गुजर का एक बहुत है कि वहाँ है, लेकिन मैं वास्तव में कैसे को समझ नहीं सकता है।

Answer 1

पहली गलत चीज जो आप कर रहे हैं वह सीन और कोउट का उपयोग कर रही है, जो बहुत धीमी हैं। प्रतियोगिता प्रोग्रामिंग के लिए कभी भी सिने और कॉउट का उपयोग न करें! मैं स्कैन/printf में cin/cout बदलकर टीएलई से एसी तक चला गया हूं।

Answer 2

जब आप उत्तर की संख्या का अधिकतम आकार जानते हैं तो वेक्टर की बजाय सरणी का उपयोग करना बेहतर है क्योंकि यह वेक्टर से बहुत तेज है। ("कम से कम एक ऐसी यात्रा है, लेकिन 1000 से अधिक अलग-अलग नहीं हैं")

फ़ंक्शन fillv कोड में बहुत समय बर्बाद कर देता है। क्योंकि इसे रनटाइम में बहुत सी जगह मिलती है और इसे मुक्त करें (fillv फ़ंक्शन के लिए स्थानीय स्थान की वजह से)। इसके लिए वैश्विक उत्तर का उपयोग करना बेहतर है।

"गैंडफेल ग्रे" के जवाब को पूरा करने के लिए इनपुट और आउटपुट के लिए इनपुट और आउटपुट के लिए, यदि आप सीन और कॉउट का उपयोग करना चाहते हैं, तो std::ios::sync_with_stdio(false); (अपने आईओ रनटाइम को तेज करने के लिए) का उपयोग करना बेहतर है, हालांकि printf और स्कैनफ़ इस से बहुत तेज है ।

Answer 3

आप fread() या fread_unlocked() (यदि आपका प्रोग्राम एकल-थ्रेडेड है) का उपयोग करके इनपुट ले कर निष्पादन के समय को बहुत कम कर सकता है। इनपुट स्ट्रीम को लॉक करना/अनलॉक करना केवल एक बार नगण्य समय लेता है, इसलिए इसे अनदेखा करें।

#include <iostream> 

int maxio=1000000; 
char buf[maxio], *s = buf + maxio; 

inline char getc1(void) 
{ 
    if(s >= buf + maxio) { fread_unlocked(buf,sizeof(char),maxio,stdin); s = buf; } 
    return *(s++); 
} 
inline int input() 
{ 
    char t = getc1(); 
    int n=1,res=0; 
    while(t!='-' && !isdigit(t)) t=getc1(); if(t=='-') 
    { 
     n=-1; t=getc1(); 
    } 
    while(isdigit(t)) 
    { 
    res = 10*res + (t&15); 
    t=getc1(); 
    } 
    return res*n; 
} 

यह C++ में कार्यान्वित किया जाता:

यहाँ कोड है। C में, आपको iostream, फ़ंक्शन isdigit() शामिल करने की आवश्यकता नहीं होगी।

आप getc1() पर कॉल करके वर्णों की धारा के रूप में इनपुट ले सकते हैं और input() पर कॉल करके पूर्णांक इनपुट ले सकते हैं।

fread() का उपयोग करने के पीछे पूरा विचार एक बार में इनपुट के बड़े ब्लॉक लेना है। scanf()/printf() पर कॉल करना, स्ट्रीम को लॉक करने और अनलॉक करने में मूल्यवान समय लेता है जो एकल-थ्रेडेड प्रोग्राम में पूरी तरह से अनावश्यक है।

यह भी सुनिश्चित करें कि maxio का मान ऐसा है कि सभी इनपुट केवल कुछ "roundtrips" (आदर्श रूप में, इस मामले में) में लिया जा सकता है। इसे आवश्यकतानुसार ट्विक करें। निष्पादन के समय के दौरान अपने प्रतिद्वंद्वी पर बढ़त हासिल करने के लिए, यह तकनीक प्रोग्रामिंग प्रतियोगिताओं में अत्यधिक प्रभावी है।

आशा है कि इससे मदद मिलती है!