Hai nhận xét nền tảng

Các phép lật giao hoán: cùng một tập vị trí bắt đầu sẽ cho cùng kết quả, bất kể thứ tự. Ngoài ra không cần lật hai lần tại cùng vị trí; nhờ tính giao hoán, có thể đưa hai lần ấy cạnh nhau và chúng triệt tiêu. Vì vậy mỗi vị trí bắt đầu hoặc được dùng đúng một lần, hoặc không dùng.

Bộ nhỏ

Có \(N-K+1\) phép lật khả dĩ, nên chỉ có \(2^{N-K+1}\le2^9=512\) tập con. Thử từng tập, mô phỏng kết quả, bỏ những tập còn bánh - và lấy số phép ít nhất. Một cách khác là BFS trên các trạng thái chuỗi bánh, với mỗi phép lật là một cạnh. Cả hai đều dư sức cho \(N\le10\).

Bộ lớn: quyết định bắt buộc từ trái sang phải

Xét bánh trái nhất \(p_1\). Chỉ phép lật trái nhất \(f_1\) tác động tới nó, nên muốn kết thúc toàn + thì phải dùng \(f_1\) khi và chỉ khi \(p_1\) hiện là -. Sau khi quyết định \(f_1\), trong các phép chưa quyết định chỉ còn \(f_2\) có thể tác động bánh \(p_2\); trạng thái hiện tại của \(p_2\) lại buộc quyết định \(f_2\). Tiếp tục như vậy, \(N-K+1\) bánh đầu xác định duy nhất toàn bộ tập phép lật.

Sau khi xử lý các vị trí bắt đầu hợp lệ, kiểm tra \(K-1\) bánh cuối. Nếu tất cả là +, số phép đã dùng là đáp án; nếu còn -, không một tập phép nào có thể thành công nên in IMPOSSIBLE. Lập luận “mỗi quyết định là bắt buộc” đồng thời chứng minh tính đúng và tối ưu; thực ra nhiều nhất chỉ một tập con trong vét cạn của bộ nhỏ có thể hợp lệ.

Mô phỏng lật trực tiếp \(K\) bánh mỗi lần tốn \(O(NK)\), hay \(O(N^2)\) ở cận xấu nhất, vẫn đủ giới hạn chính thức. Có thể đạt \(O(N)\) bằng hiệu XOR: giữ parity số phép đang phủ vị trí hiện tại và mảng đánh dấu thời điểm hiệu lực kết thúc. Trước khi xét \(i\), loại phép bắt đầu ở \(i-K\); nếu ký hiệu bánh sau khi XOR là -, bắt đầu phép mới tại \(i\) và đánh dấu nó hết hiệu lực ở \(i+K\). Nếu \(i+K>N\) thì vô nghiệm. Bộ nhớ \(O(N)\), hoặc \(O(K)\) với hàng đợi vòng.

Cụ thể, giả sử \(N=10\), \(K=5\) và bánh đầu tiên là -. Khi bắt đầu ở bánh thứ nhất, ta buộc phải lật nó, nên biết rằng cả năm bánh đầu đều sẽ bị lật. Tăng số phép lật đang “nợ” bánh hiện tại lên \(1\), đồng thời ghi một mốc để giảm số này đi \(1\) khi tới bánh thứ sáu, nơi phép lật đầu tiên hết hiệu lực. Tiếp tục từ trái sang phải và áp dụng các mốc trước khi xử lý từng bánh. Nếu bánh gốc là - khi số phép đang phủ nó chẵn, hoặc bánh gốc là + khi số ấy lẻ, thì trạng thái hiệu dụng của nó là -: ta tăng số phép đang phủ lên \(1\) và ghi thêm một mốc giảm tại vị trí cách đó \(K\). Các mốc này chỉ cần một mảng độ dài \(N\) được kiểm tra trước mỗi bánh; đây chính là cách nhìn bằng mảng hiệu/parity của thuật toán trên.

Tối ưu này không cần thiết để vượt qua Test Set lớn, nhưng là một mẹo hữu ích trong các bài thi lập trình — và ít nhất một kỹ sư Code Jam đã dùng chính nó trong công việc kỹ thuật phần mềm hằng ngày.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Qualification Round, bài Oversized Pancake Flipper; kho Google Coding Competitions (Apache-2.0).