Phân tích

Test Set 1

Test Set 1 chứa 12 dữ liệu vào khả dĩ theo giới hạn. Ta có thể tìm kiếm theo chiều rộng (BFS) trên đồ thị trạng thái, trong đó trạng thái là cách xếp bài hiện tại. Tuy nhiên, trường hợp có 14 lá tạo đồ thị khổng lồ, khiến lời giải quá chậm — có lẽ ngay cả chạy cục bộ để tính trước đáp án rồi ghi cứng cũng quá chậm!

Một nhận xét hữu ích: vì điều kiện thành công hoàn toàn không liên quan đến chất, ta có thể bỏ chất và chỉ xét hạng. Số trạng thái giảm mạnh từ \((R \times S)!\) xuống \((R \times S)!/((S!)^R)\). Nhờ đó BFS đủ nhanh cho test set này. Nhận xét này cũng hữu ích cho test set tiếp theo...

Test Set 2

Trường hợp xấu nhất (\(R=40,S=40\)) có khoảng \(1{,}8 \times 10^{2517}\) thứ tự khác nhau, nên vét cạn không thể hoạt động.

Nhận xét quan trọng đầu tiên: một thao tác chỉ có thể giảm nhiều nhất 2 cặp lá kề nhau khác hạng. Ban đầu có \((R \times S)-1\) cặp như vậy; cuối cùng có \(R-1\). Vì thế cần ít nhất \(\lceil(R \times S-R)/2\rceil\) thao tác.

Do \(\lceil(R \times S-R)/2\rceil\) là cận dưới, nếu tìm được phương pháp luôn dùng không quá số bước đó thì nó luôn cho đáp án hợp lệ.

Ta sẽ sắp xếp bằng đúng số thao tác ấy. Duy trì bất biến: với hạng \(X,Y\) của hai lá liên tiếp bất kỳ, hoặc \(Y=X\), hoặc \(Y=(X+1)\bmod R\). Thứ tự ban đầu hiển nhiên thỏa mãn.

Lặp thao tác sau chừng nào số cặp kề cùng hạng còn nhỏ hơn \(R-1\) và thao tác không lấy lá dưới cùng: lấy A là đoạn dài nhất từ trên cùng chứa đúng 2 hạng. Theo bất biến, đó là một hay nhiều lá hạng \(X\), rồi một hay nhiều lá hạng \((X+1)\bmod R\). Từ lá đầu tiên sau A, lấy B là đoạn dài nhất không chứa hạng \(X\), cộng mọi lá hạng \(X\) liên tiếp ngay sau đoạn ấy. Phải có ít nhất một lá \(X\) như vậy; nếu không, theo bất biến số cặp kề khác hạng đã là \(R-1\).

Thao tác này giảm đúng 2 cặp kề khác hạng nếu không lấy lá dưới cùng. Lá cuối B có hạng \(X\); lá đầu phần còn lại, theo bất biến, có hạng \((X+1)\bmod R\). Hai cặp mới là hai lá \(X\) (cuối B, đầu A) và hai lá \((X+1)\bmod R\) (cuối A, đầu phần còn lại). Theo định nghĩa A và B, hai cặp bị phá đều khác hạng. Vì vậy số cặp khác hạng giảm 2.

Giả sử thao tác sẽ lấy lá dưới cùng. Khi ấy, trước thao tác, mọi lá hạng \(X\) nằm trong hai đoạn liên tiếp ở đầu và cuối. Vì đây là lần đầu lá dưới cùng bị lấy, \(X=R\). Bất biến buộc mỗi hạng khác nằm trong một đoạn liên tiếp duy nhất. Thứ tự này có đúng \(R\) cặp kề khác hạng. Thay cho thao tác trên, chọn A là đoạn dài nhất gồm các lá hạng \(R\) bắt đầu từ đỉnh, và B là toàn bộ phần còn lại. Sau thao tác còn \(R-1\) cặp khác hạng (lập luận tương tự, bỏ các cặp bị phá/tạo liên quan đến phần còn lại vì không còn phần ấy), và lá cuối vẫn có hạng \(R\).

Sau \(\lfloor(R \times S-R)/2\rfloor\) lần thực hiện thao tác lặp, số cặp kề khác hạng giảm còn \(R-1\) nếu \(R \times S-R\) chẵn, hoặc \(R\) nếu lẻ. Trước mỗi thao tác ấy, số này vẫn lớn hơn \(R\), nên chưa từng lấy lá dưới cùng. Với trường hợp chẵn, số cặp khác hạng đã tối thiểu và chưa lấy lá dưới cùng, nên ta ở đúng thứ tự đích. Với trường hợp lẻ, thao tác cuối rơi vào trường hợp lấy lá dưới cùng; như đã chứng minh, nó cũng đưa bộ bài về thứ tự đích.

Dữ liệu kiểm thử

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

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