Xóa chữ số (version khó)

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Khá Ngăn xếp đơn điệu Tham lam

Đề bài

XOACHUSO – Xóa chữ số (Kỳ thi tuyển sinh 10 THPT chuyên TP. Hồ Chí Minh, năm học 2017 – 2018, môn Tin học – đề đã được chỉnh sửa lại cho version khó)

Cho trước một số nguyên dương $N$. Gọi $L$ là số chữ số của $N$.

Yêu cầu: Xóa đi $K$ chữ số của $N$ để nhận được phần còn lại là số lớn nhất. Thứ tự các chữ số vẫn giữ nguyên.

Input (ở version khó này thì $L$ tối đa 1 triệu):

Dòng thứ nhất ghi số nguyên dương $N$ $(L \le 10^6)$.
Dòng thứ hai ghi số nguyên dương $K$ $(K < L)$.

Output: số lớn nhất tìm được sau khi xóa $K$ chữ số của $N$.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.

Ví dụ – input

58673
2

Ví dụ – output

Lưu ý: trên CLUE OJ dữ liệu đọc từ bàn phím và in ra màn hình; đề gốc có yêu cầu file XOACHUSO.INP/XOACHUSO.OUT thì cứ kệ nó. Đề gốc chỉ cho $L \le 255$, còn bản này nâng lên $L \le 10^6$. Ví dụ: xoá 2 chữ số của $58673$ – xoá chữ số $5$ và $6$ còn lại $873$, đó là số lớn nhất.

Lời mở đầu

Bài này là "bản nâng cấp" của bài Xóa chữ số ở chương Tham lam: cùng đề, nhưng $N$ dài tới một triệu chữ số. Với $L \le 255$ thì cách "xoá từng chữ số" $O(K \cdot L)$ chạy vèo vèo, còn bây giờ $K \cdot L$ cỡ $5 \cdot 10^{11}$ – không thể. Đây là lúc ngăn xếp đơn điệu tỏa sáng: chỉ cần duyệt $N$ đúng một lượt. Mình đi lần lượt 3 cách, chạy thật trên bộ test để các bạn thấy rõ khác biệt.

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ưởngtham lam Cách 1xoá K lần Cách 2cửa sổ Cách 3ngăn xếp Tổng kếtkết quả

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

Bộ test có 100 test và đề không chia subtask. Điều đặc biệt: cả 100 test đều có kích thước tối đa:

Test	Số chữ số L của N	K (số chữ số xoá)	Độ dài kết quả	Số chữ số 9 trong kết quả
1–100	1.000.000	500.000	500.000	99.464 … 100.652

Mọi test đều có $L = 10^6$ chữ số và phải xoá đúng một nửa: $K = 500\,000$. Kết quả là một số có $500\,000$ chữ số – đương nhiên phải lưu bằng string.
Các chữ số của $N$ trông như sinh ngẫu nhiên: kết quả bắt đầu bằng một dãy rất dài chữ số $9$ (mỗi đáp án có hơn 99.464 chữ số 9). Chi tiết này sẽ giải thích vì sao cách 2 "ăn may" được full điểm.
Kết quả không bao giờ bắt đầu bằng chữ số 0.

Vì mọi test giống nhau về kích thước, một cách giải hoặc qua hết, hoặc trượt hết. Kết quả chạy thật (giới hạn 1 giây):

Mức	Điều kiện	Test	Cách 1 (xoá K lần)	Cách 2 (chọn max trong cửa sổ)	Cách 3 (ngăn xếp)
Duy nhất	$L = 10^6$, $K = 5 \cdot 10^5$	1–100	0/100	100/100	100/100

Ý tưởngTham lam: chữ số đứng trước càng lớn càng tốt

Sau khi xoá, mọi kết quả đều có cùng $M = L - K$ chữ số. Hai số cùng độ dài thì so sánh từ trái sang phải, nên chữ số đầu quan trọng hơn tất cả các chữ số sau cộng lại.

Nhận xét tham lam

Nếu có hai chữ số kề nhau $N_i < N_{i+1}$ thì xoá $N_i$ sẽ đưa $N_{i+1}$ (lớn hơn) lên đúng vị trí đó → số mới lớn hơn. Vậy mỗi lần xoá, ta xoá chữ số đầu tiên nhỏ hơn chữ số đứng ngay sau nó; nếu dãy đã không tăng thì xoá chữ số cuối cùng.

Cài đặt bằng ngăn xếp: đọc lần lượt từng chữ số $c$; chừng nào còn lượt xoá và chữ số ở đỉnh ngăn xếp nhỏ hơn $c$ thì xoá đỉnh (để $c$ lên trước sẽ tốt hơn); sau đó đẩy $c$ vào. Cuối cùng nếu còn lượt xoá thì cắt bớt ở cuối. Ngăn xếp luôn là một dãy không tăng từ đáy lên đỉnh – đó chính là ngăn xếp đơn điệu.

Em nhập $N$, $K$ rồi bấm Tiếp để xem ngăn xếp hoạt động (ô vàng là chữ số đang xét, ô đỏ là chữ số bị xoá):

N = K =

Ví dụ nhanh:

Cách 1Xoá lần lượt K chữ số – $O(K \cdot L)$

Làm đúng nhận xét tham lam: lặp $K$ lần, mỗi lần đi từ đầu xâu tìm chữ số đầu tiên nhỏ hơn chữ số đứng sau và xoá nó. Đây chính là cách đã full điểm ở bài gốc $L \le 255$.

C++▶ Chạy tay từng dòng codeCách 1: K lần, mỗi lần xoá chữ số đầu tiên nhỏ hơn chữ số đứng sau – O(K·L).

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

Dữ liệu mẫu:

Vòng while dừng ở vị trí i đầu tiên có N[i] < N[i + 1]; nếu đi tới chữ số cuối thì i là chữ số cuối.
N.erase(i, 1) xoá 1 ký tự nhưng phải dời toàn bộ phần phía sau lên một ô – tốn $O(L)$ mỗi lần.

Không gian$O(L)$

Thời gian$O(K \cdot L)$

Với $K = 5 \cdot 10^5$, $L = 10^6$: khoảng $K \cdot L / 2 \approx 2{,}5 \cdot 10^{11}$ phép dời ký tự – hàng trăm giây.

Kết quả chạy thật: Bản C++ đúng 0/100 test, quá thời gian ở test 1–100. Bản Python đúng 0/100 test, quá thời gian ở test 1–100. Cách này không qua nổi test nào vì test nào cũng lớn tối đa.

Cách 2Chọn chữ số lớn nhất trong "cửa sổ"

Một cách nhìn khác: kết quả có $M = L - K$ chữ số. Chữ số đầu tiên của kết quả phải nằm trong $K + 1$ chữ số đầu (nếu chọn xa hơn thì không còn đủ chữ số phía sau). Tham lam: chọn chữ số lớn nhất trong đoạn đó, lấy vị trí sớm nhất nếu có nhiều chữ số bằng nhau (để chừa nhiều lựa chọn cho phía sau). Chữ số thứ $t$ (đếm từ 0) được chọn trong đoạn từ ngay sau vị trí vừa chọn tới vị trí $K + t$.

C++▶ Chạy tay từng dòng codeCách 2: chữ số thứ t chọn max (sớm nhất) trong đoạn [from, K + t], gặp 9 thì dừng.

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

Dữ liệu mẫu:

from là vị trí đầu tiên còn được chọn; đoạn xét cho chữ số thứ t là [from, K + t] – đầu phải của "cửa sổ" tăng dần đều.
So sánh N[j] > N[best] (dấu lớn hơn hẳn) để giữ vị trí sớm nhất của chữ số lớn nhất.
Dòng if(N[best] == '9') break; là "mẹo": chữ số 9 không thể bị vượt, nên gặp 9 là dừng quét ngay.

Không gian$O(L)$

Thời gian$O(M \cdot K)$ trường hợp xấu, rất nhanh với dữ liệu ngẫu nhiên

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

Cẩn thận "ăn may": vì dữ liệu ngẫu nhiên, trung bình chỉ cần quét khoảng 10 chữ số là gặp số 9, nên cách 2 chạy rất nhanh trên bộ test. Nhưng trường hợp xấu vẫn là $O(M \cdot K)$: mình tự sinh một test $L = 10^6$, $K = 5 \cdot 10^5$ chỉ gồm các chữ số $1..8$ ngẫu nhiên thì bản C++ cách 2 chạy 2,5 giây (quá 1 giây), còn cách 3 chỉ mất khoảng 0,02 giây. Thi thật thì đừng trông vào may mắn nhé!

Cách 3Tham lam + ngăn xếp – $O(L)$

Cách 1 mỗi lần xoá lại đi từ đầu xâu và dời cả xâu. Dùng ngăn xếp thì chỉ cần đi một lượt: chữ số nào bị "đè" bởi chữ số lớn hơn đứng sau thì bị xoá ngay.

C++▶ Chạy tay từng dòng codeCách 3: ngăn xếp không tăng, mỗi chữ số vào/ra tối đa 1 lần – O(L).

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

Dữ liệu mẫu:

st là một string dùng như ngăn xếp: back() là đỉnh, pop_back() lấy ra, push_back() đẩy vào – đều $O(1)$.
Vòng while xoá đỉnh khi còn lượt (K > 0) và đỉnh nhỏ hơn c – đúng là "xoá chữ số nhỏ hơn chữ số đứng sau nó".
Duyệt xong mà vẫn còn $K$ lượt xoá thì ngăn xếp là dãy không tăng, bỏ $K$ chữ số cuối bằng resize.
Mỗi chữ số được đẩy vào 1 lần, lấy ra tối đa 1 lần nên tổng thời gian $O(L)$ – bất kể dữ liệu thế nào.

Không gian$O(L)$

Thời gian$O(L)$

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

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. Xoá lần lượt K chữ số	C++	0/100	> 1s	Quá thời gian test 1–100
	Python	0/100	> 1s	Quá thời gian test 1–100
2. Chọn max trong cửa sổ	C++	100/100	0.01s	Full điểm nhờ test ngẫu nhiên (gặp 9 là dừng)
	Python	100/100	0.50s	Full điểm
3. Tham lam + ngăn xếp	C++	100/100	0.02s	Full điểm, $O(L)$ mọi trường hợp
	Python	100/100	0.34s	Full điểm

Ghi chú của mình: cả 100 test đều có $L = 10^6$ nên cách 1 trượt toàn bộ, cách 3 (ngăn xếp) qua hết với thời gian rất nhỏ ở cả C++ lẫn Python. Cách 2 qua được bộ test chỉ nhờ dữ liệu ngẫu nhiên nhiều chữ số 9 – trường hợp xấu nó vẫn quá thời gian. Khi đọc $10^6$ chữ số, nhớ dùng ios::sync_with_stdio(0) (C++) hoặc sys.stdin.read() (Python).

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 😇

Lập Trình Thuật Toán