Are C strings faster than C++ string object?

A very weird thing I faced today in Cook Off, my same solution got AC when I used char str[MAX] than using string str, is C string faster than C++ string object?

1 Like

It is because complexity of str1=str1+'a'; is O(n). Use str1+='a';

5 Likes

for(ll i=0;i<str1.size();i++)
{
}
this loop is creating problems for you ,
str1.size() is not guarenteed to be O(1) operation .read this

my solution for reference

1 Like

Okay, thank you for this,It costed me 4 TLE and penalties :frowning:

It says in the very link you provided that “So you can’t rely on size() having constant complexity, but I’m honestly not sure if there are any implementations that do not have a constant string::size()”, and as far as I know I never had any difficulty with size() becoming \mathcal{O}(n), so I think it is safe to assume that it is indeed a constant time operation in the standard library used by the Codechef judge, unless you have some evidence to the contrary.

5 Likes

Its ok ! Dude ! Believe me Lessons learnt this way will never be forgotten !

2 Likes

Lol, ask me. I got penalty for using "n/2 *(2 x a+(n-1) x d) instead of (n x (2 x a+(n-1) x d)/2

@pankajkhan that is very true XD

3 Likes

@dushsingh1995 exactly :expressionless: @vijju123 for a moment I was thinking O(lg n) or O(1) solution isn’t possible then why TLE. :expressionless:

1 Like