I am requesting for help from python experts (e.g: pajenegod) regarding this issue.
Article: https://usaco.guide/general/choosing-lang
Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=992
Over here in this article, they mentioned that: "A comparable Python solution only passes the first five test cases:", "After some optimizations, this solution still passes only the first seven test cases:", "We are not sure whether it is possible to modify the above approach to receive full credit (please let us know if you manage to succeed)! Of course, it is possible to pass this problem in Python using DSU (a Gold topic):"
So I went ahead to try to optimise the approach (Binary Search with DFS) but I could only get 9/10 testcases to pass reliably. Very rarely, I will have 10/10 testcases passed, with the 10th testcase having ~3990 ms. I wonder if it is possible to get 10/10 testcases to pass reliably?
I have tried many approaches, including speeding up IO, using list comprehensions whenever possible instead of for loops, using bitwise operators to avoid slow tuple sorting.
I have also profiled my code and found that the valid() function is the one that is the bottleneck.
Here is the code:
from operator import methodcaller
def main():
lines = open("wormsort.in","rb").readlines()
n,m = map(int,lines[0].split())
loc = [*map(int,lines[1].split())]
edges = [[] for _ in range(n)]
lo,hi,mask = 0,m,0b11111111111111111
def valid(loc, mid):
component = [-1]*n
numcomps = 0
for i in range(n):
if component[i] < 0:
todo = [i]
component[i] = numcomps
while todo:
for child in [x[0] for x in edges[todo.pop()] if component[x[0]] < 0 and x[1] < mid]:
component[child] = numcomps
todo.append(child)
numcomps += 1
if component[i] != component[loc[i] - 1]:
return False
return True
# bitwise to avoid tuple sort
all_edges = [*map(lambda x: int(x[2]) << 34 ^ int(x[0]) << 17 ^ int(x[1]),
map(methodcaller("split", b" "), lines[2:]))]
all_edges.sort(reverse=True)
for i, val in enumerate(all_edges):
rhs = (val & mask) - 1
lhs = ((val >> 17) & mask) - 1
edges[lhs].append((rhs,i))
edges[rhs].append((lhs,i))
while lo != hi:
mid = (lo + hi) // 2
if valid(loc, mid):
hi = mid
else:
lo = mid+1
open("wormsort.out","w").write(f"{-1 if lo == 0 else all_edges[lo-1] >> 34}\n")
main()
Any tips or advice on how to speed this up would be greatly appreciated. Thank you!
Auto comment: topic has been updated by drugkeeper (previous revision, new revision, compare).
Auto comment: topic has been updated by drugkeeper (previous revision, new revision, compare).
There are tons of optimizations you can do. For one your algorithm doesn't really need the edges to be sorted. It just needs the edge weights to be sorted. So there is no reason to do the fancy
all_edges
sort.About your graph traversal. You say you are doing a DFS, but what you are doing is not a DFS. You are doing some weird mix between a DFS and a BFS. What you are doing still works, but it is not a DFS.
My prefered way to do a graph traversal is to do a BFS like this:
I think that changing your graph traversal to this could speed it up significantly.
Hi, thank you so much for the advice! I actually tried tuples before and thought that it did not really affect the performance.
I have changed my code to do tuple sort and added your graph traversal:
It is faster now, and could pass the last testcase more frequently, but still it fails more than 50% of the time. May I ask for more optimisation tips? Thank you!
Also, correct me if I'm wrong, your code for graph traversal is faster because:
I actually tried many ways to optimise this graph traversal (making a filtered list, calling todo.extend() instead of append, using list comprehension to assign the components, etc etc etc), but yours seem to be the fastest.
Here is the cProfile timing data (called on a randomly generated testcase), along with my code:
Profiling Data:
Code:
Less and simpler code runs faster in Python. If you can just use a standard for loop, then go for it. As for 3., I don't think
==-1
vs<0
matters at all.Btw about avoiding sorting the edges. The following is what I was thinking about when I said
your algorithm doesn't really need the edges to be sorted. It just needs the edge weights to be sorted
Thank you so much for the advice! I changed it up a bit and now it passes all the testcases reliably now. (Approx 3.7s/4s)
Here is the code: