Tóm tắt đề bài

Cho \(N\) điểm trên mặt phẳng tọa độ \((x_i, y_i)\) và \(M\) loại nguyên tử phóng xạ (đánh số từ \(1\) đến \(M\)). Cần gán mỗi điểm một loại nguyên tử sao cho khoảng cách Euclid nhỏ nhất giữa hai điểm cùng loại là lớn nhất có thể.

Phân tích

• Ràng buộc: \(N \leq 1000\), \(M \leq 5\).
• Đây là một bài toán tối ưu hóa giá trị nhỏ nhất (Max-Min). Thông thường, dạng bài này có thể giải quyết bằng phương pháp Chặt nhị phân kết quả.
• Với một giá trị khoảng cách \(D\) cố định, ta cần kiểm tra xem có tồn tại cách tô \(M\) màu cho \(N\) điểm sao cho không có hai điểm nào cùng màu mà có khoảng cách nhỏ hơn \(D\) hay không.
• Nếu ta coi mỗi điểm là một đỉnh của đồ thị, và nối cạnh giữa hai đỉnh \(i, j\) nếu \(dist(i, j) < D\), thì bài toán trở thành: Kiểm tra xem đồ thị có thể tô màu bằng \(M\) màu hay không (bài toán \(M\)-colorability).

Hướng giải quyết

1. Chặt nhị phân

Ta chặt nhị phân trên giá trị độ ổn định \(D\). Với mỗi giá trị mid, ta xây dựng đồ thị và kiểm tra tính hợp lệ. Vì tọa độ nguyên và số lượng điểm nhỏ, ta có thể thực hiện khoảng 60-100 bước chặt nhị phân (hoặc cố định 300 bước như trong code để đạt độ chính xác cao).

2. Kiểm tra tính hợp lệ (Hàm check(mid))

Bài toán tô màu đồ thị tổng quát với \(M \geq 3\) là một bài toán NP-khó. Tuy nhiên, với \(M\) rất nhỏ (\(M \leq 5\)) và \(N = 1000\), ta có thể sử dụng các thuật toán heuristic mạnh hoặc quay lui có nhánh cận.

Trong code tham khảo, một thuật toán tham lam kết hợp với DSATUR (Degree of Saturation) và ngẫu nhiên hóa được sử dụng:

• Xây dựng đồ thị: Nối cạnh giữa các cặp điểm \((i, j)\) nếu \(dist(i, j) < mid\).
• Độ ưu tiên: Sử dụng một giá trị ngẫu nhiên prio[i] để phá vỡ các thế bế tắc khi chọn đỉnh tiếp theo.
• Mặt nạ bit (Bitmask): Duy trì mask[i] đại diện cho các màu còn lại có thể tô cho đỉnh \(i\). Ban đầu tất cả \(M\) màu đều khả dụng.
• Hàng đợi ưu tiên (Priority Queue): Luôn chọn đỉnh có ít lựa chọn màu nhất (số bit 1 trong mask ít nhất) để tô trước. Đây chính là tư tưởng của thuật toán DSATUR.
• Tô màu:
  • Chọn màu đầu tiên còn trống trong mask[u] để tô cho đỉnh \(u\).
  • Cập nhật mask của các đỉnh kề \(v\) bằng cách loại bỏ màu vừa chọn.
  • Nếu có một đỉnh không còn màu nào để tô (mask == 0), giá trị mid hiện tại không khả thi.

3. Tại sao thuật toán này hoạt động?

Mặc dù tô màu đồ thị là NP-khó, nhưng đồ thị được tạo ra từ khoảng cách hình học thường có những cấu trúc đặc biệt. Việc kết hợp DSATUR và ngẫu nhiên hóa giúp thuật toán tìm ra lời giải rất nhanh trong hầu hết các trường hợp thực tế của bài toán này.

Độ phức tạp

• Chặt nhị phân: \(O(\log(\frac{max\_dist}{\epsilon}))\).
• Mỗi bước kiểm tra:
  • Xây dựng đồ thị: \(O(N^2)\).
  • Tô màu (DSATUR): \(O((N+E) \log N)\) với \(E\) là số cạnh, tối đa \(O(N^2)\).
• Tổng độ phức tạp: \(O(T \cdot N^2 \log N)\) với \(T\) là số bước chặt nhị phân. Với \(N=1000\), độ phức tạp này hoàn toàn khả thi trong thời gian cho phép.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MASK(i)          (1LL << (i))
#define getbit(x, y)     (((x) >> (y)) & 1LL)
#define turnoff(x, y)    ((x) & ~MASK(y))
#define bitcnt(x)        __builtin_popcountll(x)

const int maxn = 1005;

int n, m, trace[maxn];
pair<int, int> a[maxn];

inline double square(int x){ return (double)x * x; }
inline double dist(int i, int j){ 
    return sqrt(square(a[i].first - a[j].first) + square(a[i].second - a[j].second)); 
}

int prio[maxn], ok[maxn], mask[maxn];
vector<int> g[maxn];
mt19937_64 Rd(1337); // Seed ngẫu nhiên cố định hoặc dùng time

bool check(double mid){
    for(int i = 1; i <= n; ++i) {
        prio[i] = Rd() % (int)1e9;
        ok[i] = 0;
        mask[i] = MASK(m) - 1; // Tất cả m màu đều sẵn sàng
        g[i].clear();
    }

    // Xây dựng đồ thị: cạnh nối giữa các điểm có khoảng cách < mid
    for(int i = 1; i <= n; ++i) {
        for(int j = i + 1; j <= n; ++j) {
            if (dist(i, j) < mid) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    // Priority Queue chọn đỉnh có ít lựa chọn màu nhất (DSATUR heuristic)
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
    for(int i = 1; i <= n; ++i) pq.push({bitcnt(mask[i]), prio[i], i});

    while (!pq.empty()){
        array<int, 3> Top = pq.top(); pq.pop();
        int u = Top[2];

        if (ok[u]) continue;
        if (mask[u] == 0) return false; // Không còn màu nào để tô

        // Chọn màu có chỉ số nhỏ nhất còn lại
        int bit = __builtin_ctz(mask[u]);
        ok[u] = bit + 1;

        for (int v : g[u]) {
            if (!ok[v]){
                mask[v] = turnoff(mask[v], bit);
                pq.push({bitcnt(mask[v]), prio[v], v});
            }
        }
    }

    for(int i = 1; i <= n; ++i) if (!ok[i]) return false;

    // Lưu lại kết quả tốt nhất
    for(int i = 1; i <= n; ++i) trace[i] = ok[i];
    return true;
}

signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    if (!(cin >> n >> m)) return 0;
    for(int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;

    double l = 0, r = 3e6; // Khoảng cách tối đa có thể đạt được
    for (int step = 0; step < 100; ++step){
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    // In ra phương án tô màu ứng với kết quả tối ưu tìm được
    for(int i = 1; i <= n; ++i) cout << trace[i] << (i == n ? "" : " ");
    cout << endl;

    return 0;
}