tyristik's blog

Looking for problems to test Sparse Gauss Elimination implementation
By tyristik, history, 6 weeks ago, In English

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)

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yesterday contest C: https://codeforces.me/contest/2055/problem/C

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Try https://codeforces.me/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.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Man, caterpillar trees are real killers! Even though I was able to optimize my implementation even further, achieving 0.35s on initial problem, on $$$n = 1e5$$$ caterpillar tree it takes about an hour on my laptop. I've also calculated the number of operations it does with matrix and dependency is exactly cubic:
    $$$5e7$$$ operations for $$$n = 1e4$$$ caterpillar tree
    $$$1.3e9$$$ operations for $$$n = 3e4$$$ caterpillar tree
    $$$5e10$$$ operations for $$$n = 1e5$$$ caterpillar tree

    But using a smart approach with solving 57 SLE passed in 3.57/5s: 301156684

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This one 2032E - Balanced.

→ Reply