FCTRE in python

general
1

Problem:

I have checked a solution by FluentAlgorithms as shown in this video:

I extracted the Code (in c++) and checked that it passed all tests
https://www.codechef.com/viewsolution/31875160

Then i converted the code to python (pypy):
https://www.codechef.com/viewsolution/31876311

Unfortunately only the first test passed, all other tests gave TLE.
Now my question is, is python really so slow?
It is the same algorithm and should pass all tests.
I can’t understand why this isn’t so. Maybe somebody can help.

Greetings
Bewoods

1 Like
2

I had asked @dvyn01 during the contest regarding this that tester should check whether it is possible to get AC in python3/2 or pypy3/2 in this question.
He responded that intended solutions would pass under this time limit.
But many C ++ passed this limit and very rare java solutions passed this limit and python solutions were not able to pass this time limit.
I try to optimize to maximum extent for 3-4 days.
My solution link:- CodeChef: Practical coding for everyone
If there was any problem with the multiplier of python or time limit for python please rejudge python solutions.
@admin Please look into this matter because this has affected a lot of python users.

1 Like
3

I too spent my time to optimise my solution for about 3-4 days. Still just managed to get 40pts. It was failing (TLE) for the same four subtasks. Interestingly for some random test cases which I created myself were resulting the algorithm to run in time limits. I don’t know what kind of data was there in those four subtask files.
Link to my submissions: CodeChef: Practical coding for everyone

4

In my opinion, multiple array creation/initialization is slowing down Python in comparison to C++

5

I was using same mo’s algorithm from same blog he mentioned
though there were many things like block size or way of sorting queries that prevented similar cpp solution to get 100 on those particular test cases
Itis just some values worked better on the test cases used I don’t think it was fair but what can i do about that also don’t care as cc was never very friendly with python anyways ( :heart: leetcode )

Moving on intially even with mo’s algorithm i didn’t passed 2 case of 2nd subtask
here are somethings i did to get that 40 atleast:

  1. moved all functions into the body
  2. use fast input output
  3. initialized with * like list of n zeros as [0]*n
  4. hard-coded factor of first 1000 numbers
    5 hard-coded all primes required for factorization
  5. replaced dictionary check for a key with try except

all this combined cleared that 2nd test case and i got 40 :grin: :grin:

6

You can use Numpy to get C level speeds in array operations…

2 Likes
7

though that’s in case you are working mostly with mathematical operation as numpy already know datatype of element it will be fast not c level fast i think

there are often cases when it actually acts slower than lists
it is solely depend on what is problem
for my implementation here numpy didn’t do anything but sometimes it is highly advantageous

(it is also not supported very well by pypy in case you occasionally try your luck by submitting same code in pypy :stuck_out_tongue: )

edit: codechef also support pandas i think that too can help sometimes overall you have to fight different battles when you bring python to fight on codechef

8

I was too lazy to convert that long python code to cpp. :stuck_out_tongue_winking_eye:

9

I have initialized most of the lists in global and are initialized once.So I think there might be another reason for the tle in subtask3.

1 Like