AboAbdoMC's blog

One quick question
By AboAbdoMC, history, 3 years ago, In English

why AC?

https://mirror.codeforces.com/contest/81/submission/177441374

shouldn't this be O(n^2)?

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

Comments Comments (13)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I think so but it is an old problem so maybe bad test cases?

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

This solution uses ovidiush11's trick. String erase is apparently O(0). I hope he can explain with more details because I am not good enough for this obscure idea yet.

Marinush

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

It is $$$O(n^2)$$$, but all your operations are basically memcpy, so the constant factor is really small.

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

order is n^2 but Coefficient is small

→ Reply