Test Set nhỏ

Small có nhiều nhất 10 chiếc bánh, nên tổng số trạng thái có thể đạt được bằng mọi dãy phép lật là \(2^{10}=1024\). Có thể tìm kiếm theo chiều rộng trên không gian trạng thái này. Với \(N\) chiếc, cách cài đặt đó chạy trong \(O(N2^N)\).

Test Set lớn

Large cần cách hiệu quả hơn. Hãy hình dung chồng bánh gồm vài chiếc +, rồi vài chiếc -, rồi lại +, v.v. Ta nên tránh lật tại ranh giới giữa hai chiếc cùng hướng và cố gộp thành các nhóm cùng hướng lớn hơn. Định nghĩa độ cao theo nhóm của một tiền tố (có thể là toàn chồng) là số nhóm liên tiếp có cùng hướng. Trạng thái đích có độ cao theo nhóm bằng 1. Các phép lật ảnh hưởng như sau:

• Lật một đoạn có độ cao theo nhóm chẵn thì độ cao theo nhóm của cả chồng không đổi.
• Lật một đoạn có độ cao theo nhóm lẻ thì độ cao của cả chồng tăng 1 nếu điểm cắt nằm giữa hai bánh cùng hướng, giảm 1 nếu nằm giữa hai bánh ngược hướng, và không đổi nếu lật toàn bộ chồng.

Các trường hợp trên bao quát mọi phép lật, nên một phép lật chỉ có thể giảm độ cao theo nhóm nhiều nhất 1. Trạng thái đích có độ cao 1, vì vậy chồng có độ cao \(H\) cần ít nhất \(H-1\) phép lật. Tuy nhiên \(H-1\) chưa luôn đủ: chồng toàn mặt trống có \(H=1\) nhưng vẫn phải lật toàn bộ. Nếu chiếc dưới cùng là mặt trống, phải lật toàn bộ ít nhất một lần vì chỉ thao tác đó mới lật được nó; thao tác này không đổi độ cao theo nhóm. Do đó cận dưới chặt hơn là \(H-1\) nếu chiếc cuối là +, và \(H\) nếu chiếc cuối là -.

Với \(H>1\), ta luôn có thể lật nhóm cùng hướng trên cùng để giảm độ cao theo nhóm đúng 1. Vì vậy cận dưới chặt ấy cũng đạt được: liên tục lật nhóm trên cùng, mỗi lần giảm độ cao 1, đến khi chỉ còn một nhóm; nếu cần thì lật toàn bộ thêm một lần.

Bài chỉ hỏi số phép lật, không hỏi các đoạn cần lật. Kết quả là độ cao theo nhóm trừ 1 nếu bánh cuối là +, ngược lại là đúng độ cao theo nhóm. Độ cao bằng 1 cộng số lần chuỗi đổi từ + sang - hoặc ngược lại:

def minimumFlips(pancakes):
  groupedHeight = 1 + pancakes.count('-+') + pancakes.count('+-')
  if pancakes.endswith('-'):
    return groupedHeight
  else:
    return groupedHeight - 1

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Qualification Round - Revenge of the Pancakes, kho Google Coding Competitions (Apache-2.0).