Judging the Southeast Region

This problem was not one of the problems we had considered to be World-Finals-Hard, but yet no team solved it. This was disappointing. The fundamental algorithm is actually pretty simple – but the input numbers were so large that the solution needs some trickery in order to complete in time. That trickery introduces a bit of tedium and boundary cases, which is probably why no team managed to solve it.

Check out the Judge Input, the Judge Output, the main Solving Program, and another in Java, and one in C++.

A solution outline follows in the spoiler.
[spoiler]
The fundamental algorithm is simple:

For Each Tree
    Find the closest horizontal path north of this tree
    See if there are any trees with the same X between this tree and the path, blocking the view
    Find the closest horizontal path south of this tree
    See if there are any trees with the same X between this tree and the path, blocking the view
    Find the closest vertical path east of this tree
    See if there are any trees with the same Y between this tree and the path, blocking the view
    Find the closest vertical path west of this tree
    See if there are any trees with the same Y between this tree and the path, blocking the view
    If all four views are blocked, then the tree can't be seen
    Else it can be seen, add one to the Visible count
End For 

The problem is the large number of paths and trees. Locating the closest paths, searching through to see if any trees block the view, can add up to O(n^2), and with the data set size, that just won’t do.

There’s a simple trick that we’ll use to cut down on the iterations – sorting. First, separate the paths into horizontal (by Y) and vertical (by X), and sort each of these lists. For any tree, the paths immediately north and south will be next to each other in the horizontal array. Ditto for the east & west in the vertical array. Finding both north and south is just a binary search, O(logn). Same for east and west.

Now, about the trees. Start by sorting them by X, then Y. What I mean by that is: sort them by X, but if two trees have the same X, then use Y as a tiebreaker. Now, all the trees with the same X are grouped together, ordered by Y. That means that, if any tree is going to block the next path north, it’s going to be the next tree in the list, and likewise, for south, it’ll be the tree immediately previous. It’s cost us O(nlogn) to sort the list, but finding the tree that blocks the view (if there is one) is reduced to O(1). For east/west, it’s the same deal, but we must re-sort the list by Y, then X.

That’s about it. There are lots of boundary conditions to consider – what if there’s no path to the north? or south? or east? or west? what if there’s no next/previous tree? Lots of care must be taken, but the algorithm, at its core, is really pretty simple.
[/spoiler]