Блог пользователя Noureldin

Автор Noureldin, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.