Coding Practice: Day 2

Three easy problems and one pretty hard problem. The three easy ones were all pretty much simulation or simple BFS.
One thing I realized was that I've been implementing queues (e.g. when doing a BFS) as vectors, and just traversing the whole thing. It's much more efficient to just use the STL queue, so there isn't as much wasted space. I'm too used to using vectors...
The tough problem was LINELAND (there wasn't even a solution on the NWERC '06 site, which was the source of the problem). My solution was basically just to try placing the segment of lenght L starting at all the x values of the given points, then do a ternary search between every consecutive pair of x values. Here, I augmented the list of possible x values by adding x[i] - L to take into accounting the segment of length L ending at x[i]. It's not too hard to show that the area is piece-wise quadratic, so this works.
An interesting note is that while I could've just solved all those quadratics (would've made the solution faster? too many cases, though) it was much easier to just implement the ternary search. The hard part was dealing with double precision when you're at the corners.
I noticed I'm getting into the habit of optimizing problems I've solved, coming up with heuristics to speed them up, etc. It means I won't be able to work on as many problems as would otherwise, but I'm learning more this way :)

More Notes

So, I made a few more optimizations to LINELAND. For finding the left and right boundary points for the segment of length L at a given position, I just binary searched. Learned something subtle about the difference between finding a lower/upper bound (a +1 index difference). More importantly, I got to implement the sqrt(N) solution to range min queries. Got this about 7x faster.

Coding Practice