Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Việt Nam Sơn
ZaloĐăng ký họcNhắn Zalo cho thầy

Lưới tổ ong (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng B)

Lưới tổ ong
Nguồn: Tin học trẻ 2025 Độ khó: Khó Quy hoạch động QHĐ trên lưới Thêm chiều trạng thái

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng B (bài Lưới tổ ong). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Lưới tổ ong kích thước $N$ gồm $2N - 1$ hàng ngang, đánh số từ trên xuống. Hàng trên cùng có $N$ ô, mỗi hàng sau có nhiều hơn hàng trước 1 ô cho tới hàng giữa ($2N - 1$ ô), rồi mỗi hàng sau lại ít hơn hàng trước 1 ô cho tới hàng dưới cùng ($N$ ô). Mỗi ô ghi một số nguyên.

Lưới tổ ong kích thước 3, các mũi tên chỉ hướng đi chéo xuống

Lưới tổ ong kích thước 3 (hình mình vẽ lại).

Một đường đi xuất phát từ một ô ở hàng trên cùng, kết thúc ở một ô ở hàng dưới cùng; mỗi bước chỉ được đi chéo xuống sang ô kề ở hàng ngay dưới, phía trái hoặc phía phải (theo các mũi tên).

Trước khi chọn đường, bạn được phép đổi chỗ hai số nằm trên cùng một hàng ngang, nhiều nhất một lần (cho toàn bộ lưới).

Yêu cầu: chọn $K$ đường đi ($0 < K \le 2$) đôi một không giao nhau (không có ô chung) sao cho tổng các số trên các ô chúng đi qua là lớn nhất (có tính tới khả năng đổi chỗ một lần nói trên).

Dữ liệu vào:

  • Dòng đầu: hai số nguyên $N, K$ ($1 < N < 100$; $0 < K \le 2$).
  • $2N - 1$ dòng tiếp theo: mỗi dòng là các số trên một hàng ngang, từ trên xuống dưới, từ trái sang phải. Các số là số nguyên trong đoạn $[0, 10^9]$.

Kết quả: một số nguyên là tổng lớn nhất của $K$ đường đi.

Subtask: Subtask 1 (50%): $K = 1$; Subtask 2 (50%): $K = 2$.

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

Ghi chú: đề gốc ghi "tổng độ dài" nhưng nghĩa đúng là tổng các số trên đường đi (khớp ví dụ). Khi $K = 2$, phép đổi chỗ là một lần chung cho cả lưới, không phải mỗi đường một lần.

Ví dụ 1 – input
3 1
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
Ví dụ 1 – output
22
Ví dụ 2 – input
3 2
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
Ví dụ 2 – output
36

Giải thích: Ví dụ 1: đổi chỗ hai số $5$ và $1$ ở hàng thứ 4 (hàng 4 thành 1 3 5 2), rồi đi đường $3 \to 2 \to 8 \to 5 \to 4$ (các ô tô xám trong hình) được tổng $22$. Ví dụ 2 cùng lưới nhưng cần 2 đường không chung ô, tổng lớn nhất là $36$.

Lời mở đầu

Bài QHĐ trên lưới quen thuộc ("đi từ trên xuống, tổng lớn nhất") nhưng có hai "gia vị": một lần đổi chỗ và hai đường đi không giao nhau. Mỗi gia vị được xử lý bằng một kỹ thuật kinh điển: thêm một chiều trạng thái "đã dùng phép đổi chưa", và QHĐ trên cặp vị trí của hai đường đi cùng lúc. Mình đi từ cách dễ nghĩ nhất cho $K = 1$ tới lời giải đầy đủ.

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ộ test22 testNhận xétđổi chỗCách 1thử từng hàngCách 2thêm trạng tháiCách 3cặp ô – 100đTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 22 test (test 1, 2 là hai ví dụ của đề), 11 test $K = 1$ và 11 test $K = 2$. Có các kiểu dữ liệu đặc biệt: toàn số 0, toàn $10^9$, mỗi hàng có một số rất lớn nằm ở mép (phép đổi chỗ rất có lợi)...

Test$N$$K$Số ôKiểu dữ liệuĐáp án
13119ví dụ 122
3217nhỏ (số 0..9)21
44137nhỏ (số 0..9)56
5101271ngẫu nhiên14.793.514.278
65017.351"gai": mỗi hàng có 1 số rất lớn ở mép31.563.831.221
799129.107ngẫu nhiên148.601.495.531
899129.107toàn $10^9$197.000.000.000
999129.107toàn 00
1099129.107"gai" ở mép68.318.734.054
1199129.107số lớn ở 2 mép104.605.553.040
1298128.519số $10^9$ ở giữa mỗi hàng195.000.000.000
23219ví dụ 236
13227nhỏ (số 0..9)22
14227ngẫu nhiên2.186.146.183
155261nhỏ (số 0..9)131
163022.611ngẫu nhiên88.258.290.297
1799229.107ngẫu nhiên297.464.013.858
1899229.107toàn $10^9$394.000.000.000
1999229.107toàn 00
2099229.107"gai" ở mép110.256.128.875
2199229.107số lớn ở 2 mép220.777.087.124
2298228.519số $10^9$ ở giữa mỗi hàng195.147.109.961

Đáp án lớn nhất cỡ $2 \cdot 197 \cdot 10^9 \approx 3{,}9 \cdot 10^{11}$ (hai đường, mỗi đường 197 ô) nên phải dùng long long.

Đã nộp thử trên bộ chấm chính thức
Lời giải đầy đủ theo ý tưởng cách 3 mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask:

SubtaskĐiều kiệnTestCách 1
thử từng hàng		Cách 2
QHĐ 2 trạng thái		Cách 3
QHĐ cặp ô C++		Cách 3
Python
Subtask 1 (50%)$K = 1$1, 3–1211/1111/1111/1111/11
Subtask 2 (50%)$K = 2$2, 13–221/111/1111/115/11

Nhận xétĐổi chỗ thế nào mới có lợi?

Đường đi (hoặc hai đường đi) chỉ dùng một ô (hoặc hai ô) trên mỗi hàng. Phép đổi chỗ trên hàng $r$ chỉ làm tổng thay đổi khi nó đưa một số từ ô ngoài đường vào ô trên đường. Vậy:

  • $K = 1$: đổi ở hàng $r$ tốt nhất là mang số lớn nhất của hàng $mx_r$ vào ô đường đi đang dùng. Nói cách khác: khi đi qua hàng được chọn để đổi, ô đó được tính là $mx_r$ thay vì $a[r][j]$. (Nếu ô đó đã là số lớn nhất thì đổi không có lợi, cũng không có hại.)
  • $K = 2$: hai đường đi qua ô $j_1, j_2$ của hàng $r$. Đổi chỗ tốt nhất là đưa số lớn nhất trong các ô còn lại (khác $j_1, j_2$) vào thay số nhỏ hơn trong hai ô $a[r][j_1], a[r][j_2]$. Muốn biết "số lớn nhất ngoài $j_1, j_2$" nhanh thì chỉ cần nhớ 3 ô lớn nhất của mỗi hàng – trong 3 ô đó chắc chắn có một ô khác $j_1$ và $j_2$.

Còn cách di chuyển: đánh số hàng $r = 0..2N-2$, ô trong hàng $j = 0, 1, \dots$ từ trái sang. Ở nửa trên ($r < N - 1$, hàng dưới dài hơn) ô $j$ đi xuống được ô $j$ và $j + 1$; ở nửa dưới (hàng dưới ngắn hơn) ô $j$ đi xuống được ô $j - 1$ và $j$ (bỏ các ô nằm ngoài hàng).

Cách 1Thử từng hàng để đổi – O(N³) (Subtask 1)

Với $K = 1$, theo nhận xét: thử lần lượt "không đổi" và "đổi ở hàng $sw$" với mọi $sw$. Đổi ở hàng $sw$ thì coi mọi ô của hàng $sw$ có giá trị $mx_{sw}$ (đường đi dùng ô nào ở hàng đó thì ô đó cũng nhận được $mx_{sw}$). Với mỗi lưới như vậy, chạy QHĐ đường đi tổng lớn nhất quen thuộc:

$$f[r+1][k] = \max\big(f[r][j]\big) + b[r+1][k] \quad \text{với mọi ô } j \text{ ở hàng } r \text{ đi xuống được ô } k.$$

C++▶ Chạy tay từng dòng codeCách 1: thử không đổi và đổi ở từng hàng sw, mỗi lần chạy QHĐ đường đi tổng lớn nhất.
Dữ liệu mẫu:
  1. Hàm bestPath là QHĐ "đẩy xuống": từ mỗi ô $(r, j)$ cập nhật cho 2 ô kề ở hàng dưới. Biến k1 là ô kề bên trái ($j$ ở nửa trên, $j - 1$ ở nửa dưới), ô kề bên phải là k1 + 1.
  2. Có $2N - 1 \approx 200$ hàng để thử, mỗi lần QHĐ trên khoảng $3N^2 \approx 30\,000$ ô → khoảng $6 \cdot 10^6$ phép tính, rất nhanh.
  3. Cách này chỉ đúng cho $K = 1$ (code vẫn chạy với $K = 2$ nhưng in sai).
Không gian$O(N^2)$
Thời gian$O(N \cdot N^2) = O(N^3)$

Kết quả chạy thật: Bản C++ đúng 12/22 test, sai test 2, 13–18, 20–22 (các test đúng chạy lâu nhất 0.028s) → 50 điểm (đúng toàn bộ subtask 1; test 19 của subtask 2 đúng "ăn may" vì lưới toàn số 0).

Cách 2Thêm trạng thái "đã đổi chưa" – O(N²) (Subtask 1)

Thay vì chạy QHĐ $2N$ lần, ta cho QHĐ "nhớ" thêm việc đã dùng phép đổi hay chưa:

  • $f[j][0]$ = tổng lớn nhất của đường đi tới ô $j$ của hàng hiện tại, chưa dùng phép đổi;
  • $f[j][1]$ = tổng lớn nhất tới ô $j$, đã dùng phép đổi ở một hàng nào đó (kể cả hàng hiện tại).

Đi từ ô $j$ (hàng $r$) xuống ô $k$ (hàng $r + 1$):

$$g[k][0] = \max\big(f[j][0] + a[r+1][k]\big), \qquad g[k][1] = \max\big(f[j][1] + a[r+1][k],\ \ f[j][0] + mx_{r+1}\big).$$

Vế thứ hai của $g[k][1]$ chính là "dùng phép đổi ở hàng $r + 1$". Hàng đầu tiên: $f[j][0] = a[0][j]$, $f[j][1] = mx_0$. Em bấm Tiếp để xem bảng $f$ được tính dần từng hàng (mỗi ô hiện f0 | f1), cuối cùng là đường đi tốt nhất và chỗ đổi:

Ví dụ nhanh:
C++▶ Chạy tay từng dòng codeCách 2: QHĐ f[j][u] – u cho biết đã dùng phép đổi chỗ hay chưa.
Dữ liệu mẫu:
  1. Chỉ cần 2 mảng một chiều f (hàng hiện tại) và g (hàng dưới) vì mỗi hàng chỉ phụ thuộc hàng ngay trên.
  2. Đáp án là giá trị lớn nhất của cả f[j][0] lẫn f[j][1] ở hàng cuối (không bắt buộc phải đổi).
Không gian$O(N^2)$
Thời gian$O(N^2)$

Kết quả chạy thật: Bản C++ đúng 12/22 test, sai test 2, 13–18, 20–22 (các test đúng chạy lâu nhất 0.005s). Bản Python đúng 12/22 test, sai test 2, 13–18, 20–22 (các test đúng chạy lâu nhất 0.040s). Vẫn 50 điểm – nhưng kỹ thuật "thêm chiều trạng thái" này chính là chìa khoá cho $K = 2$.

Cách 3QHĐ trên cặp ô của hai đường – O(N³) (full)

Với $K = 2$, hai đường đi đi xuống song song, mỗi hàng mỗi đường dùng một ô. Vì hai đường không chung ô và mỗi bước chỉ dịch tối đa một ô, đường bên trái luôn ở bên trái (không thể "vượt" qua nhau mà không chung ô). Vậy trạng thái QHĐ là:

$$f[j_1][j_2][u] \quad (j_1 < j_2):\ \text{tổng lớn nhất khi ở hàng hiện tại đường trái ở ô } j_1, \text{ đường phải ở ô } j_2, \ u = \text{đã đổi chưa}.$$

Từ $(j_1, j_2)$ mỗi đường có 2 lựa chọn ô ở hàng dưới → 4 cặp $(k_1, k_2)$, chỉ giữ cặp có $k_1 < k_2$. Gọi giá trị hàng $r+1$ khi đi qua $(k_1, k_2)$ là $u_0 = a[k_1] + a[k_2]$ (không đổi) và $u_1 = u_0 - \min(a[k_1], a[k_2])$ $+ (\text{số lớn nhất ngoài } k_1, k_2)$ (đổi ở hàng này, lấy max với $u_0$). Chuyển trạng thái:

$$g[k_1][k_2][0] \leftarrow f[j_1][j_2][0] + u_0, \qquad g[k_1][k_2][1] \leftarrow \max\big(f[j_1][j_2][0] + u_1,\ \ f[j_1][j_2][1] + u_0\big).$$

Code đầy đủ gồm solve1 (giống cách 2) cho $K = 1$ và solve2 cho $K = 2$; hàm rowVal tính $u_0, u_1$ nhờ 3 ô lớn nhất của hàng (top).

C++▶ Chạy tay từng dòng codeCách 3: K = 1 dùng solve1 (như cách 2), K = 2 dùng QHĐ trên cặp ô (j1 < j2) kèm trạng thái đã đổi.
Dữ liệu mẫu:
  1. Mỗi hàng có tối đa $2N - 1 \approx 197$ ô nên khoảng $197^2 / 2 \approx 19\,000$ cặp, nhân 4 cách đi, nhân 197 hàng ≈ $1{,}5 \cdot 10^7$ phép tính – chạy khoảng 0,1 giây.
  2. Bảng f lưu phẳng trong vector một chiều cỡ $W \cdot W \cdot 2$ với $W = 2N$; giá trị NEG = -1 đánh dấu trạng thái không đạt được (mọi tổng thật đều $\ge 0$).
  3. Không cần xét đổi chỗ giữa chính hai ô $j_1, j_2$ (chỉ chuyển số giữa hai đường, tổng không đổi).
Không gian$O(N^2)$
Thời gian$O(N^3)$

Kết quả chạy thật: Bản C++ đúng 22/22 test, chạy lâu nhất 0.096s. Full điểm. Bản Python đúng 16/22 test, quá thời gian test 17–22 (các test đúng chạy lâu nhất 0.270s) – bản Python dùng từ điển cho các cặp, với $N = 99$, $K = 2$ thì $1{,}5 \cdot 10^7$ bước là quá sức Python.

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

CáchNgôn ngữĐúngLâu nhất
(test đúng)		Điểm theo subtask
1. Thử từng hàng đổi + QHĐ (K = 1)C++12/220.028s50%
2. QHĐ thêm trạng thái "đã đổi" (K = 1)C++12/220.005s50%
Python12/220.040s50%
3. QHĐ trên cặp ô (K = 1 và 2)C++22/220.096s100%
Python16/220.270s50%
Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây). Ba ý cần nhớ: (1) phân tích phép biến đổi trước (đổi chỗ chỉ có ích khi đưa số lớn nhất ngoài đường vào đường) để biến nó thành một lựa chọn đơn giản; (2) "được dùng tối đa 1 lần" → thêm một chiều 0/1 vào trạng thái; (3) nhiều đường đi không giao nhau → QHĐ trên bộ vị trí của tất cả các đường, nhờ tính chất các đường giữ nguyên thứ tự trái – phải.
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 😇

Nhận xét

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)