Problem Statement

Run K-Means on 1D data and return the WCSS (Within-Cluster Sum of Squares) after each iteration to demonstrate monotone convergence.

Given n 1D data points, k initial centroids, and t iterations, return a list of t+1 WCSS values: the initial WCSS (before any updates) followed by the WCSS after each of the t iterations.

K-Means iteration:

1. Assignment: assign each point to the nearest centroid (by absolute distance in 1D).
2. Update: set each centroid to the mean of its assigned points (if a centroid has no points, keep it unchanged).

WCSS = Σi (xi - centroid[assignment_i])²

Function signature:

def kmeans_wcss_trace(X: np.ndarray, init_centroids: np.ndarray, t: int) -> list:
    # returns list of t+1 WCSS values

Input Format

Line 1: n k t — number of points, clusters, and iterations
Line 2: n space-separated floats — data points
Line 3: k space-separated floats — initial centroid positions

Output Format

t+1 lines: one WCSS value per line (10 significant figures)

Example

Input:

5 2 3
1.0 1.5 5.0 5.5 6.0
0.0 10.0

Output:

64.5
3.9375
0.625
0.625

Derivation

K-Means is guaranteed to converge because:

1. The assignment step minimizes WCSS given fixed centroids.
2. The update step (mean) minimizes WCSS given fixed assignments.
3. There are a finite number of possible assignments.

Therefore WCSS is non-increasing at each step. The algorithm terminates when assignments stop changing (WCSS stops decreasing).

In this example: initial centroids 0.0 and 10.0 are poor choices, but after 2 iterations the algorithm finds the optimal split at ~3.25, achieving WCSS = 0.625.

Notes

• Convergence is to a local, not global, minimum in general.
• The trace shows WCSS non-increasing: 64.5 → 3.9375 → 0.625 → 0.625 (converged).