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?

UPD: was able to optimize my implementation to 0.35s on 2028E (link) and crack some other problems. Here is the current statistics of my algorithm. $$$n$$$ is the number of variables, $$$k$$$ is the number of non-zero coefficients in the matrix. I'm still looking for more problems to test!

W:

https://codeforces.me/contest/1823/problem/F ($$$n = 2e5, k = 6e5$$$, 0.96/2s, 302018850)

https://codeforces.me/contest/2028/problem/E ($$$n = 2e5, k = 6e5$$$, 0.35/2s, 301505556)

https://codeforces.me/contest/2032/problem/E ($$$n = 2e5, k = 6e5$$$, 0.78/2s, 301921985)

https://codeforces.me/contest/2055/problem/C ($$$n = 2e3, k = 4e3$$$, 0.43/2s, 300892471)

https://judge.yosupo.jp/problem/sparse_matrix_det ($$$n = 3e3, k = 1e4$$$, 0.57/10s, 261477)

https://codeforces.me/contest/1844/problem/G (smart approach) ($$$57$$$ SLE with $$$n = 1e5, k = 2e5$$$, 3.57/5s, 301156684)

L:

https://codeforces.me/contest/1844/problem/G (straightforward approach) ($$$n = 1e5, k = 3e5$$$, ~3600/5s on caterpillar trees)