Checklist NOAI Singapore 2025 Final · Task 2
SOTA-AI Editorial
K-Means Clustering
Implement k-means clustering with given initial centroids and return the final centroids.
Hints
Hint 1
Use the supplied centroids as-is and compute each point's distance to each one.
Hint 2
Assign by the smallest distance; ties can deterministically go to the first centroid.
Hint 3
Take coordinate-wise means for nonempty clusters and keep the previous center when a cluster is empty.
Hint 4
Stop on unchanged centers or after `max_iterations`; round the final centers to four decimals.
The solution in one line
The supplied example converges to `[(2.0, 7.3333), (10.0, 2.0)]`, matching the official notebook.
The editorial
NOAI Singapore 2025 — K-Means Clustering
Problem domain: Unsupervised learning, clustering, algorithm implementation
Evaluation metric: Return final centroids rounded to four decimal places; the task is worth 25 marks. No public automated grader or hidden test set was found.
Abridged statement
Implement K-means for a list of coordinate vectors, a requested cluster count, initial centroids, and a maximum iteration count. Assign each point to its nearest centroid, replace each nonempty cluster's centroid with its member mean, retain a previous centroid for an empty cluster, and stop at convergence or the iteration limit.
Data analysis
The fixed example has six two-dimensional points. Three lie around x = 2 and three around x = 10; the supplied starting centroids (2, 2) and (10, 1) already seed the two visible groups. This is a small unlabeled toy set, not a train/test dataset. There are no missing or categorical values.
Experiments
The released example was run with k = 2 and max_iterations = 10. Both the local implementation and the official notebook return:
[(2.0, 7.3333), (10.0, 2.0)]
The first center is the mean of the three points with first coordinate 2; the second is the mean of the three points with first coordinate 10. No empty cluster occurs in this example.
Solution
The implementation is k_means_clustering.py. It uses vectorized squared distances and argmin assignment, updates each nonempty centroid with a mean, leaves an empty centroid unchanged, and rounds only the returned centers.
Score evidence and limits
Measured result: Exact centroid match to the output of the official solution notebook on the released example. The task is worth 25 marks, but no public grader or further scored cases were located. The result supports a full-credit implementation for the released example; it is not an organizer-issued 25/25 score.
Implementation and diagnostics
Tie assignments go to the first centroid, matching NumPy's deterministic argmin behavior. Convergence is checked with absolute tolerance 1e-12; otherwise, iteration stops at the requested limit. Internal centers retain full precision, and only final values are rounded. Input shape checks catch mismatched dimensions and an invalid centroid count.
Compute and footprint
The method uses CPU NumPy arrays and a few matrix-sized distance calculations. The supplied six-point case runs in milliseconds; no GPU or training framework is needed.
Alternatives considered
- Random initialization is unsuitable because the task explicitly supplies starting centroids.
- Reseeding empty clusters can produce a different answer; retaining the existing center is the statement's suggested policy and matches the reference behavior.
- Rounding at every iteration can alter later assignments on finely balanced data; rounding only the result follows the stated output rule while preserving standard K-means updates.
Sources and reuse
- SOTA task summary
- Official NOAI 2025 programming questions and solution notebooks
- Official NOAI learning-resources page
The task source does not state a license. It specifies Python 3.9 standard library and NumPy. This report paraphrases the statement, and the code is independently written rather than copied from the official solution notebook.
Code
Solution code
"""NOAI Singapore 2025, Section 2 Question 2.
K-means with caller-supplied initial centres, deterministic nearest-centre
assignment, empty-cluster retention, and four-decimal output.
"""
from __future__ import annotations
from typing import Iterable, Sequence
import numpy as np
def euclidean_distance(a: Sequence[float], b: Sequence[float]) -> float:
"""Return the Euclidean distance between two coordinate vectors."""
a_array = np.asarray(a, dtype=float)
b_array = np.asarray(b, dtype=float)
if a_array.shape != b_array.shape:
raise ValueError("a and b must have the same shape")
return float(np.linalg.norm(a_array - b_array))
def k_means_clustering(
points: Iterable[Sequence[float]],
k: int,
initial_centroids: Iterable[Sequence[float]],
max_iterations: int,
) -> list[tuple[float, ...]]:
"""Return k-means centres, rounded to four decimals.
Empty clusters keep their previous centre. Ties go to the first centre,
matching ``argmin``'s deterministic behavior and the released example.
Centres remain full precision during iteration; only the returned answer
is rounded.
"""
data = np.asarray(list(points), dtype=float)
centres = np.asarray(list(initial_centroids), dtype=float)
if data.ndim != 2 or data.shape[0] == 0:
raise ValueError("points must be a non-empty collection of vectors")
if centres.ndim != 2 or centres.shape[0] != k or k <= 0:
raise ValueError("initial_centroids must contain exactly k vectors")
if data.shape[1] != centres.shape[1]:
raise ValueError("points and centroids must have matching dimensions")
if max_iterations < 0:
raise ValueError("max_iterations must be non-negative")
for _ in range(max_iterations):
distances_squared = np.sum(
(data[:, np.newaxis, :] - centres[np.newaxis, :, :]) ** 2,
axis=2,
)
assignments = np.argmin(distances_squared, axis=1)
updated = centres.copy()
for cluster in range(k):
members = data[assignments == cluster]
if members.size:
updated[cluster] = members.mean(axis=0)
if np.allclose(updated, centres, rtol=0.0, atol=1e-12):
centres = updated
break
centres = updated
rounded = np.round(centres, 4)
return [tuple(float(value) for value in row) for row in rounded]
if __name__ == "__main__":
points = [(2, 4), (2, 8), (2, 10), (10, 2), (10, 4), (10, 0)]
initial_centroids = [(2, 2), (10, 1)]
print(k_means_clustering(points, 2, initial_centroids, 10))Editorials are written by members of the SOTA community, not by the olympiad. The official statement and scoring win wherever an editorial differs.