Python 3 - TLE in MAGICSTR

disjoint-set
magicstr
python3
tle
union-find

#1

So, I was trying to solve the MAGICSTR problem here.

After reading the editorial and going through some blogs, I made an implementation of the Union-Find Data Structure in Python and tried to solve the problem using it. But I am getting a TLE. Here is the link to my last solution. In the data structure, I used both path compression and union by rank. Please help.

Thanks.


#2

There was one small bug in your solution, you missed out N in your list of midpoints. But anyway the time limit is simply too strict for Python I think :frowning:
It is quite easily accepted using PyPy, but I just couldn’t get it to pass using Python 3.5. I tried to optimize it by getting rid of anything unnecessary and all function calls, but it still times out. Here is my last version if it helps you.


#3

Thanks a lot! I was worried that my implementation was incorrect. Thanks again. :slight_smile:


#4

Sure thing. I use Python too, so it’s good to know cases like these to keep me from relying too much on it :stuck_out_tongue:


#5

At last… https://www.codechef.com/viewsolution/15609514 :stuck_out_tongue: