Problem: A. Cut and Paste when i am using
s=s+t; [this is giving me TLE on 37 test ] [128332169](https://mirror.codeforces.com/contest/1280/submission/128332169)
and s+=t; is Accepted 128332405 20 ms
can anyone tell me why such happen.???
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | cry | 157 |
3 | nor | 157 |
5 | atcoder_official | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Problem: A. Cut and Paste when i am using
s=s+t; [this is giving me TLE on 37 test ] [128332169](https://mirror.codeforces.com/contest/1280/submission/128332169)
and s+=t; is Accepted 128332405 20 ms
can anyone tell me why such happen.???
Название |
---|
s = s + t;
this line will create new string object with values + t
and assign it tos
, complexity $$$O(|s| + |t|)$$$s += t;
this line just simply appendt
tos
, complexity $$$O(|t|)$$$This code produced the following output on my system
So avoid using assignment operator!
Thanks. Found where i am wrong.
When I'm running your code on Dev C++ it is printing 0 0, but in the online C++ compiler, it is giving the right answer. Can you please tell me what is wrong with the Dev C++ compiler? Thank You:)
I guess
CLOCKS_PER_SEC
on your system has the value 1000. So just add consuming stuff between 2clock()
call, you'll see the difference:For better precision, I suggest using chrono. IMO using
clock()
is better as it's really easy to remember the syntax.I think the '+' operator's complexity is O(2*(n1 + n2)), where n1 and n2 are the lengths of the strings s and t.
The complexity of the operator '+=' might only be O(2*n2) in some implementations on the other hand as only the append() operation is to be performed.
A Stack Overflow Thread
If there is a huge difference between the lengths of s and t, this could effectively work out as the difference between an O(N) algorithm and an O(1) algorithm, and could possibly lead to TLE.
Click