Ếch nhảy
Đề bài
Cho một mảng gồm $n$ số tự nhiên $a[0], a[1], \ldots, a[n-1]$.
Một con ếch đang đứng ở vị trí $0$, $a[i]$ là độ dài lớn nhất con ếch có thể nhảy khi nó đứng ở vị trí $i$.
Hãy giúp con ếch kiểm tra xem nó có thể nhảy đến vị trí $n - 1$ hay không.
Input:
- Dòng đầu chứa số nguyên $T$ là số bộ test $(1 \le T \le 300)$.
- Với mỗi bộ test: dòng đầu chứa số nguyên $n$ là số phần tử trong mảng $(1 \le n \le 26\,000)$; dòng tiếp theo chứa các số nguyên $a[i]$ $(0 \le a[i] \le 10^6)$.
Output: Với mỗi bộ test in ra True nếu con ếch có thể nhảy đến vị trí $n - 1$, ngược lại in ra False.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.
4
5
2 3 1 1 4
2
1 2
3
0 2 3
4
1 0 1 0True
True
False
FalseLời mở đầu
"Độ dài lớn nhất" nghĩa là đứng ở ô $i$ ếch có thể nhảy $1, 2, \ldots$ hoặc $a[i]$ bước – không bắt buộc phải nhảy hết. Ở ví dụ 1, ếch nhảy $0 \to 1$ (1 bước) rồi $1 \to 4$ (3 bước) là tới đích. Ở ví dụ 3 ($0\ 2\ 3$) ếch đứng ở ô 0 với $a[0] = 0$ nên không nhảy được bước nào. Ở ví dụ 4 ($1\ 0\ 1\ 0$) ếch chỉ tới được ô 1 rồi "kẹt" vì $a[1] = 0$.
Đây là bài tham lam rất kinh điển (trên LeetCode tên là Jump Game). Mình đi từ đệ quy thử hết, tới đánh dấu các ô tới được, rồi tới lời giải tham lam chỉ một vòng for.
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 OJLộ 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ì?
Bộ test có 100 test, mỗi test chứa nhiều bộ dữ liệu. Đề không chia subtask, mình chia theo kích thước:
| Test | Số bộ T | n | $a_i$ lớn nhất | Số True / False |
|---|---|---|---|---|
| 1–10 | 1 | 1 … 15 | 14 | 10 / 0 |
| 11–50 | 50 | 500 | 499 | 1.325 / 675 |
| 51–100 | 30 | 26.000 | 25.999 | 990 / 510 |
- Test 1 có $n = 1$: ếch đã đứng sẵn ở ô $n - 1 = 0$ nên đáp án là
Truedù $a[0] = 0$. - Các số $a_i$ thực tế phần lớn rất nhỏ (0 … 7), thỉnh thoảng xen một số lớn – lớn nhất chỉ khoảng 26 000, nhỏ hơn nhiều so với $10^6$ của đề.
- Khoảng 1/3 số bộ có đáp án
False.
Kết quả chạy thật (giới hạn 1 giây):
| Mức | Điều kiện | Test | Cách 1 (đệ quy thử) | Cách 2 (đánh dấu) | Cách 3 (tham lam) |
|---|---|---|---|---|---|
| Mức 1 | $T = 1$, $n \le 15$ | 1–10 | 10/10 | 10/10 | 10/10 |
| Mức 2 | $T = 50$, $n = 500$ | 11–50 | 14/40 | 40/40 | 40/40 |
| Mức 3 | $T = 30$, $n = 26\,000$ | 51–100 | 0/50 | 50/50 | 50/50 |
Ý tưởngChỉ cần nhớ vị trí xa nhất tới được
Nhận xét quan trọng: nếu ếch tới được ô $x$ thì nó tới được mọi ô $0, 1, \ldots, x$ (vì mỗi bước nhảy có thể ngắn tuỳ ý, các ô tới được luôn liền một dải từ 0). Vậy thay vì nhớ từng ô, ta chỉ cần nhớ một số:
xa là vị trí xa nhất ếch tới được. Duyệt $i = 0, 1, 2, \ldots$ chừng nào $i \le$ xa (ô $i$ tới được): từ ô $i$ ếch nhảy xa nhất tới $i + a[i]$, nên cập nhật xa = max(xa, i + a[i]). Nếu có lúc $i >$ xa thì ô $i$ không tới được và mọi ô sau cũng vậy. Cuối cùng đáp án là xa ≥ n − 1.Em nhập mảng $a$ rồi bấm Tiếp để xem vùng tới được (màu xanh) lan dần sang phải:
Cách 1Đệ quy thử mọi bước nhảy
Cách nghĩ đầu tiên: từ ô $i$, thử nhảy $1, 2, \ldots, a[i]$ bước, với mỗi ô mới lại gọi đệ quy hỏi "từ đây có tới được $n - 1$ không?".
- Điều kiện dừng: đang đứng ở $n - 1$ thì trả về
true. - Vòng
forchỉ thử những bước nhảy không vượt quá ô $n - 1$. - Vấn đề: một ô có thể được tới bằng rất nhiều đường, và mỗi lần tới lại bị tính lại từ đầu → số lời gọi tăng theo hàm mũ (đặc biệt với những bộ đáp án
False, máy phải thử hết mọi đường).
Kết quả chạy thật: Bản C++ đúng 24/100 test, quá thời gian ở test 11, 13–15, 17, 19–21, 24–26, 29, 31–35, 37, 39, 41–44, 47, 49–100; test đúng chạy lâu nhất 0.10s. Bản Python đúng 12/100 test, quá thời gian ở test 11–35, 37, 39–100; test đúng chạy lâu nhất 0.11s.
Cách 2Đánh dấu các ô tới được – $O(n \cdot \max a)$
Sửa cách 1 bằng cách mỗi ô chỉ xử lý một lần: mảng toi[i] cho biết ếch có tới được ô $i$ không. Duyệt $i$ từ trái sang phải; nếu tới được ô $i$ thì đánh dấu mọi ô $i+1, \ldots, i + a[i]$.
- Phải gán lại
toi[i] = falsecho mỗi bộ test, nếu không dữ liệu bộ trước sẽ "dính" sang bộ sau. - Vì ta chỉ nhảy sang phải nên khi xét tới ô $i$, mọi ô bên trái đã xử lý xong –
toi[i]lúc đó là chính xác.
Trường hợp xấu nhất ($a_i$ đều lớn) là $O(n^2) \approx 6{,}8 \cdot 10^8$ cho mỗi bộ – nhưng bộ test thực tế có $a_i$ hầu hết rất nhỏ nên cách này vẫn chạy kịp.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.49s. Bản Python đúng 50/100 test, quá thời gian ở test 51–100; test đúng chạy lâu nhất 0.07s.
Cách 3Tham lam – $O(n)$
Từ nhận xét "các ô tới được luôn là một dải $[0, xa]$", mảng toi[] ở cách 2 thực chất chỉ là true từ 0 tới xa. Ta thay cả mảng bằng một biến:
- Điều kiện vòng lặp
i <= xa: chỉ đứng được ở những ô đã tới được; khi $i$ vượtxathì dừng luôn. xacó thể vượt quá $n - 1$ (nhảy quá đích) – không sao, vì nhảy ngắn hơn cũng được.- Với $n = 1$: vòng lặp chạy $i = 0$,
xa = a[0] ≥ 0 = n − 1→True.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.08s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.36s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Đệ quy thử mọi bước nhảy | C++ | 24/100 | > 1s | Quá thời gian test 11, 13–15, 17, 19–21, 24–26, 29, 31–35, 37, 39, 41–44, 47, 49–100 |
| Python | 12/100 | > 1s | Quá thời gian test 11–35, 37, 39–100 | |
| 2. Đánh dấu ô tới được | C++ | 100/100 | 0.49s | Full điểm |
| Python | 50/100 | > 1s | Quá thời gian test 51–100 | |
| 3. Tham lam: vị trí xa nhất | C++ | 100/100 | 0.08s | Full điểm |
| Python | 100/100 | 0.36s | Full điểm |
Nhận xét
Đăng nhận xét