hackercupai/hackercup huggingface dataset:
Another way to view the half-plane constraint is that you may only stop at points that are vertices of the convex hull of all \(N\) points, which can be computed in \(\mathcal{O}(N \log N)\) time.

There are many incorrect approaches which are broken by the samples. For instance, it is not always optimal to travel across either the upper or lower hull, nor is it obvious how a two pointer solution would work correctly in the general case with the nonlinear cost function involving \(\max()\).

One potential solution is to construct the full graph of all \(N\) nodes with edge weights set to the brand damage between houses, and run Dijkstra's algorithm. This solution is correct, but at first seems to have a time complexity of \(\mathcal{O}(N^2 \log N)\), much too slow for \(N = 1{,}000{,}000\). However, we are only interested in points on the convex hull border — how many vertices can it have?

Let's treat the convex hull edges as vectors lined up tip-to-tail. It turns out that even if these vectors are chosen optimally, one can only fit a convex hull of \(\mathcal{O}(a^{2/3})\) vectors in an \(a \times a\) grid. To see why, consider the vectors in the lower-right quadrant of the hull, sorted radially. In the worst case, the hull will resemble a circle centered at \((500\,000,\,500\,000)\). What is the maximum number of vectors we can generate such that:
- the sum of the vectors' \(x\)-coordinates is at most \(500{,}000\),
- the sum of the vectors' \(y\)-coordinates is at most \(500{,}000\), and
- no vector is a scalar multiple of another?

There aren't that many unique vectors with both small \(x\)- and \(y\)-coordinates. The total number of vectors we can pick is on the order of \((10^6)^{2/3} = 10^4\). In practice, the worst-case convex hull only consists of about \(35{,}000\) vertices. We've included a script, [lemonade_life_count_hull_vertices.py](https://www.dropbox.com/s/nqolapgsm4y6313/lemonade_life_count_hull_vertices.py?dl=0), in the Dropbox for demonstration. This brings the running time of an \(\mathcal{O}(E \log V)\) Dijkstra's implementation to \(35{,}000^2\log_2(35{,}000) \approx 18\) billion steps, which is almost feasible if not for constant factors and the \(\mathcal{O}(E)\) space complexity.

To get the rest of the way there, we can take advantage of the fact that the graph here is complete. On complete graphs, it is more efficient to run Dijkstra's *without a priority queue*. Instead, we can manually search in \(\mathcal{O}(V)\) time to "dequeue" the next node of minimum tentative distance at each step, ridding ourselves of the \(\log(V)\) factor due to heap pushes. We end up with a running time of \(\mathcal{O}(V^2) \approx 1.2\) billion steps, with a low constant factor and \(\mathcal{O}(V)\) space.

With a pessimistic assumption of \(10^8\) steps per second, one would estimate that each of the \(15\) large cases takes under \(12\) seconds, thus comfortably finishing in the \(6\) minute limit. In practice, our official C++ implementation processes the whole file in under \(20\) seconds on a modest laptop.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=D_ZXdemwpgk)