90% of Python solutions to A will get hacked or fail systests, since using the obvious ans += s[i] in a loop or similar will immediately balloon into O(n^2). My question is, why would one even need to consider this for a Div2A? It's not like it even adds to the complexity of the problem — the difficulty and algorithm would be the same for $$$|s| \lt 10^3$$$ or something. At the very least, have a pretest that's the trivial print(1) print('A'*200000) generator I wrote in 30 seconds, instead of leaving that to the hacking phase.
(To be fair, I'm pretty salty right now because I dropped from 2000 to 8000 after hacking my A. But I still think this is a pretty serious problem, especially for an educational round where problems have equal weighting... unless the goal was to educate me to not use Python ever again :/)
Update: Yep, I know that Python string concatenation is rather expensive now, you don't have to keep commenting that (although I appreciate everyone who responded :D). I guess the Educational Round succeeded in being educational! I still think that there should have been a strict $$$2*10^5$$$ pretest, but whatever, I'll take the L here. Now time to get back to Expert...
Can't you just reverse sort?
thats what i did
is this reverse sort?
The core logic would be something like this:
That's a good and pretty elegant burn
I'll be a bore but this can educate some people that python strings are immutable and are not based on vectors, so
str += charis a heavy operationso what is testcase which is hacking all python submissions
Just print all the T's first and then the other letters :)
Doesn't work if you use a separate string to store non-T letters and concatenate to that :(
I'm sorry, but I really can't get what you're saying. Is there any issue with this solution, or is it just hard to be code in Python?
String concatenation is linear time in Python
Thanks for your answer!
It is more of like lack of knowledge of Python. I too have encountered similar problem in my old days. Just use
''.join(arr)to join a list of strings it takesO(n)time. You can check it here.Fair enough, I used C++ for every other problem (string problems are easier in Python for me)
is 'T' * cnt hackable?
use c++ instead of python
No, python is the best language
dude u use c++
Yeah, shit happens)))
Well, I think its pretty educational to know that strings are immutable in python. Furthermore, it seems like you did a lot more work for a problem that was just reverse sorting the string.
It's been a day and I think I'll take the L on this one lol. Still sucks that there wasn't at least a $$$2*10^5$$$ test case in pretests, but whatever. Time to get back to expert...
I also tried to hack but there was no option for room and so that's why I leave it btw if for eg I do hack someones submission then I got extra + rating or wt? (cuz haven't done bfr so asking)
Hacking in the open hacking phase (which is available in Edu and Div3/4 rounds) does not award any points or ratings.
ohh thx for telling btw
Round is educational, and it educated you not to use += for strings
agree lol
still, no $$$2*10^5$$$ pretest? :(
Auto comment: topic has been updated by pilliamw (previous revision, new revision, compare).