UVa 10920 Spiral Tap gave me quite a bit of grief. What appeared to be a simple simulation pproblem resulted in several TL submissions and many hours of banging my head against my desk before I could find a fast enough solution. Thus my new philsophy: “The more bruises on your head, the more progress you’re making”. Here’s my first (failed) attempt. It just simulates the problem by changing the x and y coordinates as we move around the spiral:
What I failed to realize before I submitted this solution is the while loop has complexity O(n^2). With a maximum input size of 99999, this is much too slow. I also submitted a solution where I tried to precompute the cartesian coordinates, but this has the same complexity. I got an inkling that it was too slow when it took 30 seconds to accept my input :P. Here, then, is my accepted solution. The central concept is that the grid is divided into concentric “rings”, with the square of each odd integer in the top right corner. Notice in the diagram in the problem statement that 1 (1^2) is at the “corner” of a “ring” containing just itself, 9 (3^2) is at the corner of a ring that goes around the 1 ring, and 25 (5^2) is at the corner of a ring that goes around the 3 ring. While computing the cartesian coordinates directly takes O(n^2), finding the ring that contains the given cell can be found in O(sqrt(n)) time. Furthermore, the other corners of the rings are also odd integers that follow a pattern, so the “side” of the ring that contains the given cell can also be computed. Once the containing ring and the containing side of that ring are found, we do a little math to get the cartesian coordinates, and we’re done!