Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Data Science] Một vòng K-medoids (PAM, L1)

    K-medoids giống K-means nhưng tâm cụm là một điểm dữ liệu thực (medoid) và dùng khoảng cách Manhattan (L1L_1L1​).

    Cho nnn điểm trong Rd\mathbb{R}^dRd và danh sách kkk chỉ số medoid khởi tạo. Thực hiện một vòng:

    1. Gán: mỗi điểm thuộc về medoid gần nhất theo L1L_1L1​. Nếu hòa, chọn medoid có chỉ số cụm nhỏ hơn.
    2. Cập nhật: trong mỗi cụm, medoid mới là thành viên có tổng khoảng cách L1L_1L1​ tới mọi thành viên cùng cụm nhỏ nhất. Nếu hòa, chọn chỉ số điểm nhỏ hơn.

    In ra kkk chỉ số medoid mới (theo thứ tự cụm), cách nhau bởi dấu cách.

    • Định dạng đầu vào:

      Dòng 1: nnn, ddd, kkk. Tiếp theo nnn dòng, mỗi dòng ddd số (điểm). Dòng cuối: kkk chỉ số medoid khởi tạo (0-based).

    • Ràng buộc đầu vào:

      1≤k≤n≤5001 \le k \le n \le 5001≤k≤n≤500, 1≤d≤101 \le d \le 101≤d≤10. Bảo đảm mỗi cụm khởi tạo có ít nhất 1 điểm.

    • Định dạng đầu ra:

      Một dòng gồm kkk số nguyên (chỉ số medoid mới), cách nhau bởi dấu cách.

    Ví dụ:

    Đầu vào:

    4 1 2
0
1
10
11
0 2

    Đầu ra:

    0 2

    Giải thích:

    Medoid khởi tạo điểm 0(=0) và 2(=10). Gán: {0,1}->cụm0, {10,11}->cụm1. Trong {0,1} tổng L1 của 0=1, của 1=1, hòa chọn chỉ số nhỏ ->0. Trong {10,11} ->2.

    Đang tải editor...