Agniva_'s blog

Why is this leading to TLE?

By Agniva_, history, 9 months ago, In English

Problem Link 254383531

void solve(){
   int n; cin>>n;
   vi v(n); rep(i,0,n) cin>>v[i];
   int flag=1;
   rep(i,0,n/2){
     if(v[i]!=v[n-1-i]) {
        flag=0; break;
     }
   } 
   if(flag){
    yes
    return;
   }
   string s="";
   for(int i=0;i<n;i++) 
     if(v[i]!=v[0]) s=s+to_string(v[i]);
    string s2=s;
    reverse(s2.begin(),s2.end());
    if(s==s2) 
    {
        yes return;
    }
    s="";
    for(int i=0;i<n;i++) 
     if(v[i]!=v[n-1]) s=s+to_string(v[i]);
    s2=s;
    reverse(s2.begin(),s2.end());
    if(s==s2) 
    {
        yes return;
    }
    no 
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

because of s=s+to_string(), instread of this , you can use s+=to_string().

Spoiler
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

try to avoid using strings, this problem can be solved easily without really maintaining any additional $$$O(n)$$$ structure, in your for loop you are reversing a string which could grow linearly, so your code is essentially $$$O(n^2)$$$

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not reversing the string inside the loop though but yeah i get your point-will avoid string operations

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay, I didnt see it, but still '+=' operator can take as much as length of the new string time, look at cpp docs here

      → Reply