### mixed_juice717's blog

By mixed_juice717, history, 3 months ago,

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).

• +93

By mixed_juice717, history, 6 months ago,

Sometimes when you are contesting and problems are accepteding, round becomes unrated. Very much sad thing to happen! If rated contest becomes unrated makes people sad, then unrated contest becomes rated should make people happy! Ver y exciting news indeed. Now when you are doing well in contesting, but is unrated for you, it can be surprise rated and you surprise be happy :)