You are not logged in. Please login at www.codechef.com to post your questions!

×

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?

asked 24 Apr '17, 00:03

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%


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

link

answered 24 Apr '17, 00:19

dushsingh1995's gravatar image

4★dushsingh1995
92313
accept rate: 11%

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

(24 Apr '17, 00:34) neilit19923★
2

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

(24 Apr '17, 00:59) pankajkhan5★

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

(24 Apr '17, 01:17) vijju123 ♦♦5★
3

@pankajkhan that is very true XD

(24 Apr '17, 01:24) meooow ♦6★
1

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

(24 Apr '17, 01:31) neilit19923★

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

link

answered 24 Apr '17, 00:19

acodebreaker2's gravatar image

1★acodebreaker2
1.2k12
accept rate: 18%

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.

(24 Apr '17, 00:49) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,357
×555

question asked: 24 Apr '17, 00:03

question was seen: 413 times

last updated: 24 Apr '17, 01:32