tyristik's blog

Looking for problems to test Sparse Gauss Elimination implementation
By tyristik, history, 6 hours 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?

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

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Yesterday contest C: https://mirror.codeforces.com/contest/2055/problem/C

→ Reply
  • »
    »
    17 minutes 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