By Badral1, history, 18 months ago,

Today I tried to solve this 219C - Цветная полоска using ruby and my code's time complexity was 26*n but, I got a TLE (Time Limit Exceeded). Could someone explain to me the time complexity of ruby language? (My code:75217241)

• +2

 » 18 months ago, # |   +2 Auto comment: topic has been updated by Badral1 (previous revision, new revision, compare).
 » 18 months ago, # | ← Rev. 2 →   +11 Time complexity is theoretical and does not change with programming language. You are looking to understand how to optimise the Runtime in Ruby language.I don't know much about Ruby but it is always risky to use an Interpreted language in Competitive Programming !
•  » » 18 months ago, # ^ |   0 my code's time complexity is 26*n, but I'm having TLE ToT
•  » » » 18 months ago, # ^ |   +3 Your algorithm is probably correct but Ruby is a 'slow' language compared to C++. I don't know about Ruby specific tricks to optimise your code. But I noticed that for that particular problem, there was no AC solution in Ruby.
•  » » » 18 months ago, # ^ |   +2 Your code's time complexity is $O(n)$, it's more about asymptotic and it really doesn't change with language as ghoshsai5000 mentioned. $26 * n$ is precise number of high-level operations and it also doesn't change with language. Thing you should be interested in to understand difference of code runtime in different languages is number of low-level operations and it depends on how high-level operations is implemented in particular programming language. Basically, that is the reason why some programming languages is faster and some is slower. Ruby is very slow language. If you see on your submission details you will saw that on test #23 (which runs on $O(n)$ part of your solution for special cases) your code spend ~600ms. So, you cannot AC this task on Ruby with solution which use $26 * O(n)$ operations in the general case (although C++ solutions with $O(n*k^2)$ complexity passed it). So I tried to optimize your code for this general case and improved it firstly to $\log 26 * O(n)$ with SortedSet and even to $O(n)$ afterwards with auxiliary array. But both solutions also got TLE and I can summarize that this problem should have bigger time limit to be accepted with Ruby. Also, partially, problem with TLE can be related to the fact that this problem was added before Codeforces upgraded the judging servers and now solution runtime is just doubled to be adjusted to old time limits. I think you can ask MikeMirzayanov to look into this issue when he would have time for that.
 » 18 months ago, # |   +3 One tip regarding these kind of interpreted languages — try to avoid manually written loops. Often, if you use built in stuff, it may have underlying implementation in a fast language like C.If you want to investigate runtime bottlenecks, your best bet is to time your code at various sections. That is probably going to better than any advice than anyone can give.
 » 17 months ago, # |   0 Contrary to what others have said above, it is possible to AC this problem comfortably in Ruby after all. Even though I have close to zero experience in Ruby, I commented out critical parts of the code and benchmarked the code to identify the bottleneck.It turns out that the main cause of the problem is, string manipulation in ruby is slow. If you transform your string into an array and manipulate on the array instead, you will get AC very easily. In particular, benchmarks on my computer showed a 10x speedup.Besides that, I also introduced a optimization via trivial observation to turn your code into O(3*n) instead of O(26*n). I think you should be able to figure out the details from the code yourself. So I have posted the updated code here.Lesson of the day: Do not be like wannabe competitive programmers who are quick to ignore details and push the blame to everything else except themselves.
•  » » 17 months ago, # ^ |   0 Thank you very much for advice.