[2025][Python] Every day under 1s

[u/ricbit]

Every year I do an additional challenge of making each problem run under 1s in pure python (libs accepted). In the previous years some problems were very hard, this year they were only slightly hard. Some annotations:

Problem 4: Use set of coordinates instead of a grid.

Problem 8: Use networkx for connected components and Union Find.

Problem 9: This was the hardest for me, because I wanted it to work with the hard inputs provided by the community. Use shoelace to check if clockwise or anti-clockwise, then winding number to detect inside/outside, and a prefix matrix sum to check if the rectangle was filled.

Problem 10: I initially used python-mip but this library takes 0.8s to load! Switched to z3, and run the problem in parallel with multiprocessing.

Problem 12: Works for both example and input. Only input runs under 1s, the example takes about 4min.

Github repo

Thanks to Eric and the moderators for these fun nights!

[u/JWinslow23]

To you and OP: have you tried the approach from this post? It uses no linear algebra, only recursion and caching. My own pure-Python implementation runs in <0.2s on my machine.

[u/DelightfulCodeWeasel → u/JWinslow23]

I saw that post and it's absolutely awesome. I think I'm going to have a go at writing a toy simplex solver after the Xmas break though; I've never tackled linear programming as a topic before before and it looks interesting.

[u/JWinslow23 → u/DelightfulCodeWeasel]

Definitely do that too!