Test Set 1

Test Set 1 đủ nhỏ để chúng ta mô phỏng quá trình. Vì mỗi bước lấy đi ít nhất một chiếc bánh khỏi một chồng, cách này cần nhiều nhất \(L + R\) thao tác. Ta còn có thể nhận thấy rằng vì bước thứ \(i\) lấy đi \(i\) chiếc bánh, tổng số bánh bị lấy trong \(i\) bước đầu là \(i \times (i + 1) / 2\). Điều đó có nghĩa số bước thực ra bị chặn trên bởi \(2 \times \sqrt{L + R}\), nên thuật toán mô phỏng cũng có độ phức tạp \(O(\sqrt{L + R})\). Thuật toán này thậm chí còn dùng được với các giới hạn lớn hơn rất nhiều so với giới hạn của test set này!

Test Set 2

Đáng tiếc, \(O(\sqrt{L + R})\) vẫn quá chậm đối với giới hạn \(10^{18}\) của Test Set 2, đặc biệt khi phải xử lý tới 1000 bộ test!

Ta có thể mô phỏng nhiều bước cùng lúc bằng cách nhận thấy quá trình có hai pha riêng biệt. Pha đầu tiên chỉ dùng một chồng: chồng có nhiều bánh hơn lúc ban đầu. Pha thứ hai bắt đầu khi số bánh còn lại trong chồng đó nhỏ hơn hoặc bằng số bánh trong chồng kia. Lưu ý rằng nếu chồng bên trái là chồng được dùng để phục vụ trong pha 1, nó vẫn có thể là chồng đầu tiên được dùng trong pha 2. Cũng có thể không có khách hàng nào được phục vụ trong một trong hai pha.

Tùy vào chênh lệch kích thước ban đầu giữa hai chồng, ta có thể phục vụ rất nhiều khách hàng trong pha 1. Nếu phục vụ đến khách thứ \(i\) chỉ bằng một chồng, ta lấy khỏi chồng đó \(i \times (i + 1) / 2\) chiếc bánh. Vì vậy, ta có thể tính hiệu quả số khách được phục vụ trong pha 1 bằng cách tìm \(i_1\) lớn nhất sao cho \(i_1 \times (i_1 + 1) / 2\) nhỏ hơn hoặc bằng chênh lệch số bánh giữa hai chồng tại thời điểm mở cửa. Ta có thể tính giá trị này bằng cách giải phương trình bậc hai rồi làm tròn cẩn thận, hoặc bằng tìm kiếm nhị phân.

Pha thứ hai là nơi điều kỳ diệu xảy ra. Giả sử khi phục vụ khách hàng thứ \(i\), chồng \(X\) được dùng còn \(Y\) không được dùng, nhưng sau đó ta phục vụ khách hàng thứ \(i + 1\) từ chồng \(Y\). Như vậy, chồng \(X\) mất \(i\) chiếc bánh và chồng \(Y\) mất \(i + 1\) chiếc. Vì \(X\) được chọn thay cho \(Y\) khi phục vụ khách thứ \(i\), lúc đó \(X\) phải có số bánh không ít hơn \(Y\). Vì \(X\) mất ít bánh hơn \(Y\), sau khi ta phục vụ khách thứ \(i\) và \(i + 1\), \(X\) phải có nhiều bánh hơn \(Y\). Điều này có nghĩa là nếu ta từng dùng hai chồng khác nhau theo thứ tự \((X, Y)\), lần kế tiếp ta phải dùng \(X\). Cũng theo lập luận ấy nhưng đổi vai trò hai chồng, lúc này hai chồng được dùng gần nhất theo thứ tự \((Y, X)\), nên lần kế tiếp ta sẽ dùng \(Y\), và cứ tiếp tục như vậy. Do đó, một khi đã dùng cả hai chồng, ta sẽ luôn luân phiên giữa chúng.

Ta có thể dùng nhận xét này để xác định hiệu quả những gì xảy ra trong pha 2. Sau khi cập nhật hai lượng bánh ban đầu bằng cách trừ đi số bánh đã phục vụ trong pha 1, ta biết chồng nào được dùng đầu tiên trong pha 2. Chồng đầu tiên sẽ được dùng để phục vụ các khách hàng thứ \(i_1 + 1, i_1 + 3, i_1 + 5, \ldots\); vì vậy, nếu nó được dùng cho \(c_1\) khách hàng, tổng cộng \((i_1 \times c_1) + c_1^2\) chiếc bánh sẽ được phục vụ từ chồng này. Tại thời điểm đó ta đã biết \(i_1\), nên một lần nữa có thể tính \(c_1\) bằng cách giải phương trình bậc hai hoặc tìm kiếm nhị phân. Chồng còn lại cũng tương tự, vì nó sẽ được dùng để phục vụ các khách hàng thứ \(i_1 + 2, i_1 + 4, i_1 + 6, \ldots\); do đó, nếu nó được dùng cho \(c_2\) khách hàng, tổng cộng \(((i_1 + 1) \times c_2) + c_2^2\) chiếc bánh sẽ được phục vụ từ chồng này. Vậy số khách hàng cuối cùng được phục vụ là \(i_1 + c_1 + c_2\). Tổng số bánh được phục vụ từ mỗi chồng được tính từ các đại lượng của pha 2, đồng thời cộng thêm lượng của pha 1 vào chồng được dùng đầu tiên.

Nếu dùng tìm kiếm nhị phân, mỗi pha cần thời gian \(O(\log(L + R))\). Nếu trực tiếp giải các phương trình bậc hai, mỗi pha thực ra chỉ cần thời gian hằng số. Cả hai cách đều đủ nhanh với giới hạn của bài toán.

Lưu ý rằng việc giải phương trình bậc hai có thể khó hơn bình thường, vì thông thường ta phải tính một số căn bậc hai. Tuy hầu hết ngôn ngữ đều cung cấp cách thực hiện phép tính đó, chúng dùng số thực dấu phẩy động độ chính xác kép, không có đủ độ chính xác cho bài toán này và có thể gây ra lỗi lệch một đơn vị. Ta nên tính căn bậc hai trực tiếp trên số nguyên (chẳng hạn bằng cách tìm kiếm nhị phân đáp án), hoặc dùng hàm dựng sẵn rồi kiểm tra giá trị trả về cùng các giá trị lân cận để tìm kết quả làm tròn chính xác.

Dữ liệu kiểm thử

Tải dữ liệu kiểm thử

Chúng tôi khuyên bạn nên luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2020, Round 2 — Incremental House of Pancakes.