The runtime for this algorithm is $O(n^3)$, but I've seen at least two problems where the intended solution is using this algorithm and $N = 1000$. (The ones I'm thinking of are: https://open.kattis.com/problems/engaging and https://open.kattis.com/problems/cordonbleu ). It runs in under 1.5 seconds for both. That's about 7 times faster than I'd expect if we actually had to use $1000^3 = 10^9$ operations. My main concern is being able to estimate how long the algorithm will take to run, in a contest setting. Is it possible to generate a worst case where we need all $n^3$ operations? Does this algorithm have a provably low-constant factor for being $O(n^3)$? Or is it like a flow problem, where we can say a strict upper-bound and know that the algorithm will usually out-perform this estimate, but it's harder to give a precise estimate? Given what I know about the similarities with flow, I'm guessing it's the latter, but I wanted to ask if there's a better way to estimate how long this algorithm will take to run.↵
↵
(Just FTR I've read the KACTL implementation, and kind of understand how it works, but it's not obvious how many times that inner while loop is called while updating potentials).
↵
(Just FTR I've read the KACTL implementation, and kind of understand how it works, but it's not obvious how many times that inner while loop is called while updating potentials).
