This blog will be useful for all those who never achieved Master but really wants to. Based on my experience, you can achieve Master by doing these steps:

1. Become GM on your main account

2. Create an alt and smurf Div.2+ contests until you reach Master.

3. ...

4. PROFIT!

Hope it helps, codeforcers!

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.net/contest/1823/problem/F ($$$n = 2e5, k = 6e5$$$, 0.96/2s, 302018850)

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

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

https://codeforces.net/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.net/contest/1844/problem/G (smart approach) ($$$57$$$ SLE with $$$n = 1e5, k = 2e5$$$, 3.57/5s, 301156684)

L:

https://codeforces.net/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?