Duyệt điểm

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Trung bình Quy hoạch động QHĐ trên lưới

Đề bài

Xét lưới ô vuông tạo thành từ $n$ đoạn thẳng nằm ngang (các đoạn này được đánh số từ 1 đến $n$ từ trên xuống dưới) và $n$ đoạn thẳng dọc (cũng được đánh số từ 1 đến $n$) theo chiều từ trái qua phải. Giao của đoạn thẳng nằm ngang thứ $i$ và đoạn thẳng dọc thứ $j$ có toạ độ $(i, j)$.

Cho một tập $S$ gồm $n$ đoạn thẳng, đoạn thứ $i$ nằm trên đoạn thẳng thứ $i$ của lưới xác định bởi hai điểm $(i, l_i)$ và $(i, r_i)$.

Yêu cầu: Xác định độ dài của đường đi ngắn nhất dọc theo các cạnh của lưới từ điểm $(1, 1)$ đến điểm $(n, n)$ và thoả mãn các điều kiện:

• Chỉ đi sang phải, sang trái hoặc xuống dưới;
• Đi qua tất cả các điểm của các đoạn thẳng thuộc tập $S$ đã cho.

Ví dụ, với lưới $6 \times 6$ và 6 đoạn thẳng như sau (đoạn tô đỏ):

Khi đó, nếu xuất phát từ điểm $(1, 1)$ đến $(6, 6)$ cần đi một quãng đường ngắn nhất bằng 24.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 200\,000)$.
• Dòng thứ $i$ trong $n$ dòng sau chứa hai số nguyên dương $l_i, r_i$ $(1 \le l_i \le r_i \le n,\ i = 1 \dots n)$.

Kết quả: một số nguyên duy nhất là độ dài của đường đi ngắn nhất tìm được.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

6
2 6
3 4
1 3
1 2
3 6
4 5

Ví dụ – output

24

Lời mở đầu

Bài này nhìn thì giống bài đường đi trên lưới, nhưng điểm mấu chốt là: trên mỗi hàng, sau khi đi hết đoạn thẳng thì ta chỉ có thể đứng ở một trong hai đầu mút. Chỉ cần 2 trạng thái cho mỗi hàng là đủ để quy hoạch động – một ví dụ rất đẹp về việc chọn trạng thái thật gọn. Ngoài ra bài còn giấu một cái bẫy kinh điển: tràn số.

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ưởng2 đầu mútCách 1vét cạn 2ⁿCách 2QHĐ O(n)Tổng kếtkết quả

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

Đề không chia subtask, nhưng bộ 100 test chia rất rõ thành 2 nhóm:

Nhóm	Test	$n$	Đáp án	Số test đáp án vượt kiểu int	Độ dài đoạn trung bình
Nhóm 1	1–30	5 – 10	10 – 74	0	1,8
Nhóm 2	31–100	200.000 – 200.000	20.964.905.692 – 21.077.639.492	70	81137,6

• Nhóm 1 (test 1–30): $n \le 10$ – lưới nhỏ xíu, vét cạn thoải mái. Có 74 đoạn chỉ là 1 điểm ($l_i = r_i$) và 3 đoạn phủ kín cả hàng.
• Nhóm 2 (test 31–100): cả 70 test đều có $n = 200\,000$ với các đoạn ngẫu nhiên khá dài, và đáp án của cả 70 test đều vượt quá $2^{31} - 1 \approx 2{,}1 \cdot 10^9$ (khoảng $2{,}1 \cdot 10^{10}$). Dùng kiểu int là mất trắng 70 điểm.

Kết quả chạy thật của các cách bên dưới theo từng nhóm:

Nhóm	Test	Cách 1 vét cạn $2^n$	Cách 2 QHĐ, kiểu int	Cách 2 QHĐ, long long
Nhóm 1	1–30	30/30	30/30	30/30
Nhóm 2	31–100	0/70	0/70	70/70

Ý tưởngMỗi hàng chỉ có 2 cách kết thúc

Vì chỉ được đi trái, phải, xuống (không được đi lên), nên đường đi xử lý lần lượt từng hàng 1, 2, …, $n$; mỗi hàng đi xuống đúng 1 lần, tổng cộng $n - 1$ bước dọc. Ở hàng $i$, ta vào ở một cột $c$ nào đó và phải đi qua mọi điểm từ $l_i$ tới $r_i$. Muốn đi qua cả hai đầu mút thì:

• hoặc tới $r_i$ trước rồi quay về, kết thúc ở $l_i$: tốn $|c - r_i| + (r_i - l_i)$;
• hoặc tới $l_i$ trước rồi đi sang, kết thúc ở $r_i$: tốn $|c - l_i| + (r_i - l_i)$.

Kết thúc ở chỗ khác (giữa đoạn hoặc ngoài đoạn) không bao giờ có lợi: đứng ở đầu mút rồi đi tiếp sang hàng dưới cũng ngắn bằng hoặc hơn. Vậy sau mỗi hàng ta chỉ cần nhớ 2 con số:

Trạng thái QHĐ

$fL[i]$ = quãng đường ngắn nhất khi đã đi hết hàng $1..i$ và đang đứng ở $(i, l_i)$;
$fR[i]$ = như trên nhưng đang đứng ở $(i, r_i)$.
Với $p_L = l_{i-1}$, $p_R = r_{i-1}$ là hai chỗ đứng của hàng trước (hàng "0" coi như đứng ở cột 1, $fL = fR = 0$): $$fL[i] = \min\big(fL[i-1] + |p_L - r_i|,\ fR[i-1] + |p_R - r_i|\big) + (r_i - l_i)$$ $$fR[i] = \min\big(fL[i-1] + |p_L - l_i|,\ fR[i-1] + |p_R - l_i|\big) + (r_i - l_i)$$ Đáp án $= \min\big(fL[n] + (n - l_n),\ fR[n] + (n - r_n)\big)$ $+ (n - 1)$.

Em bấm Tiếp để xem hai trạng thái được tính qua từng hàng: đường xanh dương là đường tốt nhất kết thúc ở đầu trái, đường cam là đường tốt nhất kết thúc ở đầu phải; cuối cùng đường xanh lá là đáp án. Em có thể sửa dữ liệu (mỗi cặp là $l_i\ r_i$):

n = Các cặp l r =

Ví dụ nhanh:

Cách 1Vét cạn mọi cách kết thúc – nhóm 1

Mỗi hàng có 2 lựa chọn (kết thúc ở trái hay phải), nên có $2^n$ đường đi "hợp lý". Hàm đệ quy thu(i, c, len) thử cả hai lựa chọn ở hàng $i$ rồi đi xuống hàng $i + 1$, tới hàng cuối thì cộng thêm đoạn đi tới cột $n$.

C++▶ Chạy tay từng dòng codeCách 1: thử cả 2 cách kết thúc ở từng hàng (2^n đường đi) – ví dụ đề n = 6 quá dài nên dùng ví dụ n ≤ 4.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. dau là đầu mút đi tới trước, ket là đầu mút kết thúc: đi từ $c$ tới dau, rồi đi hết đoạn ($r_i - l_i$) để tới ket.
2. Mỗi lần xuống hàng cộng thêm 1 (len2 + 1).
3. Đã dùng long long cho độ dài ngay từ đầu.

Không gian$O(n)$

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

Kết quả chạy thật: Bản C++ đúng 30/100 test, sai ở test 31–100; test đúng chạy lâu nhất 0.01s. Bản Python đúng 30/100 test, sai ở test 31–100; test đúng chạy lâu nhất 0.03s. Ở 70 test lớn chương trình bị lỗi chạy (RE) ngay lập tức: đệ quy sâu 200 000 tầng làm tràn ngăn xếp (bản Python vượt giới hạn đệ quy) – mà kể cả không tràn thì $2^{200000}$ lời gọi cũng không bao giờ xong.

Cách 2QHĐ hai trạng thái – full điểm

Để ý cách 1 gọi thu(i, c, …) với rất nhiều giá trị len khác nhau nhưng chỉ có 2 giá trị $c$ ($l_{i-1}$ hoặc $r_{i-1}$). Với cùng chỗ đứng thì chỉ cần giữ len nhỏ nhất – đó chính là $fL$, $fR$ ở phần ý tưởng. Mỗi hàng tính 2 số từ 2 số của hàng trước, nên chỉ cần vài biến, không cần mảng:

C++▶ Chạy tay từng dòng codeCách 2: QHĐ 2 trạng thái fL, fR qua từng hàng, O(n).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phải tính nL, nR vào biến tạm rồi mới gán cho fL, fR: nếu gán fL trước thì lúc tính nR lại dùng nhầm fL của hàng mới.
2. Hàng "0" là điểm xuất phát $(1, 1)$: pL = pR = 1, fL = fR = 0.
3. $n - 1$ bước đi xuống được cộng một lần ở cuối.

Bẫy tràn số

Mỗi hàng có thể đi tới gần $2n$ bước, nên đáp án có thể tới cỡ $2n^2 = 8 \cdot 10^{10}$ – vượt xa giới hạn $2^{31} - 1$ của int. Mình đã thử thay hết long long trong code trên bằng int: bản int đúng 30/100 test, sai ở test 31–100; test đúng chạy lâu nhất 0.00s – sai đúng 70 test lớn vì đáp án thật cỡ $2{,}1 \cdot 10^{10}$.

Không gian$O(1)$ (không cần mảng)

Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.03s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.35s. Full điểm.

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. Vét cạn $2^n$	C++	30/100	0.01s	Chỉ qua nhóm 1 ($n \le 10$)
	Python	30/100	0.03s	Chỉ qua nhóm 1
2. QHĐ (biến int)	C++	30/100	0.00s	Đúng thuật toán nhưng tràn số ở cả 70 test lớn
2. QHĐ (long long)	C++	100/100	0.03s	Full điểm
	Python	100/100	0.35s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình với giới hạn 1 giây; "> 1s" là bị quá thời gian. Bài học của bài: (1) khi một bước của bài toán chỉ có ít "chỗ đứng" quan trọng (ở đây là 2 đầu mút) thì dùng chúng làm trạng thái QHĐ; (2) luôn ước lượng đáp án lớn nhất để chọn kiểu dữ liệu – bộ test này có tới 70% số test "bẫy" int.

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 😇