Subtask 1: \(P = 1, M*N \le 20\)

Ta có thể duyệt nhị phân mọi sự thay đổi của bảng và kiểm tra.
Độ phức tạp: \(O(2^{MN}MN)\)

Subtask 2: \(P \le 10, K = 1\)

Với \(P \le 10\), ta có thể sinh ra toàn bộ bảng \(M \times P\) dòng, \(N\) cột. (10000 dòng, 10 cột).
Bài toán được đưa về tìm đường ngắn nhất hoặc quy hoạch động.

Subtask 3:

Tương tự subtask 2, nhưng \(K = 2\).
Ta có thể QHĐ F[i, u1, u2] là chi phí nhỏ nhất đến dòng \(i\), bóng thứ nhất ở vị trí \(u1\), bóng thứ 2 ở vị trí \(u2\). Số trạng thái của F là 1 triệu.
Từ trạng thái F[i, u1, u2] đến trạng thái tiếp theo, nếu không xử lý khéo, số lần xét sẽ là \(2^10\) (xét mọi trạng thái của dòng tiếp theo). Nếu xử lý khéo léo hơn, số trạng thái phải xét tiếp theo là \(2^6\) (chỉ quan tâm các ô \(u1-1, u1, u1+1, u2-1, u2, u2+1\))

Subtask 4:

Ta vẫn có \(P \le 10\) (có thể sinh toàn bộ bảng) và không còn giới hạn \(K\).
Khi đó ta thay đổi \(F\) thành F[i, state] với state là vị trí hiện tại của \(K\) quả bóng khi tới hàng \(i\).
Trên lý thuyết, kích thước mảng F là lớn, nhưng có thể nhận xét để giảm số lượng state phải xét:

• Không xét các state mà không thể tới đích (ví dụ có 1 quả bóng là -1 mà đích là có giá trị > 0)
• Nhận xét: một quả bóng xuất phát ở cột chẵn sẽ đi theo thứ tự -> lẽ -> chẵn
• Hai quả bóng xuất phát ở \(u < v\) thì tại mọi thời điểm \(u'\) và \(v'\) (nếu không bằng -1) thì \(u' < v'\)

Subtask 5:

Tương tự subtask 4 nhưng ta có thêm nhận xét là vì bảng được nhân lên \(P\) lần từ bảng \(M * N\) ban đầu, đoạn cuối cùng sẽ có chung pattern.
Ta vẫn tiến hành tính F[i, state] như subtask 4, nhưng sau một số lần tính toán
sẽ có F[u], F[u + period], F[u + 2*period] thoả mãn:

• Số state bằng nhau và mỗi state, thì 3 giá trị tạo thành cấp số cộng.

Câu hỏi: các bạn nghĩ rằng sau tối đa bao lâu thì cấp số cộng sẽ xuất hiện?