Sắp xếp bò
Đề bài
Nông dân John muốn sắp xếp $n$ con bò (bao gồm cả bò đực và bò cái) của ông ta trên 1 hàng. Ông ta biết rằng những con bò đực rất hung hăng – nếu 2 con bò đực đứng quá gần nhau thì chúng sẽ trở nên hung dữ và bắt đầu húc nhau, vì thế chúng sẽ phá hỏng mất trật tự trên hàng mà ông ta vừa sắp xếp được.
Theo kinh nghiệm lâu năm của mình, John biết được nếu ở giữa hai con bò đực có ít nhất $K$ con bò cái thì sẽ ngăn chặn được việc chúng húc nhau (+_+).
Vì thế, ông ta nhờ các Vcoders giúp đỡ để tính toán xem có bao nhiêu cách sắp xếp đàn bò của ông ta lại sao cho không có "chiến tranh" xảy ra giữa những chú bò (\^_\^). Tất cả những con bò đực và những con bò cái đều giống nhau. Hai dãy $(B_1 \ldots B_n)$ và $(A_1 \ldots A_n)$ được cho là khác nhau nếu tồn tại một vị trí $i$ $(1 \le i \le n)$ sao cho $A_i \ne B_i$.
Dữ liệu nhập: gồm 1 dòng duy nhất chứa 2 số $n$ và $k$ cách nhau 1 dấu cách $(1 \le n \le 10^5;\ 0 \le k \le n)$. Có 1/3 số test với $n \le 15$.
Dữ liệu xuất: gồm duy nhất một số là kết quả theo modulo 2111992.
4 26Giải thích ví dụ ($C$ = bò cái, $B$ = bò đực): với $n = 4$, $k = 2$ có 6 cách xếp là CCCC, BCCC, CBCC, CCBC, CCCB, BCCB. Chú ý: số con bò đực là tuỳ ý (có thể không có con nào), đề chỉ cấm 2 con bò đực đứng gần nhau.
Lời mở đầu
Đây là một bài quy hoạch động đếm rất đẹp: đáp án là một dãy số giống dãy Fibonacci "giãn ra". Mình sẽ đi đúng lộ trình của chương: đầu tiên vét cạn mọi cách xếp để ăn subtask nhỏ và hiểu đề, sau đó tìm công thức quy hoạch động $O(n^2)$, rồi rút gọn thành $O(n)$ để lấy trọn điểm.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | Số test | $n$ | $k$ | Đặc biệt |
|---|---|---|---|---|
| 1–33 | 33 | 4 – 15 | 0 – 15 | 4 test $k = 0$ (đáp án $2^n$), 1 test $k = n$ |
| 34–100 | 67 | 114 – 100.000 | 1 – 58.787 | 25 test có $n > 30.000$, trong đó 5 test $n = 10^5$ |
Đề ghi "có 1/3 số test với $n \le 15$" – kiểm tra trên bộ test thật thì đúng là 33 test đầu có $n \le 15$, 67 test còn lại $n$ lớn tuỳ ý tới $10^5$ (xếp lẫn lộn, không tăng dần). Mình chia thành 2 subtask:
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 QHĐ $O(n^2)$ | Cách 3 QHĐ $O(n)$ |
|---|---|---|---|---|---|
| 1 | $n \le 15$ | 1–33 | qua | qua | qua |
| 2 | $n \le 10^5$ | 34–100 | sai / quá thời gian | qua 42/67 test | qua |
Ý tưởngNhìn vào con bò đứng cuối hàng
Gọi $f[i]$ là số cách xếp hợp lệ cho $i$ con bò đầu tiên. Xét con bò thứ $i$ (con cuối cùng):
- Nó là bò cái (C): bò cái thì không gây chuyện với ai, $i-1$ con phía trước chỉ cần xếp hợp lệ → có $f[i-1]$ cách.
- Nó là bò đực (B): thì $k$ con ngay trước nó bắt buộc là bò cái (nếu có con đực nào trong đó thì 2 con đực quá gần). Phần còn lại là $i-k-1$ con đầu tiên, xếp hợp lệ tuỳ ý → có $f[i-k-1]$ cách.
Vì sao $f[j] = 1$ khi $j < 0$? Khi $i \le k$, nếu con thứ $i$ là bò đực thì tất cả $i - 1$ con trước nó phải là bò cái – chỉ có đúng 1 cách. Còn $f[0] = 1$ ứng với "hàng rỗng" – cũng là 1 cách. Với $k = 0$ công thức thành $f[i] = 2f[i-1]$, tức $2^n$: đúng vì không có ràng buộc gì. Với $k = 1$ ta được đúng dãy Fibonacci!
Em nhập $n$, $k$ rồi bấm Tiếp để xem bảng $f$ được điền dần. Ô vàng là ô đang tính, ô xanh là $f[i-1]$, ô cam là $f[i-k-1]$. Với $i \le 6$ mình liệt kê luôn các cách xếp để em thấy 2 nhóm "kết thúc bằng C" và "kết thúc bằng B":
Cách 1Vét cạn mọi cách xếp bằng bitmask (subtask 1)
Mỗi cách xếp là một dãy $n$ chữ B/C, ứng với một số nhị phân mask từ $0$ đến $2^n - 1$: bit $i$ bằng 1 là bò đực. Với mỗi mask, đi từ trái sang phải, nhớ vị trí last của con bò đực gần nhất; gặp bò đực mới ở vị trí $i$ thì số bò cái ở giữa là $i - last - 1$, phải $\ge k$.
if(mask >> i & 1) cho từng vị trí i (gộp luôn vòng for i).Kết quả chạy thật: đúng 33/100 test – qua trọn subtask 1 (33 test $n \le 15$). Từ test 34 trở đi ($n \ge 114$) thì 1 << n bị tràn số (dịch bit từ 31 vị trí trở lên với kiểu int là hành vi không xác định) nên vòng lặp chạy lung tung: 39 test in kết quả sai, 28 test chạy mãi → quá thời gian. Dù có dùng long long thì $2^{60}$ cách xếp cũng không bao giờ duyệt nổi. Bản Python cũng được 33/100 (không bị tràn số vì số nguyên Python không giới hạn, nhưng quá thời gian toàn bộ 67 test lớn).
Cách 2QHĐ theo vị trí con bò đực cuối cùng – O(n²)
Một cách nghĩ khác (thường là cách các bạn nghĩ ra đầu tiên): gọi $dp[i]$ là số cách xếp mà con bò đực cuối cùng đứng ở vị trí $i$ (sau $i$ toàn bò cái). Khi đó:
- hoặc $i$ là con bò đực duy nhất (đầu tiên): 1 cách;
- hoặc con bò đực ngay trước đứng ở vị trí $j$ với $i - j - 1 \ge k$, tức $j \le i - k - 1$: cộng thêm $dp[j]$.
$$dp[i] = 1 + \sum_{j=1}^{i-k-1} dp[j], \qquad \text{đáp án} = 1 + \sum_{i=1}^{n} dp[i]$$ (số 1 ở đáp án là cách xếp toàn bò cái).
Kết quả chạy thật: đúng 75/100 test. Vòng $j$ chạy khoảng $\frac{(n-k)^2}{2}$ lần. Trên bộ test thật: mọi test có $n - k \le 19.193$ đều qua (chậm nhất 0,63 giây), còn 25 test có $n - k \ge 24.536$ thì phải làm từ $3 \cdot 10^8$ tới $5 \cdot 10^9$ phép tính → quá thời gian.
Nhận xét: tổng $\sum_{j=1}^{i-k-1} dp[j]$ chính là một tổng tiền tố. Nếu lưu tổng tiền tố thì mỗi $dp[i]$ tính trong $O(1)$. Làm tiếp phép biến đổi đó thì ta được đúng công thức $f[i] = f[i-1] + f[i-k-1]$ ở phần ý tưởng: $f[i] = 1 + \sum_{j \le i} dp[j]$ chính là số cách xếp $i$ con đầu (cách toàn C + các cách có con đực cuối ở $\le i$).
Cách 3QHĐ f[i] = f[i−1] + f[i−k−1] – O(n) (full điểm)
- Mảng
fkhai báo toàn cục cỡ $10^5 + 5$; chỉ cần đặtf[0] = 1. - Chỉ số
j = i - k - 1có thể âm (khi $i \le k$) – lúc đó cộng 1 thay vì đọcf[j](đọc chỉ số âm là lỗi truy cập ngoài mảng). - Lấy modulo 2111992 ngay sau mỗi phép cộng: hai số hạng đều $< 2111992$ nên tổng không tràn
int.
Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,01 giây. Bản Python cũng đúng 100/100, chậm nhất 0,06 giây.
Nhận xét
Đăng nhận xét