Are C strings faster than C++ string object?

codechef
cook-off

#1

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?


#2

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


#3

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


#4

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


#5

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.


#6

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


#7

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


#8

@pankajkhan that is very true XD


#9

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