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)

The dynamic RMQ problem goes as follows:

Given an array of integers $$$a$$$ of length $$$n$$$ and $$$q$$$ queries of $$$2$$$ types:

1. $$$l\ r$$$ — find the minimum on $$$a[l..r]$$$
2. $$$i\ x$$$ — make $$$a_i = x$$$

If the number of updates $$$\gt \gt$$$ the number of queries (which may occur in MO algorithm for example, where we can have $$$O(n)$$$ min queries and $$$O(n\sqrt n) $$$ updates), what is the most efficient way to solve the problem?

We obviously need smth faster than $$$O(\log(n) )$$$ per update (which is achievable with a ton of ways), like $$$O(1)$$$ or maybe $$$O(\log{\log{n} }) $$$.

I though about it for a while but wasn't able to come up even with sublinear solution for querying min while preserving $$$O(1)$$$ update time.

Current rating graph looks like this:

But it should look like this:

MikeMirzayanov, when rating graph will be improved?

How to solve today's C problem if alphabet is not $$$26$$$ characters but rather $$$O(n)$$$? I could only come up with simple offline $$$O(q \sqrt n)$$$ solution using basic MO algorithm. Any ideas?