First and foremost, I really appreciate the team behind this code challenge… This was my first coding based competition (on CodeChef) but I have been programming for almost 6 years now…
I understand that C/C++ is preferred in competitions but I decided to participate in this challenge with Python because this is the language that I use the most, both for personal as well as work projects (backend developer)…
While I didn’t face much difficulty in understanding the problems or even solving it, my submissions continuously ended up getting TLE violations…
My usual approach was to get all the test cases before proceeding to find the solution of each individual test case. Unfortunately, this approach didn’t work… After doing some profiling, I realized that (as I guessed) that my I/O (input() / print()) functions were the main culprit…
I wanted to test against the test file created by your testers but after some digging into your forums, I came to know that they don’t allow us access to them… Hence, I have a couple of questions that I would love to get answers on:
How to effectively handle I/O based operations with Python?
Does your test files have newline characters in them? Or, some idea behind the general format of test files?
Do I need to create a test case generator for each problem? Any tips regarding one?
First of all, thank you so much for your quick reply… I have already tried the methods mentioned in the article and it didn’t make much difference to my submission… Probably, I was implementing it in the wrong way…
I will give it another spin…
If you don’t mind, can you please tell me a bit about what time limit is applied for Python programs… After going through the forums, I observed there is a lot of confusion regarding it…
Some are saying it is 5x (of times given for C/C++) or 2x… I would like to get a definitive answer…
And secondly, do you check for newline characters while dealing with inputs? Because I believe my habit of checking for blank lines are creating a bottleneck…
I have limited knowledge of Python, but if you’re getting constant TLEs, you should check your algo first.
And as for the test cases, the usual approach is to place a while loop that runs for T times (T - no. of test cases) and inside the while loop you will scan for each test case (rewriting the variables each time). Each test case (set) will expect an answer before the next test case (set) is set, you can see this more clearly on Codeforces. I actually recommend Codeforces over Codechef for practise because you can see all test cases. Helps a lot during practising. You can try this contest.
I might be totally wrong, but this is my approach.
And at the very basic level (div 2) fast I/O doesn’t make much of a difference.
All the best man.
If you compare python and C++ , C++ is 5 times faster than python in terms of compiling and execution but anyhow there will be different time allocation for different programming languages during the contests . For a given problem , if they give 1 sec time for C++ language , then python will be given 5 seconds . It doesn’t mean that python is inefficient . It is just the way , python works.
Secondly we shouldn’t take care of inputs whether they maybe in newline or same line.
what we should focus is on how output should be printed.
last but most important is how efficient your algorithm works for given problem
@zer0_skill I was exceeding the time limit by just 0.01 seconds but anyways, I was able to make some changes into my code and my solution was finally accepted… So, I am glad…
Read the editorial and realized that there was an obvious mathematical trick that I missed… In my solution, I was constantly creating a matrix but the solution didn’t need me to create one…
And, hence the delay… Anyways, thank you so much for taking your time out and helping me…
@anon57245732 Thank you so much for your answer… This is exactly what I was looking for…
@anon89270066 I agree on the differences between the various programming languages… I have been working in Python for more than 2 years and it is my preferred language to use (even though, I started programming in C++)…
And, I also completely agree about the input part… Unfortunately, my work as an app dev, came in my way as I became too fixated on getting the inputs in the right way…
Thank you once again for your help… By the way, I have finally solved the problem…
Okay, which contest are you talking about. Is it the recently concluded long contest. Are you talking about problem S10E of long contest.
One thing I observed is that you are calling function too many times, even for reading input. Python is unable to handle function calls so quickly. It might slow your program down.
Look at the code of people who got AC with python to understand what they are doing differently.
Regarding TLE, the limit appears to be five times. Here is the proof:
Solved S10E but somehow got stuck in SAKTAN… I pulled my code out of functions and just submitted as a script but was constantly getting TLEs… I finally understood where I was going wrong after reading the editorial but it was really frustrating…
My algorithm (while being brute-force) was solving the test cases (which I had created manually) but the lack of access to the mammoth test cases (used in the contest) made me feel like I was running with my eyes closed because I couldn’t pinpoint where I was going wrong…
On top of that, I observed that my program was taking too long in the process of getting inputs (because I was constantly invoking a function inside a for loop)… So, my complete focus was somehow getting the I/O operations faster…
As a software engineer, I sometimes feel so frustrated to see how code’s readability gets sacrificed for performance gains… Especially codes where people don’t even bother with proper indentation or formatting or single-letter variable names…
P.S: Sorry for ending up ranting… Had a tough 24 hours where we were nearly forced to pull an all-nighter to solve a critical bug in one of our client’s websites…
I solve problems in Python almost exclusively.
For inputs you can use input().split() where inputs on a single line are separated by spaces. Further as these will be strings you will have to map them to integers. This process is adequately fast and I haven’t faced any TLE problems because of large inputs.
Regarding function calls, these will be slow. Avoid repeatedly calling functions, try integrating them in your code instead. However, I haven’t faced any TLE issues even when I have made multiple function calls, although it visibly takes more time.
Thirdly, brute-force methods will almost always give you a TLE and the solution generally involves a trick/maths optimisation to reduce the number of computations. Once you have figured this out, language of choice is irrelevant for 99.9% questions (Though they are a few questions where C++ is better).
Lastly when you get a TLE, the judge will interrupt your execution at 0.01s more than the time allotted, hence it will always show TLE 5.001s this does not mean your code was just 0.01s slower, it just means the judge interrupted the execution at that point.
All the best for your future contests!
EDIT: Python lists are also not very memory efficient nor are they time efficient. If you want to create and perform operations on large matrices use numpy(I think codechef allows), but you won’t have numpy elsewhere.
My solution in C is to use one single and low-level read command to read the whole input in one go. I allocate a buffer for the maximum input that can be expected and read all in one go into this buffer.
Since I know the format of the input and don’t have to check for correctness of the format, I can simply read the respective next item from the buffer whenever I need this in my algorithm. No need to use scanf() functions with all the formatting overhead. I have functions like ReadULONG(), ReadULLONG() and ReadCHAR(). This reduces IO and conversion of strings to ints to the absolute minimum.
I assume that you can do the same in any other language.
First of all, I am so sorry for not being able to respond to your replies earlier…
@dardev Your code for the Bacterial Reproduction was brilliant… And, I hope that I will be able to reach your level of mastery one day… Thank you for inspiring me and your wonderful insights…
Like @trikster9 mentioned, my tendency to go for solving the problem in the simplest manner possible, leads me to not focus on identifying the mathematical aspects of the problem… Like the one in ‘SAKTAN’…
Also, @trikster9 your advice and insights have brought a great deal of comfort to me… I came to this site, to cover the gaps that I know I have when it comes to data structures & algorithms… I guess it is mainly due to my lack of confidence when it comes to maths…
It is an area that I am still improving as I try to put some time into mathematical subjects important in CS like Linear Algebra and Discrete Maths, etc…
And, last but not least, @amigaforever my approach to inputs is similar to yours… But, I am still experimenting with what style is fit for me, as I continue my march towards becoming a better programmer…
Thank you all of you once again for all of your help and patience, in answering my questions…