Phân tích: Painting a Fence

Đây là bài toán dễ nhất trong kỳ thi này. Một lời giải duyệt trâu (brute force) trực tiếp là đủ để vượt qua các giới hạn.

Thuật toán

Bước 1: Chọn một tập hợp \(C\) gồm (tối đa) ba màu sẽ được sử dụng. Vì có tối đa \(N\) màu khác nhau, nên có \(O(N^3)\) cách chọn như vậy.

Bước 2: Từ các lời đề nghị ban đầu, lọc ra những lời đề nghị có màu nằm trong tập hợp \(C\). Chúng ta cần xác định xem các lời đề nghị còn lại này có thể bao phủ toàn bộ hàng rào hay không, và nếu có, số lượng lời đề nghị tối thiểu cần thiết là bao nhiêu.

Bước 2 là một bài toán kinh điển có thể giải bằng thuật toán tham lam kết hợp kỹ thuật quét (scanline):

1. Sắp xếp các lời đề nghị (các khoảng) theo điểm đầu bên trái của chúng.
2. Quét từ trái sang phải, xem xét từng lời đề nghị một.
3. Tại bất kỳ thời điểm nào, nếu chúng ta đã bao phủ hàng rào từ đoạn \(1\) đến \(k\), chúng ta luôn chọn lời đề nghị tiếp theo sao cho nó bắt đầu trước hoặc tại vị trí \(k+1\) và kết thúc càng xa về phía bên phải càng tốt.

Độ phức tạp

Nếu chúng ta sắp xếp tất cả các lời đề nghị theo điểm đầu bên trái ngay từ đầu, thì Bước 2 sẽ mất thời gian \(O(N)\). Tổng thể thuật toán sẽ chạy trong thời gian \(O(N^4)\).

Dựa trên phân tích chính thức của Google Code Jam.