A tale of two Kirchhofs

Revision en1, by Noureldin, 2020-12-29 19:34:24

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?

Tags #kirchhoff

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Noureldin 2020-12-29 19:34:24 1113 Initial revision (published)