I need help regarding a question which was there in November cook-off 2017:
problem link: https://www.codechef.com/COOK88/problems/ONCHESS
The problem was pretty simple and my solution for it worked but unfortunately it was not that good in terms of time complexity. Can any one please help and tell how can i reduce time of execution here.(language used: Python 2.7)
Solution link: https://www.codechef.com/viewsolution/16321937
if(j!=k and j not in list1 and k not in list1)
Do no use not in operator, it does a linear search. Use a binary array instead to identify if you already have matched that player or you can use python dictionary, that should do the job too.
int(j[0]) in range(int(k[1]),int(k[2])+1) and int(k[0]) in range(int(j[1]),int(j[2])+1)
range() function creates a list that takes linear time and then you use in operator that takes linear time too. instead replace them with relational operators and compute them in constant time.
i.e.
k[1] <= j[0] <= k[2]
That should do the job
in and not in are O(n), so your solution is O(n^3)
Here’s is my python 3 code
[1]
[1]: https://www.codechef.com/viewsolution/16333417