hackercupai/hackercup huggingface dataset:
The key insight is that the squared distance \(||p - t||^2 = (p_x - t_x)^2 + (p_y - t_y)^2\) between a well at point \(p\) and tree at point \(t\) can be obtained by treating each of the two axes independently.

We can project the \(x\)-coordinates of trees \(t_1, \ldots, t_N\) onto a number line (the \(x\)-axis), and likewise for the \(y\)-coordinates onto the \(y\)-axis. There may multiple trees with a given \(x\) or \(y\), so we can precompute their frequencies in arrays \(\text{xcnt}[x]\) and \(\text{ycnt}[y]\). The time and space complexities will both be linear on the largest possible values of \(x\) and \(y\), which are only up to \(3{,}000\).

Then, we see that the inconvenience of a well at point \(p\) can be computed as:

\[\begin{aligned} \sum_{i=1}^{N} \lVert p - t_i \rVert^2 &= \sum_{i=1}^{N} [(p_x - A_i)^2 + (p_y - B_i)^2] \\ &= \sum_{i=1}^{N} (p_x - A_i)^2 + \sum_{i=1}^{N} (p_y - B_i)^2 \\ &= \sum_{x=0}^{3{,}000} \text{xcnt}[x]\cdot(p_x - x)^2 + \sum_{y=0}^{3{,}000} \text{ycnt}[y]\cdot (p_y - y)^2 \end{aligned}\]

Computing this directly will take \(\mathcal{O}(3{,}000)\) steps on each of the \(Q = 500{,}000\) queries, for a total of ~\(1.5\) billion steps. This should already be fast enough to pass within the \(6\) minute time limit. However, we can optimize further by precomputing the answer for all \(3{,}000^2\) possible coordinates, after which, each query can be answered in \(\mathcal{O}(1)\).

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