So, seriously? I’m tired of Diophantine equations.
10090 – Marbles
This problem ate up three late evenings in Utah, when I probably would have gotten more enjoyment out of reading. The frankenstein of a solution is redundant and crude, but I was so damn tired of the problem once I got AC, I didn’t care anymore.
It took a while to get close, even though the problem isn’t that hard at first glance. Once I got close, a few things bit me. The first was underflow, which I fixed by dividing out the gcd to begin with. Duh, learn2maths. The second was being the victim of duplicated code, and not adjusting everything correctly. I intentionally hand-rewrote the duplicate blocks to avoid this, but still managed to fuck it up. The real lesson is don’t duplicate code, but refactoring and using clever functions in programming puzzles is often more hassle than it’s worth. This is, of course, why being good at programming puzzles doesn’t imply any sort of talent in the real world. But what really screwed me up was a misplaced break where I should have had a continue, causing my program to prematurely abort and terminate. This was giving me a WA and the illusion that my code was fast, when in fact it was just aborting very early on the input stream and terminating.
After fixing all that stupid stuff, I was back to TLE due to my ignorant fondness for iteration over math. Doing more math and less iteration should have fixed the problem, but it didn’t, I was still getting TLE. Why? Because I’d made my algorithm too robust; a mistake I made earlier in the algorithm produced an incorrect answer, but the robustness of the algorithm caused it to fix itself later in the process. Unfortunately, this robustness came with a massive performance penalty, which was trivially exploited by the judge.
Sometimes I’m convinced I’m not really smart enough to be employed as a software engineer.
10089 – Repackaging
I got help from the forums; my solution follows from that.
And with that, I’m done with chapter seven. That’s probably all I’ll do while on vacation, looking forward to hitting chapter eight when I get back home.