Factors that do harm to the speed (python)
I came up with the idea of summing up 2&5 from four directions during the test, but get TLE all the time, so I play around and see which factors did harm to the
I came up with the idea of summing up 2&5 from four directions during the test, but get TLE all the time, so I play around and see which factors did harm to the speed.\n1. Initially I used two 4-dim arrays to store the sums of 2&5 for four directions\n```\nlt = [[[[0 for k in range(2)] for l in range(2)] for i in range(n)] for j in range(m)]\nrb = [[[[0 for k in range(2)] for l in range(2)] for i in range(n)] for j in range(m)]\n```\nalong with a function\n```\ndef addl(a,b):\n    return [a[i]+b[i] for i in range(len(a))]\n```\nto add up the 1d array for [#2,#5]. This got TLE at 48 / 54 test cases.\n\n2. Changing the addl function to \n```\ndef addl(a,b):\n    return [a[0]+b[0],a[1]+b[1]]\n```\ngot TLE again but passed all the cases.\n\n3. Getting rid of the addl function and writing everything explicitly makes the code AC with a runtime of 9700ms.\n4. Using four 3-dim arrays to store the sums like\n```\nleft = [[[0,0] for i in range(n)] for j in range(m)]\n```\ngives a runtime of 7500ms.\n\n5. Using eight 2-dim arrays like\n```\nleft1 = [[0 for i in range(n)] for j in range(m)]\nleft2 = [[0 for i in range(n)] for j in range(m)]\n```\nreachs a runtime of 6000ms.\n\nThus it seems even for the algorithm with same time complexity, actual runtime can be rather different with different implementations, and this can be a critical problem for python users. \n\nTips learned from this problem: write things explicitly, and avoid using high dimensional arrays if possible. \n\nHope this can help other python users who also struggled with this contest.
['Python']