Đây là một bài có thể giải được bằng nhiều thuật giải khác nhau, tuy nhiên, ở đây mình sẽ chỉ trình bày thuật giải tìm cây khung nhỏ nhất (MST) bằng thuật Kruskal, sử dụng cấu trúc dữ liệu Trie để tối ưu.

Lưu ý: Vì lời giải có sử dụng đến các khái niệm chủ yếu là Kruskal, Trie và xử lý các phép toán bitwise trên số nhị phân, nên mình mong các bạn tìm hiểu trước về các khái niệm này trước khi đọc lời giải bên dưới.

Lời giải

Xét các bit ~i~ từ lớn đến bé, ta xét hai thành phần liên thông (TPLT) là ~V_0~ và ~V_1~ (việc xét như thế có thể dùng cấu trúc dữ liệu Trie). ~V_0~ là TPLT nối giữa các đỉnh có mask của các bit từ ~i~ đến ~log_2(max(a_i)) = 29~ giống nhau và bit ~i~ có giá trị là ~0~ (~V_1~ tương tự nhưng bit ~i~ có giá trị là ~1~). Ta sẽ ưu tiên nối các đỉnh thuộc cùng TPLT ~V_0~ (hoặc ~V_1~) vì chi phí để nối hai đỉnh có giá trị tại bit ~i~ khác nhau luôn có chi phí lớn hơn nối 2 đỉnh có giá trị bit ~i~ giống nhau (~2^i > \displaystyle \sum^{i-1}_{j=0}2^j~). Như vậy, bài toán có thể giải được nhờ vào việc dùng Trie để tối ưu thuật toán Kruskal (giúp tìm MST).

Sử dụng Kruskal, ta xét qua các bit ~i~ từ lớn đến bé, tạo ra hai tập ~V_0~, ~V_1~ rồi lần lượt tính chi phí MST nối các đỉnh có giá trị tại bit ~i~ giống nhau, tức là tính MST của lần lượt các TPLT ~V_0~ và ~V_1~. Sau đó ta sẽ chọn ra hai đỉnh ~i~ thuộc ~V_0~ và đỉnh ~j~ thuộc ~V_1~ sao cho trọng số cạnh của ~i~ và ~j~ là nhỏ nhất để nối hai TPLT ~V_0~ và ~V_1~. Toàn bộ quá trình này chỉ tốn tối đa ~n \cdot log(max(a_i))^2~ thời gian xử lý. Vì vậy độ phức tạp của thuật giải này là ~n \cdot log(max(a_i))^2~