Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

uamer's blog

Problem with time !!!
By uamer, history, 5 years ago, In English

why my this code 118446438 get Time limit exceeded and this code 118446206 get accepted in problem 1535C - Нестабильная строка

any hint

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

for(int i=0 ; i<strlen(s) ; i++)

strlen(s) has $$$O(n)$$$ complexity so this whole loop has $$$O(n^2)$$$ complexity.

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

strlen() is O(n)

the way strlen works is that it will scan and count, until it finds a null character: every time you call strlen, it scans again and again from the beginning, so it's inefficient, while s.size() is constant

→ Reply