For Python Coders: Insane time constraint for Delicious Cake (Contain)

general
1

in the recently ended Long Challenge, I was unable to get full marks in Delicious Cake question when coding in Python. Though I was able to get partial marks but even after 30+ submissions, I was unable to get 100 in Contest. What I feel is Time Limit constraint for python coders on this question was really harsh. There might be some errors on my part but after contest, I saw very much less optimised CPP code getting 100 marks. For all the python coders, what can be done to prevent getting TLE from just language barrier at first? ( Python is 5x slow than CPP but Time limit is 2.5x ).

Screenshot from 2020-06-14 20-01-39
Screenshot from 2020-06-14 20-01-39856Ă—704 33.1 KB

3 Likes
2

I too was getting TLE. But using PyPy solved it. Of course, this is not a solution to the problem, but just in case you are stuck in the future.

2 Likes
3

Bro better go with c++

4

You can see this blog of codeforces : Python performance tips - Codeforces

1 Like
5

Thanks, I too submitted in PYPY. It helped in reducing my running time. It didn’t gave satisfactory results. And yes, that is not the long term solution

6

I know CPP is very much safe, but I find Python more appealing. Plus shifting to another language isn’t a permanent solution. If everybody has to submit in CPP, then why Codechef supports another language.

1 Like
7

Either you can learn all the ins and outs of python to perform well in CP or just have decent in depth knowledge of c++ and perform well in CP(same problem solving skills in both cases).
Also changing to other languages IS a solution. Ex:
for web dev : JS
for ML/AI : python
for cp : C++
for game dev : C++ / java / game engine.
It’s all about flexibility to adopt as a programmer.

P.S: If you really like python you should just ignore the drawback, learn more and overcome them with python.

1 Like
8

Thanks for sharing this. But the line “finally, realize that acceptable solutions to many Codeforces problems simply cannot be coded in Python, no matter how hard you try.” saddens me to the core. In a such big event like Codechef Long, this should not be the case. Maybe the problem setter had some test cases which was too harsh for python and not for Vectors(CPP)

9

the problem is the algorithm, not the language. Each time you build a CH you check each point of the hull with each point and then delete from the points list. Just each delete operation is O(N) so that procedure is O(N^2). Try to swap the point to delete to the back and then reduce the size of the vector

2 Likes
10

Thank you for the reply. I will surely think about it.

11

I honestly did the exact same thing. I may be not 100% correct, but I’m Sure of the Time Complexity of the each algo I used was best. Honestly better way was to use sets and then subtract the set from set of original points which was faster. My point being: My algo should definetly be giving a AC on all cases if done in CPP (wrt time Complexity). Thanks for sharing your thoughts.

14

Ultimately we most of us are doing this problem solving to land in a good company i guess, when all hiring platform give us decent time limit , as in google codejam they test every code on every language and give time limit much above that execution time that particular language. Please include python testers in your team so they can provide appropriate time limits. Python is 3rd most used competitive coding language , atleast consider that.

1 Like
15

Thanks, Finally somebody said it. That’s what I was trying to convey.

16

Now see other people solutions, maybe can learn something from every solution.

17

Thanks for sharing, I tried this too. I used Points in Polygon vector cross multiplacation instead of Ray tracing method. The binary search was giving similar running time but was also giving Runtime in one case. Maybe vector multiplacation part was going wrong somewhere but rest of the cases were executed similarly so I sticked to orginal. Thanks for sharing, This might help me somewhere.

18

Competitive programming is competitive so if you’re going to choose a slower language (like Python) you should be ready to deal with the potential setbacks and advantages of your chosen language.
There already exists a 2.5 multiplier, you should make use of that (Codeforces has same time limit for all), also submit your Python code through PyPy, it’s considerably faster (https://speed.pypy.org).

2 Likes
19

What I observed from my code was that my code was taking a few milliseconds more, I used binary search and PyPy compiler and got AC, moreover we can’t blame CodeChef for time limit because they just use a multiplier against the time taken by cpp, I did see some solutions in python and they were quite fast without using any of optimizations so we should be learning from them.

1 Like