How many neighbours to ask about depth
A seismologist wants to guess from the position of the epicentre alone how deep an earthquake happened: shallow foci (less than 70 km below the surface), intermediate (70–300 km) or deep (300 km and more). The method is k nearest neighbours over the catalogue of shocks that have already happened. It remains to choose k.
Check each k from 1 to K honestly, without a separate validation set: remove each shock from the catalogue in turn and ask the rest about it. A neighbour is another shock of the catalogue; the distance is the ordinary straight-line one in space; neighbours are ordered by distance, and at equal distance by their number in the input; on a tie in votes, the class of the contender nearest of all wins. For each k count how many shocks are guessed right, and name the best k (the smallest of equal ones).
Three tests are real earthquakes of magnitude 5 and above in 2015–2025 from the USGS catalogue: the epicentre is given as a point on a sphere of radius 6371 km, with coordinates in kilometres.
Input
The first line holds the numbers n and K (2 ≤ n ≤ 1000, 1 ≤ K ≤ min(50, n − 1)). Each of the following n lines holds integer coordinates x, y, z (at most 10⁴ in absolute value) and a depth class c: 0 shallow, 1 intermediate, 2 deep.
Output
The first line holds the best k and the number of shocks guessed right with it. The second holds K numbers: how many shocks are guessed right with k = 1, 2, …, K.
Examples
Example 1
7 4 0 0 0 0 10 0 0 0 0 10 0 0 100 100 0 2 110 100 0 2 105 104 0 0 50 50 0 1
1 3 3 3 3 3
Limits
- Time · Python
- 8000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The head-on solution, for each k finding the k neighbours of each shock anew and voting, costs O(K·n²), up to 50 million distances. What do the answers for k = 5 and k = 6 have in common for one and the same shock?
2Hint 2
The six nearest neighbours are the five nearest and one more. Sort each shock’s neighbours once and add the votes one at a time. How can the winner be found quickly with the tie rule?
3The idea
For each shock find, once, the K nearest other shocks in the right order. Then k grows from 1 to K, and at each step exactly one vote is added. There are only three classes, so the winner can be chosen anew at each step in O(1): whoever has more votes, and on a tie, whose first vote came earlier. “The first vote came earlier” is the same as “the nearest of the contenders” in the tie rule.
This is leave-one-out cross-validation: each example in turn becomes the exam for the rest. A held-out set is cheaper but spends part of the data on checking only; here everything is checked, and no shock votes for itself.
4Walkthrough
For shock i go over all j ≠ i, compute the squared distance in integers (at most 1.2·10⁹, so even a 32-bit integer suffices) and keep the K best pairs (distance, number). Then go through them, updating the vote counters and the position of each class’s first vote, and after each step add one to that k’s score if the winner matches the real class. At the end choose the k with the highest score.
On the real catalogue small k turn out best, one to three neighbours, and more than eight hundred shocks of a thousand are guessed right. Deep shocks are not scattered over the planet: they run in bands along the plates sinking into the mantle, and the nearest shock is usually of the same depth.
4+Solution
5Complexity
O(n² log K) to find the neighbours and O(n·K) to count: a million distances with n = 1000.
6Common mistakes
- A shock among its own neighbours. The most common mistake in checking models: it is nearest to itself and always guesses its own class, and k = 1 looks perfect. The example catches this.
- Each k from scratch. Correct, but 50 times slower.
- A tie by the smaller class number. With even k ties are frequent, and the answer diverges from the rule.