Noureldin's blog

A tale of two Kirchhofs
By Noureldin, history, 4 years ago, In English

I solved spoj's RESIST today, which incidently is also available on timus, to me it seemed like an excersize in solving linear equations, Kirchhof's current law yields a system of $$$(N-2) \times (N-2)$$$ equations which I solved using Gaussian elemination, that was enough to get AC on timus however it gave WA on spoj, I kept trying to find a bug in my code but I couldn't find any and I almost gave up on it when I decided to google for an algorithm or something that calculates the resistance and indeed I found cp-algorithms page on Kirchhof's matrix theoreom which got AC on both judges, naturally the next step was to stress test the two solutions to try to find a case where the first solution breaks, as of the time of writing the my stress test code has tried 26000+ random cases of different sizes and still nothing, which means that the case that breaks my first code on spoj has to have interesting properties, what do you think?

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

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

It is hard to say something for sure without actually looking at the code, so maybe you can share the code as well, and then some kind soul will be willing to look into it and try finding the root cause?

Some random guesses about what could go wrong:

  • SPOJ problem has larger N, so that sounds like a higher risk to run into precision issues if your Gauss is poorly written.
  • SPOJ has multitest.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is my first code: https://ideone.com/lzYvjn

    • I thought of this but the required precision is only 2 digits so that is very unlikely

    • yea, I know and both of my codes handle it

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

      Mb there are counter tests against default pivoting.

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

        can you elaborate?, I don't really understand what you mean.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      Gaussian Elimination has exponentially big precision errors. It can easily exceed 0.01 for $$$N \leq 100$$$.

      → Reply