Di chuyển toa tàu

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Dễ Ngăn xếp Mô phỏng

Đề bài

Hình dưới là cơ cấu của một đường tàu tại một ga xe lửa:

Ban đầu ở đường ray A có chứa các toa tàu được đánh số thứ tự từ $1$ đến $n$ theo thứ tự từ trái qua phải, người ta muốn chuyển các toa đó sang ray C để có được một thứ tự mới là một hoán vị của $(1, 2, \ldots, n)$ theo quy tắc: chỉ được đưa các toa tàu chạy theo đường ray theo hướng mũi tên, có thể dùng đường ray B để lưu tạm các toa tàu trong quá trình di chuyển.

Cho biết hoán vị cần có, hãy tìm phương án di chuyển ít nhất các toa tàu trên đường ray.

Input:

• Dòng 1: một số nguyên dương $n$ $(n \le 10^5)$.
• Dòng 2: $n$ số nguyên là hoán vị của các số từ $1$ đến $n$.

Output:

• Nếu không có phương án thì đưa ra thông báo là NO.
• Nếu có phương án thì: dòng 1 đưa ra thông báo YES; các dòng tiếp theo đưa ra các bước di chuyển ít nhất các toa tàu (mỗi bước là A->C, A->B hoặc B->C).

Ví dụ – input

4
1 4 3 2

Ví dụ – output

YES
A->C
A->B
A->B
A->C
B->C
B->C

Giải thích ví dụ: toa 1 đi thẳng A → C. Cần toa 4 nhưng toa 2, 3 đang chắn phía trước nên đưa 2 rồi 3 vào ray B, sau đó 4 đi thẳng A → C. Lúc này toa 3 nằm trên đỉnh ray B nên B → C, rồi tới toa 2: B → C. Tổng cộng 6 bước.

Lời mở đầu

Ray B là một đường cụt: toa vào sau cùng nằm sát lối ra nên phải ra trước tiên. Đó chính xác là hành vi của một ngăn xếp (stack) – "vào sau, ra trước". Bài này là ví dụ đẹp để thấy ngăn xếp không chỉ là khái niệm trong máy tính mà còn có thật ngoài đời. Mình sẽ đi từ cách mô phỏng "thật thà" tới cách gọn gàng $O(n)$, kèm kết quả chạy thật trên bộ test của CLUE.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngray B = ngăn xếpCách 1mảng, O(n²)Cách 2stack, O(n)

Bộ testBộ test chính thức có gì?

Test	n	Số test YES	Số test NO	Số bước (test YES)	Số toa phải vào ray B
1 – 30	4 … 15	21	9	6 … 24	2 … 9
31 – 100	100.000	46	24	149.831 … 150.150	49.831 … 50.150

• Đề không ghi subtask, nhưng bộ test chia rất rõ 2 mức: test 1–30 có $n \le 15$ (chấm tay cũng được), test 31–100 đều có $n = 10^5$.
• Có khá nhiều test NO (33 / 100 test), nên phải kiểm tra kỹ trường hợp không có phương án.
• Với test YES, số bước khoảng $1.5n$: khoảng một nửa số toa phải "ghé" ray B. Output dài tới hơn 150 nghìn dòng nên cần in nhanh (dùng "\n" thay cho endl, hoặc gom vào một xâu rồi in một lần).
• Máy chấm so sánh từng dòng với đáp án, nên phương án in ra phải đúng thứ tự như đáp án – ở dưới mình sẽ giải thích vì sao phương án ít bước nhất là duy nhất.

Kết quả chạy thật của từng cách theo 2 mức test:

Mức	Điều kiện	Các test	Cách 1 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python
1	$n \le 15$	1 – 30	30/30	30/30	30/30	30/30
2	$n = 10^5$	31 – 100	70/70	43/70	70/70	70/70

Ý tưởngLần lượt "gọi" từng toa theo thứ tự cần có

Ta cần các toa đến ray C theo đúng thứ tự $p_1, p_2, \ldots, p_n$. Xét lần lượt từng toa $x = p_i$ cần đưa sang C:

1. Nếu $x$ đang ở đỉnh ray B: đưa thẳng B->C.
2. Nếu $x$ vẫn còn ở ray A: các toa đứng trước $x$ trên ray A đang chắn đường, buộc phải dồn hết vào ray B (A->B từng toa), rồi $x$ đi thẳng A->C.
3. Còn lại: $x$ đang ở ray B nhưng bị toa khác đè lên trên. Muốn lấy $x$ thì phải lấy toa phía trên ra trước, mà toa đó chỉ đi được sang C – sai thứ tự. Vậy in NO.

Vì sao số bước là ít nhất (và duy nhất)?

Mỗi toa phải sang C đúng một lần. Toa nào đi thẳng A->C tốn 1 bước, toa nào ghé B tốn 2 bước. Một toa buộc phải ghé B khi có toa cần sang C trước nó lại đang đứng sau nó trên ray A; cách làm trên chỉ đưa vào B đúng những toa bị buộc như vậy, và cũng không có lựa chọn nào khác về thứ tự các bước. Nên phương án tìm được là ít bước nhất và là duy nhất.

Một nhận xét giúp cài đặt gọn: toa trên ray A luôn là một dãy liên tiếp $a, a + 1, \ldots, n$ (lấy ra từ đầu theo thứ tự tăng dần). Vậy "x còn ở ray A" chỉ đơn giản là $x \ge a$.

Em nhập hoán vị rồi bấm Tiếp để xem các toa di chuyển (ray B vẽ dạng ngăn xếp, toa trên cùng là toa ra được):

Hoán vị cần có:

Ví dụ nhanh:

Cách 1Mô phỏng "thật thà" bằng mảng

Lưu ray A trong một vector mà phần tử đầu là toa gần ngã ba, ray B trong một vector với cuối mảng là đỉnh. Để biết $x$ còn trên ray A, dùng find tìm tuần tự; để lấy toa đầu ray A, dùng A.erase(A.begin()).

C++▶ Chạy tay từng dòng codeCách 1: mô phỏng ray A, B bằng vector, dùng find và erase – O(n²).

Dữ liệu vào (stdin) – sửa thoải mái4 1 4 3 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điều kiện !B.empty() && B.back() == x: phải kiểm tra B khác rỗng trước rồi mới xem đỉnh.
2. Các bước được lưu vào moves trước, vì nếu giữa chừng phát hiện NO thì không được in gì khác.
3. find và erase(A.begin()) đều tốn $O(n)$ mỗi lần (xoá phần tử đầu phải dời cả mảng), nên cả thuật toán là $O(n^2)$.

Không gian$O(n)$

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0.535s; bản Python đúng 73/100 test (quá 1 giây ở các test 36, 38, 40, 43, 46, 48, 52, 54, 56–59, 61, 65–66, 68, 70, 72–73, 75, 82–83, 85, 94, 96, 99–100), lâu nhất 1.000s. Bản C++ qua hết là nhờ thao tác dời mảng của erase được máy làm cực nhanh (chép cả khối bộ nhớ), nhưng vẫn mất 0,54 giây ở test lâu nhất – gấp hàng chục lần cách 2. Bản Python thì không may mắn như vậy.

Cách 2Ngăn xếp + một biến đếm – O(n)

Dùng nhận xét ray A luôn là $a, a + 1, \ldots, n$: không cần lưu ray A, chỉ cần biến a là toa đầu ray A. Ray B dùng stack<int>.

C++▶ Chạy tay từng dòng codeCách 2: ray B là stack, ray A chỉ cần biến a (toa đầu ray A) – O(n).

Dữ liệu vào (stdin) – sửa thoải mái4 1 4 3 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. x >= a thay cho find: $x$ còn trên ray A khi và chỉ khi nó chưa bị lấy ra, tức $x \ge a$.
2. Vòng while(a < x) đẩy các toa $a, a + 1, \ldots, x - 1$ vào B. Mỗi toa được đẩy vào B nhiều nhất một lần và lấy ra nhiều nhất một lần, nên tổng cộng mọi vòng lặp chỉ $O(n)$.
3. Kết quả gom vào xâu out rồi in một lần ở cuối, vừa nhanh vừa đảm bảo trường hợp NO không in thừa gì.

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0.019s; bản Python đúng 100/100 test, lâu nhất 0.100s.

Ghi chú thêm cho bạn nào thích toán: hoán vị in ra NO khi và chỉ khi có ba vị trí $i < j < k$ với $p_j < p_k < p_i$ (mẫu "lớn – nhỏ – vừa"). Ví dụ 3 1 2: lấy 3 thì 1, 2 phải vào B theo thứ tự 1 rồi 2, khi đó 2 nằm trên 1 nên không lấy 1 ra trước được.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Mô phỏng bằng mảng, xoá đầu	C++	100/100	0.535s	Full điểm
	Python	73/100	1.000s	Quá 1 giây ở 27 test lớn
2. Ngăn xếp + con trỏ	C++	100/100	0.019s	Full điểm
	Python	100/100	0.100s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình, giới hạn 1 giây/test. Cách 2 chạy test lớn nhất trong khoảng 0,02 giây với C++ và 0,10 giây với Python. Mẹo nhận ra ngăn xếp: thấy cái gì "vào sau ra trước" (đường cụt, chồng đĩa, nút Undo…) là nghĩ ngay tới stack nhé.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇