Phân nhóm 1

Tính nhất quán trong bài này có một tính chất không đúng với phần lớn các hệ logic thông thường: một tập lời khai nhất quán khi và chỉ khi mọi tập con gồm \(2\) lời khai đều nhất quán. Chiều thuận là hiển nhiên, còn chiều đảo thì không, nên ta sẽ chứng minh.

Giả sử có tập lời khai \(S\) sao cho hai lời khai bất kỳ đều nhất quán. Với mỗi con chim \(b\), xét mọi lời khai nói rằng \(b\) ở một điểm cụ thể trong không-thời gian. Sắp xếp các điểm ấy theo thời gian rồi nội suy tuyến tính giữa các điểm liên tiếp; ta thu được một quỹ đạo của \(b\) nhất quán với mọi lời khai trong \(S\). Vì mọi cặp lời khai đều nhất quán — đặc biệt là những cặp liên tiếp — đoạn nội suy tuyến tính không vượt quá vận tốc tối đa. Bằng cách này, ta có thể tạo quỹ đạo cho từng con chim được nhắc tới, và tất cả quỹ đạo đều nhất quán với mọi lời khai. Theo định nghĩa, \(S\) nhất quán.

Các cuộc họp cũng khẳng định “con chim này đã ở điểm không-thời gian này” đối với những con đã biết là vịt. Do đó, lập luận tương tự cho thấy một tập lời khai cùng các con vịt đã biết nhất quán với những cuộc họp khi và chỉ khi chúng nhất quán theo từng cặp. Vì theo ràng buộc, các cuộc họp đã nhất quán từng cặp, ta chỉ còn phải kiểm tra cặp gồm hai lời khai và cặp gồm một lời khai với một cuộc họp.

Với giới hạn nhỏ của Phân nhóm 1, giờ có thể thử mọi thứ. Ta biết có ít nhất một con vịt, nên lần lượt thử từng con chim làm “con vịt đầu tiên”. Với mỗi lựa chọn, duyệt các lời khai và kiểm tra chúng với các cuộc họp (nếu lời khai liên quan tới một con vịt đã biết) cũng như với những lời khai trước đó. Nếu một lời khai mâu thuẫn một cuộc họp, người đưa ra lời khai buộc phải là vịt. Nếu một lời khai mâu thuẫn một lời khai trước đó, người đưa ra lời khai trước ấy buộc phải là vịt (vì vịt không được mâu thuẫn với ngỗng). Mỗi lần tìm được vịt mới, ta bắt đầu kiểm tra lại mọi thứ. Khi duyệt hết mọi lời khai mà không thấy mâu thuẫn nào với tập vịt hiện tại, ta hoàn tất và có một tập vịt ứng viên. Lưu ý rằng mọi con chim đều là vịt luôn là một đáp án hợp lệ. Cuối cùng, giữ tập vịt nhỏ nhất và in kích thước của nó.

Lời giải này có \(N\) vòng lặp ngoài để thử mọi “con vịt đầu tiên”. Kiểm tra tính nhất quán của một cặp lời khai hoặc một lời khai với một cuộc họp mất thời gian hằng số: chỉ cần kiểm tra những con chim xuất hiện trong cả hai có thể đi từ một điểm không-thời gian tới điểm kia hay không, bằng một phép tính đơn giản. Do đó, kiểm tra mọi lời khai với mọi lời khai khác và mọi cuộc họp tốn \(O(S(S+M))\). Trong mọi lượt duyệt lời khai trừ lượt cuối, ta tìm được ít nhất một con vịt mới, nên có nhiều nhất \(N-1\) lượt (vì đã khởi đầu với một con vịt xác định). Tổng thời gian là

Vì mọi biến đều không quá \(50\), thuật toán đủ nhanh.

Phân nhóm 2

Trong Phân nhóm 2, ta phải tăng tốc đáng kể. Trước hết, dùng một phiên bản tinh hơn của nhận xét về tính nhất quán. Như trong chứng minh, không cần buộc mọi cặp lời khai, hoặc mọi cặp lời khai-cuộc họp, phải nhất quán; chỉ cần những cặp “liên tiếp”.

Nói hình thức, gọi hai lời khai \(s_1,s_2\) liên tiếp trong \(S\) nếu chúng lần lượt nói về thời điểm \(t_1,t_2\) và cùng nói về con chim \(b\), đồng thời không có lời khai nào khác trong \(S\) nói về \(b\) tại thời điểm \(t_3\) thỏa \(t_1<t_3<t_2\). Tương tự, gọi một lời khai \(s\in S\) tại thời điểm \(t_1\) và một cuộc họp \(m\) tại thời điểm \(t_2\) là liên tiếp nếu không có cuộc họp nào khác tại thời điểm \(t_3\) thỏa \(t_1<t_3<t_2\). Quan hệ “liên tiếp” không phải một thứ tự toàn phần vì có thể có nhiều lời khai cùng thời điểm. Tuy nhiên, biến nó thành thứ tự toàn phần bằng cách phá hòa tùy ý vẫn giữ định lý đúng.

Khi đó, một tập \(S\) gồm các lời khai và/hoặc cuộc họp của các con vịt đã biết nhất quán khi và chỉ khi mọi cặp liên tiếp đều nhất quán. Chứng minh giống hệt chứng minh phía trên.

Nhờ nhận xét này, nếu duy trì được một danh sách đã sắp xếp gồm các cuộc họp và lời khai do ngỗng đưa ra về mỗi con chim, ta có thể kiểm tra mỗi lời khai \(s\) trong thời gian logarit bằng cách chỉ xét các hàng xóm liên tiếp của nó (nhiều nhất \(2\) cuộc họp và \(2\) lời khai cho mỗi con chim trong \(s\)). Điều đó đã giảm phép kiểm tra trong cùng của lời giải Phân nhóm 1 từ \(O(S(S+M))\) xuống thời gian logarit — một cải thiện đáng kể.

Để duy trì các danh sách ấy, với mỗi con chim ta dùng một cấu trúc cây hỗ trợ chèn và tìm kiếm trong thời gian logarit, chẳng hạn set trong C++ hoặc TreeSet trong Java. Mỗi khi xử lý một lời khai, chỉ cần thêm thông tin mới vào cấu trúc của các con chim thích hợp.

Ta còn có thể cải thiện bằng cách không khởi động lại mỗi lần tìm được vịt. Nếu cấu trúc cũng hỗ trợ xóa trong thời gian logarit (như các ví dụ trên), khi phát hiện một con vịt, ta xóa mọi thông tin đến từ những lời khai của nó. Để làm vậy, với mỗi con chim, lưu danh sách mọi mẩu thông tin mà nó đã đóng góp. Mỗi mẩu bị xóa nhiều nhất một lần, nên tổng số phép xóa không vượt tổng số phép chèn và không làm thay đổi độ phức tạp.

Tới đây, độ phức tạp đã giảm xuống \(O(N(S+M)F)\), trong đó \(F\) chỉ gồm các thừa số logarit. Thừa số \(N\) đến từ vòng lặp ngoài chọn “con vịt đầu tiên”. Để loại bỏ nó, trước hết nhận xét rằng nếu bắt đầu với tập vịt rỗng mà vẫn tìm ra một số con vịt, thì những con đó luôn bắt buộc là vịt và cũng sẽ được tìm ra khi bắt đầu từ bất kỳ tập nào. Vì vậy, trong trường hợp ấy, chính tập vịt đó là đáp án. Nếu không có vịt bắt buộc, ta cần làm cách khác, nhưng lúc này biết rằng không có mâu thuẫn giữa các lời khai.

Giờ chỉ còn phải kiểm tra tính nhất quán giữa lời khai và cuộc họp. Một lời khai không nhất quán với một cuộc họp tương đương với việc con chim \(b_1\) nói rằng con chim \(b_2\) không phải vịt. Do đó, nếu \(b_2\) là vịt thì \(b_1\) cũng phải là vịt. Ta biểu diễn tình huống bằng đồ thị có hướng, trong đó các cạnh biểu diễn những quan hệ kéo theo này. Nếu có đường đi từ \(b_1\) tới \(b_2\), thì có một quan hệ kéo theo (có thể không đến trực tiếp từ một lời khai duy nhất) rằng nếu \(b_1\) là vịt thì \(b_2\) cũng là vịt. Bởi vậy, nếu một con chim là vịt thì mọi con chim khác trong cùng thành phần liên thông mạnh (SCC) cũng là vịt.

Ta muốn chọn một SCC nhỏ nhất có thể. Hơn nữa, cần chọn một thành phần cuối, tức một thành phần không trỏ tới thành phần khác. Một thành phần không cuối sẽ kéo theo những thành phần khác cũng gồm vịt, và cuối cùng buộc phải chứa ít nhất một thành phần cuối. Tóm lại, trong trường hợp cuối cùng này, đáp án là kích thước SCC cuối nhỏ nhất; có thể tìm nó trong thời gian tuyến tính.

Nguồn

Google Code Jam 2022, Chung kết thế giới, bài Goose, Goose, Ducks?.

Phân tích chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.