Phân tích: Duck, Duck, Geese

Test Set 1

Với giới hạn nhỏ của \(N\), ta có thể kiểm tra mọi đoạn liên tiếp, miễn là mỗi đoạn được kiểm tra nhanh. Một cách là duyệt mọi chỉ số bắt đầu, rồi với mỗi chỉ số đó duyệt lần lượt mọi kích thước đoạn.

Ta duy trì số lần xuất hiện của mỗi màu và số màu hiện có số lượng không hợp lệ, nghĩa là khác \(0\) nhưng không thuộc đoạn cho phép của màu ấy. Khi kéo dài đoạn, chỉ màu mũ của đứa trẻ mới thêm bị ảnh hưởng. Nếu tính hợp lệ của màu đó thay đổi, cập nhật số màu hợp lệ và không hợp lệ. Nếu số màu hợp lệ bằng \(C\), tăng đáp án, miễn là độ dài đoạn từ \(2\) tới \(N-1\).

Mỗi đoạn được kiểm tra trong \(O(1)\) và có \(O(N^2)\) đoạn cần xét, nên độ phức tạp của Test Set 1 là \(O(N^2)\).

Test Set 2

Với Test Set 2, \(N\) quá lớn để kiểm tra từng đoạn. Ta dùng cây đoạn để xét đồng thời mọi độ dài đoạn đối với từng chỉ số bắt đầu. Có thể loại bỏ tính vòng tròn bằng cách nối mảng với chính nó.

Với chỉ số bắt đầu \(S\) cố định, mỗi màu có hai khoảng chỉ số kết thúc, có thể rỗng, mà tại đó màu ấy hợp lệ: số mũ của màu bằng \(0\) hoặc thuộc khoảng cho phép. Nếu cộng \(1\) trên cây đoạn cho mọi vị trí thuộc các khoảng này, đối với tất cả màu, ta có thể đếm trong đoạn chỉ số kết thúc \([S+1,S+N-2]\) bao nhiêu vị trí có giá trị đúng bằng \(N\). Con số ấy chính là số đoạn liên tiếp hợp lệ bắt đầu tại \(S\).

Việc còn lại là cập nhật cây đoạn khi dịch chỉ số bắt đầu sang phải. Dịch một vị trí chỉ ảnh hưởng các khoảng kết thúc hợp lệ của màu mũ thuộc đứa trẻ vừa bị bỏ khỏi đầu đoạn. Nếu tính trước tại mỗi vị trí lần xuất hiện tiếp theo của chính màu ấy, ta có thể xác định trong \(O(1)\) các khoảng hợp lệ của màu sẽ dịch chuyển ra sao. Bài phân tích chính thức để chi tiết cài đặt này như một bài tập cho người đọc.

Mỗi thao tác cây đoạn tốn \(O(\log N)\). Do đó, đếm số đoạn cho một chỉ số bắt đầu và chuyển sang chỉ số bắt đầu kế tiếp đều tốn \(O(\log N)\), cho tổng độ phức tạp \(O(N\log N)\).

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 3, bài Duck, Duck, Geese.