This is a writeup of the problems my team solved in the Murcia contest, which we were participating in as preparation for SWERC. Those people are way better than us, but we will not give up!
The problems are given the UVa numbers that will soon appear.
12962 Average Reuse Distance At first read this problem seems easier than it really is. But it’s not a hard problem, it’s actually a fairly straightforward simulation.
This is (part of) the notebook for my SWERC team, Not Paranoid Enough. We still accept name suggestions. There are comments before each snippet or formula for explanation, but maybe they should be removed before the contest. There are explanations on variations, but maybe they aren’t needed either.
Debugging: common mistakes Graphs may have repeated edges If you can output the solution with part of the input, make sure to still read all the input.
The information in this post is taken from the sources listed in the Sources section at the end of it. If you don’t care about understanding the algorithm and need an implementation now, skip to the Implementation subsection.
Why? Why would anyone want to multiply polynomials in $\Theta (n \log n)$ instead of the naive $\Theta(n^2)$ time? Sometimes happens. I did when I got confronted with the UVa Online Judge 12879 Golf Bot problem.