Test Set 1

Trong Test Set 1, mọi kỳ lân chỉ có đúng một màu cơ bản trong bờm: đỏ, vàng hoặc xanh dương. Các bờm khác màu không chung màu cơ bản nào, nên hạn chế duy nhất là hai kỳ lân cùng màu bờm không được kề nhau. Tuy nhiên, một màu có thể quá phổ biến đến mức không thể tránh hai con màu đó đứng cạnh nhau. Nếu rải màu phổ biến nhất sao cho giữa mỗi cặp có một kỳ lân khác màu, ta chứa được nhiều nhất \(\lfloor N/2\rfloor\) con của màu phổ biến nhất. Nếu màu nào có nhiều hơn số đó thì không thể.

Nếu không, có thể mở rộng chiến lược “cách một ô” cho mọi trường hợp. Bắt đầu ở một vị trí tùy ý trên vòng và đặt vào các ô thứ nhất, thứ ba, thứ năm, v.v. quanh vòng. Khi quay lại điểm bắt đầu, tiếp tục đặt vào các ô thứ hai, thứ tư, thứ sáu, v.v. Trong quá trình đó, đặt hết màu bờm phổ biến nhất, rồi hết màu phổ biến thứ hai, rồi phần còn lại. Vì tần suất mỗi màu không vượt \(\lfloor N/2\rfloor\), chiến lược không thể đặt hai kỳ lân cùng màu cạnh nhau.

Test Set 2

Test Set 2 phức tạp hơn. Kỳ lân có bờm màu phụ (cam, xanh lá hoặc tím) chỉ có thể có đúng một loại hàng xóm. Kỳ lân cam phải được kẹp giữa hai kỳ lân xanh dương; tương tự, kỳ lân tím chỉ có thể kề kỳ lân vàng, còn kỳ lân xanh lá chỉ có thể kề kỳ lân đỏ.

Cần bao nhiêu kỳ lân màu cơ bản để “bao quanh” mọi kỳ lân bờm màu phụ tương ứng? Nếu màu phụ và màu cơ bản bổ sung của nó là hai màu duy nhất hiện diện, số lượng hai màu phải bằng nhau. Nếu còn màu khác và có \(S\) kỳ lân màu phụ, cần ít nhất \(S+1\) kỳ lân màu cơ bản bổ sung.

Hơn nữa, ta có thể gom mọi kỳ lân cùng một màu phụ vào một chuỗi duy nhất, dĩ nhiên xen giữa bằng màu cơ bản bổ sung. Mọi cách xếp hợp lệ chưa có tính chất này đều có thể biến đổi để có. Chẳng hạn, hai chuỗi R-G-R riêng biệt bị ngăn bởi hai chuỗi hợp lệ khác \(Z,Z'\):

R-G-R-Z-R-G-R-Z'-

có thể sắp lại thành

R-G-R-G-R-Z-R-Z'-

và cách mới vẫn hợp lệ.

Nhận xét cuối cùng: một chuỗi như R-G-R-G-R, xét về những gì được phép đứng ở hai đầu, hoạt động hệt như một kỳ lân R duy nhất. Vì vậy, chiến lược cho Test Set 2 là: trước tiên kiểm tra trường hợp đặc biệt chỉ có một màu phụ và màu cơ bản bổ sung của nó. Nếu không phải trường hợp đó, với mỗi màu phụ, kiểm tra có đủ kỳ lân màu cơ bản để bao quanh chúng thành một chuỗi. Sau đó tạm coi mỗi chuỗi như một lần xuất hiện duy nhất của màu cơ bản ở hai đầu chuỗi. Bài toán rút gọn chỉ còn các màu cơ bản và giải được bằng thuật toán Test Set 1. Cuối cùng, thay chuỗi đầy đủ trở lại vào một lần xuất hiện tùy ý của màu cơ bản thích hợp.

Cụ thể, ngoài các trường hợp duy nhất RG lặp, YV lặp hoặc BO lặp với hai số lượng bằng nhau, phải có \(R>G\), \(Y>V\), \(B>O\). Rút gọn số lượng thành \(R-G\), \(Y-V\), \(B-O\), dựng vòng ba màu, rồi thay một R bằng R(GR)^G, một Y bằng Y(VY)^V, và một B bằng B(OB)^O khi số màu phụ tương ứng khác 0.

Cả lời giải Test Set 1 và Test Set 2 đều chạy trong \(O(N)\), bị chặn bởi việc đọc đầu vào, kiểm tra tần suất màu và in đầu ra. Những lời giải phức tạp hơn, như quy hoạch động, cũng tồn tại.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1B, bài Stable Neigh-bors.