Phân tích: Snapper Chain

Phần khó nhất là hiểu cách một thiết bị Snapper đơn lẻ hoạt động. Mỗi Snapper có thể ở một trong hai trạng thái -- Bật (On) hoặc Tắt (Off). Ngoài ra, mỗi Snapper có thể có điện hoặc không có điện. Snapper đầu tiên luôn có điện vì nó được cắm trực tiếp vào ổ cắm điện trên tường. Snapper thứ \(i\) có điện khi và chỉ khi Snapper thứ \((i-1)\) có điện và đang ở trạng thái Bật. Việc búng tay sẽ thay đổi trạng thái của mọi Snapper đang có điện (từ Bật sang Tắt, hoặc từ Tắt sang Bật).

Với các quy tắc này, hãy biểu diễn trạng thái Bật/Tắt của các Snapper bằng một chuỗi các bit, với 1 nghĩa là Bật. Nếu chúng ta liệt kê các bit từ phải sang trái, chúng ta có một số nguyên nhị phân. Ban đầu, số nguyên này có giá trị 0. Tương tự, chúng ta có thể viết ra số nguyên nhị phân cho trạng thái có điện/không có điện của mỗi Snapper. Ban đầu, số này là 1 vì chỉ có Snapper tận cùng bên phải (thứ nhất) là có điện.

Việc búng tay tương đương với việc thực hiện phép toán XOR giữa số nguyên Bật/Tắt và số nguyên có điện/không có điện, sau đó gán kết quả lại cho số nguyên Bật/Tắt. Sau đó, chúng ta cập nhật các bit có điện/không có điện theo quy tắc đã nêu trên.

Ví dụ, giả sử số Bật/Tắt hiện tại là 10100011111. Điều này có nghĩa là số có điện/không có điện là 00000111111. Khi chúng ta XOR hai số này, chúng ta nhận được giá trị mới của số Bật/Tắt là: 10100100000.

Điều thú vị là hai bước cập nhật này tương đương với một phép tăng đơn giản (cộng 1) cho số nguyên Bật/Tắt! Việc búng tay cộng thêm 1 vào số nguyên Bật/Tắt, và chúng ta thậm chí không cần quan tâm đến số nguyên có điện/không có điện nữa.

Lời giải cho bài toán vì thế trở nên rất đơn giản. Câu trả lời là "ON" khi và chỉ khi \(N\) bit cuối cùng (bên phải nhất) của \(K\) đều là 1.

Độ phức tạp

• Thời gian: \(O(1)\) cho mỗi bộ thử nghiệm (hoặc \(O(\log K)\) tùy thuộc vào cách kiểm tra bit).
• Không gian: \(O(1)\).

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