Editorial for Tô màu xanh đỏ
Submitting an official solution before solving the problem yourself is a bannable offence.
Gợi ý 1
Mỗi thao tác đổi màu đúng một điểm thuộc mỗi lớp vị trí có cùng số dư khi chia cho k. Hãy xét riêng số điểm đỏ trong từng lớp theo modulo 2.
Gợi ý 2
Viết n = qk + r. Có r lớp chứa q + 1 điểm và k - r lớp chứa q điểm. Để có ít điểm xanh nhất, chọn một parity chung cho số điểm đỏ của các lớp.
Nhận xét
Mã hóa màu xanh là 0, màu đỏ là 1. Một thao tác là phép XOR với một cửa sổ gồm k vị trí liên tiếp. Cửa sổ này chứa đúng một vị trí thuộc mỗi lớp modulo k, nên parity số điểm đỏ của tất cả các lớp cùng bị đổi một lần. Do đó, ở trạng thái cuối, các lớp phải có cùng parity số điểm đỏ.
Điều kiện này cũng đủ. Hai cửa sổ liên tiếp khác nhau đúng ở hai đầu, nên XOR của chúng có thể đổi đồng thời hai vị trí cùng lớp modulo k. Kết hợp các phép đổi này với một cửa sổ ban đầu, ta có thể tạo mọi trạng thái mà parity của các lớp bằng nhau.
Tối đa số điểm đỏ
Đặt r = n mod k. Nếu r = 0, mọi lớp có cùng kích thước; có thể chọn trạng thái toàn đỏ, nên đáp án là n.
Nếu r > 0, có r lớp kích thước q+1 và k-r lớp kích thước q, với n = qk+r. Hai nhóm có parity kích thước trái nhau. Với một parity chung đã chọn, mỗi lớp thuộc một trong hai nhóm phải để lại ít nhất một điểm xanh. Ta chọn nhóm nhỏ hơn, cần để xanh min(r, k-r) điểm.
Vậy nếu n mod k = 0, in n; ngược lại in n - min(n mod k, k - (n mod k)).
Độ phức tạp O(1) thời gian và O(1) bộ nhớ.