Là quản lý, mỗi phút bạn có hai lựa chọn:

• ăn: không làm gì và để mọi người có đĩa không rỗng ăn một chiếc;
• chuyển: dùng một phút đặc biệt, chọn một đĩa không rỗng và chuyển một số bánh sang một đĩa khác.

Đưa mọi phút đặc biệt lên đầu

Hãy tưởng tượng bạn, người quản lý phục vụ, đã lập một kế hoạch chuyển bánh và gọi nó là chiến lược A. Chọn hai phút liên tiếp \(t,t+1\) sao cho phút \(t\) là ăn, phút \(t+1\) là chuyển. Với tinh thần của một triết gia tự nhiên, bạn tự hỏi: nếu đổi hai quyết định ấy — chuyển ở phút \(t\) và ăn ở phút \(t+1\) — thì sao? Bạn tò mò thực hiện phép đổi và tính lại thời điểm kết thúc. Bất ngờ là bữa sáng không lâu hơn. Bạn tìm thêm nhiều cặp liên tiếp như vậy và tiếp tục đổi; thời gian không bao giờ dài hơn chiến lược A, thậm chí đôi khi còn ngắn hơn!

Quan sát kỹ cho thấy mọi chiếc bánh từng được ăn ở phút \(t\) trước khi đổi vẫn được ăn ở phút \(t+1\) sau khi đổi. Vì vậy, số bánh đã ăn sau phút \(t+1\) không giảm và bữa sáng không thể lâu hơn. Hơn nữa, một số đĩa rỗng ở thời điểm \(t\) có thể trở thành không rỗng tại \(t+1\) sau phép đổi, nên số bánh được ăn có thể tăng thêm một.

“Ồ! Vậy đổi mọi cặp <ăn, chuyển> thành <chuyển, ăn> luôn có lợi: không kéo dài bữa sáng, và có thể làm nó ngắn hơn!”

Hào hứng, bạn lấy bảng trắng và đổi mọi cặp <ăn, chuyển> cho tới khi không còn cặp nào. Bạn đọc to chiến lược mới: “Chuyển, chuyển, chuyển, ăn, ăn, ăn, ăn, ăn”. Tất nhiên! Chiến lược duy nhất không có cặp <ăn, chuyển> là thực hiện mọi lần chuyển ở đầu rồi luôn ăn sau đó. Đổi các cặp sai thứ tự đến khi hết chính là sắp xếp chiến lược bằng bubble sort. Vậy luôn tồn tại nghiệm tối ưu thực hiện tất cả lần chuyển trước, rồi mới để mọi người ăn.

Biết mình có thể được thưởng vì kết thúc bữa sáng sớm, bạn vội trình bày lời giải với sếp. Ông chưa bị thuyết phục: “Tôi hiểu rằng chuyển bánh ngay từ đầu dẫn tới nghiệm tối ưu. Nhưng ở mỗi lần chuyển, anh sẽ chuyển bánh thế nào?” Bạn trả lời rằng luôn có thể chuyển sang đĩa rỗng: có vô hạn đĩa rỗng, không có lý do để bắt người đã có bánh phải ăn nhiều hơn cần thiết, và cũng không thể chờ họ ăn hết chồng hiện tại.

Sếp ngừng đọc thư và hỏi sẽ lấy bánh từ đĩa nào. Bạn đề xuất đĩa có nhiều bánh nhất, vì nó cần được giúp nhất. Ông hào hứng diễn giải: cứ chuyển một số bánh từ những đĩa lớn nhất sang đĩa rỗng rồi dừng sau vài phút; bạn được thưởng lớn và nghỉ thêm.

Bạn vui mừng tập hợp nhân viên nhà bếp để giải thích chiến lược mới — sau khi khoe một chút trên mạng xã hội. Một thực tập sinh giơ tay hỏi: “Khi nào ta ngừng chuyển? Mỗi lần chuyển bao nhiêu chiếc?” Cả bếp im lặng nhìn bạn chờ câu trả lời; bữa sáng bắt đầu sau nửa giờ và bạn cuống cuồng suy nghĩ.

Bạn thú nhận chưa biết và ra lệnh mang tới hai đĩa lần lượt có \(15\) và \(17\) chiếc, cùng vài đĩa rỗng, để mô phỏng. Ta luôn có thể chuyển bánh sang đĩa rỗng; không có lý do đặt thêm bánh vào một đĩa vốn đã phải chờ ăn.

Sau nhiều lần mô phỏng với lượng chuyển và thời điểm dừng khác nhau, thực tập sinh chỉ ra: bạn lấy \(10\) chiếc từ đĩa 1 sang đĩa rỗng 3, rồi lấy \(3\) chiếc từ đĩa 3 sang đĩa rỗng 4. Thay vào đó, sao không chuyển trực tiếp \(7\) chiếc từ đĩa 1 sang đĩa 3, rồi \(3\) chiếc từ đĩa 1 sang đĩa 4? Như vậy, ta luôn chỉ cần chuyển từ những đĩa ban đầu không rỗng. Số lần chuyển không đổi, nên mọi phép chia có thể xem độc lập trên từng đĩa ban đầu.

Bạn kết luận có thể lấy một nửa từ đĩa lớn nhất, rồi lặp lại với đĩa lớn nhất tiếp theo. Thực tập sinh lập tức bác bỏ: với đĩa \(9\) chiếc, chiến lược ấy tốt nhất chỉ tách thành \(4\) và \(5\), mất \(1\) phút chuyển và \(5\) phút ăn, tổng \(6\). Tách thành ba đĩa \(3\) chiếc bằng \(2\) lần chuyển thì chỉ cần \(5\) phút.

Cố định số phút ăn

Thực tập sinh đề nghị: nếu dự kiến mọi người ăn hết sau \(x\) phút kể từ khi ngừng chuyển, mọi chiến lược đạt điều đó tương đương với việc liên tục chuyển nhiều nhất \(x\) chiếc từ từng đĩa ban đầu không rỗng sang đĩa rỗng, cho đến khi đĩa ban đầu còn không quá \(x\) chiếc. Khi đó mỗi phần cuối cùng phải có nhiều nhất \(x\) chiếc. Với một đĩa ban đầu có \(P_i\) chiếc, ta có thể liên tục chuyển nhiều nhất \(x\) chiếc sang đĩa rỗng cho đến khi phần còn lại cũng không quá \(x\).

Số phần tối thiểu cần có là \(\lceil P_i/x\rceil\), nên số lần chuyển tối thiểu cho đĩa đó là

Nếu luôn chuyển đúng \(x\) chiếc, với đĩa có \(P_i\) chiếc ta chỉ cần \(M(P_i)=\lceil P_i/x ceil-1\) lần để phần còn lại không quá \(x\), và không thể dùng ít hơn. Tổng cộng cần \(\sum_iM(P_i)\) lần chuyển; đó là số nhỏ nhất cho \(x\) đã chọn. Mọi người dành cho cô ấy một tràng pháo tay đứng.

Tóm lại, cố định \(x\) là số phút ăn sau khi ngừng chuyển; chọn một đĩa có hơn \(x\) chiếc, chuyển \(x\) chiếc sang đĩa rỗng và lặp đến khi mọi đĩa không quá \(x\). Sau đó để mọi người ăn. Bữa sáng kết thúc chính xác sau

phút. Thử mọi \(x\) từ 1 đến \(M=\max_iP_i\) và lấy giá trị nhỏ nhất. Độ phức tạp là \(O(DM)\), đủ nhanh vì \(M\le1000\).

Bạn định dùng bảng tính, nhưng thực tập sinh nói đã chuẩn bị sẵn. Cô mở máy và gõ vài hàm rất ngắn, dĩ nhiên bằng C++. “Vì sao ư? Vì C++ thật tuyệt!”

// Get the minimum possible breakfast end time, given 
// P[i] is the number of pancakes of diner i initially.
int f(const vector<int>& P) {
  const int max_pancakes = *max_element(P.begin(), P.end());
  int ret = max_pancakes;
  for (int x = 1; x < max_pancakes; ++x) {
    int total_moves = 0;
    for (const int Pi : P) {
      // (Pi - 1) / x is equivalent to M(Pi), 
      // which is ceil(Pi / x) - 1
      total_moves += (Pi - 1) / x;
    }
    ret = min(ret, total_moves + x);
  }
  return ret;
}

“Chà! Chạy đi, chạy đi!”, bạn reo lên. Cô bảo chờ: dù thuật toán trên đã đủ nhanh, cô còn một thuật toán nhanh hơn.

Một thuật toán nhanh hơn

Editorial nêu tối ưu sau. Dãy \(\lceil a/1\rceil,\lceil a/2\rceil,\ldots\) chỉ đổi giá trị nhiều nhất \(2\sqrt a\) lần. Ví dụ với \(a=10\), dãy là

10, 5, 3, 3, 2, 2, 2, 2, 2, 1, 1, ...,

và chỉ đổi 4 lần, ít hơn \(2\sqrt{10}\).

Với mỗi \(P_i\), có thể tiền xử lý các điểm đổi trong \(O(\sqrt M)\) và ghi thành một mảng sai phân thưa \(T_i\). Với \(P_i=10\), một mảng như vậy là

10, -5, -2, 0, -1, 0, 0, 0, 0, -1, 0, ...;

tổng tiền tố của nó khôi phục 10, 5, 3, 3, 2, 2, 2, .... Mỗi \(T_i\) chỉ có \(O(\sqrt M)\) phần tử khác 0. Cộng tất cả các mảng sai phân rồi lấy tổng tiền tố, tại vị trí \(x\) ta có \(\sum_i\lceil P_i/x\rceil\). Trừ \(D\) cho ra \(\sum_i(\lceil P_i/x\rceil-1)\), rồi quét thêm \(O(M)\) vị trí để lấy đáp án. Tổng thời gian là \(O(D\sqrt M+M)\) và bộ nhớ \(O(M)\).

Không thể áp dụng trực tiếp tìm kiếm nhị phân hay tam phân cho hàm thời gian theo \(x\), vì hàm có thể có nhiều cực tiểu. Chẳng hạn, với hai thực khách mỗi người có 9 chiếc, các cặp \((x,T(x))\) là

(1,17), (2,10), (3,7), (4,8), (5,7), (6,8), (7,9), (8,10), (9,9).

Bạn mất kiên nhẫn: “Tôi không cần cách đó! Thuật toán trước đủ nhanh, hãy chạy nó.” Cô thở dài và không giải thích cách cài thuật toán nhanh hơn nữa. Chương trình nhấp nháy; mọi người nín thở. “Đáp án là... \(42\).”

Nguồn

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