sai_aasish's blog

By sai_aasish, history, 6 weeks ago, In English
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        string a= "";//taking an empty string to store the output
        int i= n-1;
        while(i>= 0)//traversing the string from the rear
        {
            if(s[i] != 'a' && s[i] != 'e')//if its not a vowel, concatinating the last three elements to the "a" string
            {
                a= a+s[i];
                a= a+s[i-1];
                a= a+s[i-2];
                a= a+'.';
                i= i-3;
            }
            else//else, concatinating the last two elements to the "a" string
            {
                a= a+s[i];
                a= a+s[i-1];
                a= a+'.';
                i= i-2;
            }
        }
        a.pop_back();//popping out the last "."
        reverse(a.begin(), a.end());//reversing the output since I traversed from the rear
        cout<<a<<endl;
    }
    return 0;
}

Hey CF!, I came up with a solution to the below mentioned question and my code is getting a tle. What could be the problem? click here to view the problem

I must also mention that the first and the second hidden test cases are running fine but the third one is where the problem is. The constraints for "n" is 2*10^5, but my code is fulfilling it.

please let me know what is wrong in this code, thanking you.

edit:

the problem is resolved, all thanks to not_insync for the help!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sai_aasish (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sai_aasish (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sai_aasish (previous revision, new revision, compare).

»
6 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

a=a+'c' is O(N) whereas a+='c' is O(1) amortized a = a + "c" creates a copy of a, appends "c" and then assigns it back to a. a += "c" just appends "c" to a.

I hope this clears the issue for TLE

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that actually worked, thanks man, i learnt something new today, this means alot.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sai_aasish (previous revision, new revision, compare).