During the past week I've been working on implementing and optimizing Gauss elimination algorithm for sparse systems of linear equations (SLE). I took 2028E - Alice's Adventures in the Rabbit Hole as a reference: constructed 2e5 linear equations and put them into my solver. And starting from 20s runtime was able to optimize my algorithm to 1s (300847774), comfortably passing intended 2s TL.
Now I wanna try my implementation somewhere else. Can you share some other problems which are solvable by constructing big sparse SLE?
Yesterday contest C: https://mirror.codeforces.com/contest/2055/problem/C
Thanks! Got AC in 0.43s (300892471) using long double for calculations. innocentkitten wrote in the editorial that it would be too slow to directly solve SLE, but was wrong :D
Try https://mirror.codeforces.com/contest/1844/problem/G.
I've actually tested some sparse SLE heuristics when preparing this problem, and they didn't come close to working on caterpillar trees. Your implementation is much better than mine, so I'm curious how well it does.
This one 2032E - Balanced.
Passed in 0.82s (300905162) using 4e18+37 modulo for calculations.