Phân tích

Test Set 1

Ẩn số duy nhất là danh tính ba kim. Chỉ có \(3!\) phép gán ba góc, nên thử hết. Sau khi gán, đọc thời gian; dễ nhất là dùng kim giờ, vì đề cho biết nó đi một tick mỗi nanosecond, nên góc tick của kim giờ chính là số nanosecond từ nửa đêm.

Vẫn phải kiểm tra hai kim còn lại nhất quán. Có thể đọc phút, giây từ định nghĩa rồi so với thời gian của kim giờ; hoặc làm ngược: từ thời điểm dựng lại ba góc. Cách ngược được mô tả sau vì cần cho các Test Set khác.

Lời giải Test Set 2 và 3 trước tiên giải bài toán ngược: từ thời điểm, tìm một bộ ba góc chuẩn. Biết tốc độ mỗi kim, đổi thời gian thành số tick từ nửa đêm rồi lấy modulo số tick một vòng, \(12\cdot10^{10}\cdot360\).

Sau khi có ba góc, xét phép quay. Có thể quy ước bộ chuẩn luôn chứa ít nhất một góc \(0\), nhưng có tối đa ba cách — chọn lần lượt mỗi kim làm góc \(0\). Sắp từng bộ rồi lấy bộ nhỏ nhất theo thứ tự từ điển là đủ.

Test Set 2

Chỉ có \(12\cdot60\cdot60\) thời điểm nguyên giây. Với mỗi thời điểm \(t\), dựng biểu diễn chuẩn \(a\) và lưu từ điển ngược từ biểu diễn sang thời điểm; nếu nhiều thời điểm cùng biểu diễn thì lưu cái nào cũng được. Chuẩn hóa đầu vào rồi tra từ điển.

Test Set 3

Không thể duyệt mọi nanosecond. Thay vào đó giới hạn các thời điểm có thể ứng với một bộ góc và kiểm tra từng ứng viên bằng phép đổi ngược.

Thử đủ \(3!\) phép gán: \(a_h,a_m,a_s\) cho kim giờ, phút, giây. Viết thời gian thật là \(h\) giờ trọn cộng \(n\) nanosecond:

với \(0\le h\le11\). Góc kim phút là \(12n\), góc kim giờ là \(h\cdot3600\cdot10^9+n\). Hiệu của chúng là \(h\cdot3600\cdot10^9-11n\) và phải bằng \(a_h-a_m\), vì hiệu góc bất biến qua phép quay.

Thử \(h=0..11\); lúc đó mọi biến trừ \(n\) đã biết và giải được \(n\). Nếu \(n\) nguyên, ta có một thời điểm ứng viên. Cuối cùng, với nhiều nhất \(3!\cdot12\) ứng viên, dựng ngược ba góc và kiểm tra khớp hoàn toàn như lời giải trước.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1B, bài Broken Clock.