[VOJ] V8MAYORS + GARDEN25
ll931110
https://vn.spoj.pl/problems/V8MAYORS/
Đề bài được mô tả lại như sau:
Trên mặt phẳng cho N điểm. Hãy tô màu mỗi điểm bằng 1 trong 2 màu: đen
và trắng sao cho:
- Trên mỗi hàng và mỗi cột, số điểm đen chênh lệch so với số điểm
trắng không quá 1
- Tổng số điểm trắng chênh lệch với tổng số điểm đen không quá 1
Bây giờ ta giải quyết điều kiện thứ nhất trước. Các bước như sau:
- Sắp xếp các điểm theo chiều tăng dần của hoành độ, nếu có một số
điểm cùng hoành độ thì sắp tăng chúng theo tung độ
- Trên mỗi hàng (một tập hợp các điểm cùng hoành độ, ta xét các điểm
theo chiều tăng dần của tung độ và nối:
+ Điểm thứ nhất với điểm thứ hai
+ Điểm thứ ba với điểm thứ tư
+ …
(Nếu trên hàng đó có 1 số lẻ điểm, thì điểm cuối cùng không được nối)
- Sắp xếp lại các điểm theo chiều tăng dần của tung độ và nối tương tự
như với phần hoành độ
- Bây giờ tô màu các điểm. Khi tô, ta đảm bảo: 2 điểm được nối với
nhau thì được tô màu khác nhau.
Ta chứng minh cách tô này thỏa mãn điều kiện thứ nhất của bài toán:
- Do trong mỗi bước, mỗi điểm chỉ được nối với nhiều nhất 1 điểm khác,
nên mỗi điểm có bậc tối đa là 2. Nghĩa là, tập N điểm được chia thành
các ”dây” và “vòng”
- Hơn nữa, với mỗi “vòng”, cách tô luôn đảm bảo trên mỗi hàng và mỗi
cột, số điểm đen bằng số điểm trắng. Suy ra, có thể “gỡ” các vòng mà
không ảnh hưởng đến bài toán
- Trên mỗi hàng và mỗi cột, chỉ có tối đa 1 điểm không thuộc “vòng”.
Như thế, ở mỗi hàng và mỗi cột, số điểm đen chênh lệch với số điểm
trắng không quá 1. Thuật toán được chứng minh
Phần còn lại là giải quyết điều kiện 2. Ta chỉ cần sửa lại một chút về
cách tô để đạt được như sau:
- Giả sử ta đã tô được u điểm đen và v điểm trắng
- Xét đến thành phần liên thông K, nếu K có số điểm là chẵn, ta có thể
tô tùy ý. Nếu K có số điểm là lẻ, ta ưu tiên cho màu nào đang được tô
ít hơn. Nghĩa là, nếu u <= v, ta tô K sao cho số điểm đen nhiều hơn số
điểm trắng, ngược lại tô K sao cho số điểm trắng nhiều hơn số điểm
đen.
Chứng minh:
- Khởi tạo ban đầu: u = v = 0
- Tại mỗi lần tô 1 thành phần liên thông, do ta phải tô 2 điểm được
nối với nhau bằng 2 màu khác nhau, nên số điểm đen được tô thêm chênh
lệch với số điểm trắng được tô thêm là không quá 1
- Mặt khác, ta lại ưu tiên cho loại điểm nào đang được tô ít hơn. Nên
trong mọi lúc, ta luôn đảm bảo được BĐT |u – v| <= 1. Quá trình tô là
hữu hạn, nên thuật toán đã được chứng minh
Độ phức tạp của bài toán là O(n log n) (cho việc sắp xếp các điểm)
P/S: Nguồn gốc của bài này là IMO 1986, Problem 6