Học sinh giỏi Quốc gia (VOI)

Bài gợi ý: Liên Minh Dễ Dàng
Tóm tắt: Cho dãy \(a_1, a_2, \dots, a_n\). Ta cần xử lý thao tác gán \(a_i = x\) và tìm phong độ ban đầu nhỏ nhất để lần lượt thắng các trận từ \(l\) đến \(r\). Tại mỗi trận \(k\), phong độ hiện tại phải đạt tối thiểu \(a_k\), rồi được cộng thêm \(a_k\).

Xét ví dụ với ba trận có chỉ số \(2, 10, 5\). Nếu bắt đầu với \(8\) điểm, bạn hạ trận đầu và có \(8 + 2 = 10\) điểm. Mức này vừa đủ thắng trận hai để đạt \(20\) điểm, rồi vượt qua trận cuối. Nếu chỉ bắt đầu với \(7\) điểm, bạn xong trận đầu chỉ có \(9\) điểm và sẽ thua ở trận thứ hai.

Ta đang lặp lại phép tính nào khi ghép các trận liên tiếp? Giả sử đoạn bên trái cần phong độ tối thiểu \(L.req\) và tăng thêm \(L.sum\) điểm. Để đủ \(R.req\) điểm khi bước sang đoạn bên phải, bạn cần chuẩn bị sẵn ít nhất \(R.req - L.sum\) điểm trước khi vào đoạn trái.

Vì vậy, mỗi đoạn con chỉ cần lưu hai đại lượng: tổng phong độ \(sum\) và mức khởi đầu tối thiểu \(req\). Khi gộp hai đoạn kề nhau, giá trị mới được tính theo \(req = \max(L.req, R.req - L.sum)\) cùng \(sum = L.sum + R.sum\).

Cách duyệt trực tiếp từng phần tử sẽ mất nhiều thời gian cho mỗi truy vấn khi \(q\) lớn. Do phép gộp trên có tính kết hợp, cây phân đoạn (Segment Tree) là cấu trúc phù hợp để quản lý và cập nhật từng vị trí.

Khi cài đặt, mỗi nút lá ứng với phần tử \(a_i\) được gán sum = a_i và req = a_i. Khi truy vấn đoạn \([l, r]\), bạn lần lượt gộp các nút đại diện và lấy trường req của kết quả cuối cùng.

Tóm tắt: Ta chỉ nên dùng cấu trúc dữ liệu để tối ưu quy hoạch động khi bước chuyển trạng thái tương đương với một bài toán truy vấn đoạn quen thuộc.

Giả sử bạn cần tính mảng quy hoạch động (DP) với \(dp[i]\) là chi phí nhỏ nhất để đi đến vị trí \(i\). Từ một vị trí \(j\) bất kỳ trong đoạn \([i-k, i-1]\), bạn có thể nhảy thẳng đến \(i\). Công thức chuyển trạng thái được viết là \(dp[i] = \min(dp[j]) + a[i]\) với mọi \(i-k \le j \le i-1\).

Nếu duyệt lại toàn bộ các vị trí \(j\) cho từng \(i\), bạn mất \(O(k)\) phép so sánh ở mỗi bước. Khi \(n = 10^5\) và \(k = 10^5\), tổng thời gian chạy lên tới \(O(n \cdot k)\) và chắc chắn sẽ bị quá thời gian.

Cấu trúc nào trả lời được truy vấn này? Khi \(i\) tăng dần, đoạn \([i-k, i-1]\) chỉ dịch sang phải một bước: một phần tử cũ ở bên trái bị đẩy ra ngoài, và một giá trị \(dp\) mới được thêm vào bên phải.

Với dạng cửa sổ trượt tịnh tiến này, ta chỉ cần một hàng đợi hai đầu (deque) để lưu các chỉ số \(j\) có \(dp[j]\) tăng dần. Quy trình cập nhật cho mỗi \(i\) gồm 3 bước:

• Rút các chỉ số \(j < i - k\) ra khỏi đầu deque.
• Lấy \(dp[j]\) nhỏ nhất tại đầu deque để tính \(dp[i] = dp[j] + a[i]\).
• Rút các chỉ số ở cuối deque có \(dp[j] \ge dp[i]\), rồi thêm \(i\) vào cuối deque.

Khi gặp một bài quy hoạch động, bạn hãy viết biểu thức phụ thuộc của \(dp[i]\) theo \(j\) ra nháp trước. Nếu vùng \(j\) cần lấy \(\min\), \(\max\) hoặc lấy tổng là một đoạn trượt hoặc một khoảng giá trị liên tục, bạn hãy nghĩ ngay đến việc dùng deque, cây phân đoạn (Segment Tree) hoặc bảng Fenwick thay vì chạy vòng lặp duyệt trâu.

Bài gợi ý: CSES - Knuth Division | Phép chia Knuth
Tóm tắt: Bạn cần chia mảng \(n\) số nguyên thành \(n\) phần tử riêng lẻ qua các nhát cắt. Mỗi lần cắt một đoạn liên tiếp thành hai nửa, bạn chịu chi phí bằng tổng các số trong đoạn đó. Hãy tìm tổng chi phí nhỏ nhất để hoàn thành toàn bộ các nhát cắt.

Xét ví dụ với dãy ba số 2, 7, 3. Nhát cắt đầu tiên luôn tốn tổng chi phí của cả dãy là \(2 + 7 + 3 = 12\). Nếu bạn cắt giữa \(7\) và \(3\), mảng tách thành [2, 7] và [3], sau đó cắt tiếp [2, 7] tốn thêm \(2 + 7 = 9\), tổng chi phí là \(12 + 9 = 21\). Nếu bạn cắt giữa \(2\) và \(7\), nhát sau cắt [7, 3] tốn \(7 + 3 = 10\), tổng chi phí là \(12 + 10 = 22\). Ta thấy việc chọn vị trí cắt ở mỗi bước quyết định trực tiếp chi phí của các bước tiếp theo.

Để tìm cách cắt tốt nhất cho từng đoạn từ vị trí \(i\) đến \(j\), ta dùng quy hoạch động (phương pháp lưu lại kết quả của các đoạn ngắn để tính cho đoạn dài hơn). Gọi \(dp[i][j]\) là chi phí nhỏ nhất để chia đoạn \([i, j]\) thành từng phần tử đơn lẻ:
\(dp[i][j] = \min_{i \le k < j} (dp[i][k] + dp[k+1][j]) + \text{sum}(i, j)\)

Công thức trên nghĩa là: ta thử mọi vị trí cắt \(k\), lấy chi phí tối ưu của nửa trái \(dp[i][k]\) cộng chi phí tối ưu của nửa phải \(dp[k+1][j]\), rồi cộng thêm tổng các số \(\text{sum}(i, j)\) của cả đoạn \([i, j]\).

Với \(n = 5000\), số lượng đoạn \([i, j]\) lên tới khoảng \(1.25 \times 10^7\). Nếu mỗi đoạn ta lại duyệt biến \(k\) qua toàn bộ độ dài của nó, số phép tính sẽ lên tới cỡ \(5000^3 / 6 \approx 2 \times 10^{10}\) thao tác và làm chương trình chạy quá thời gian cho phép. Liệu ta có cần phải thử lại tất cả các vị trí \(k\) từ đầu đến cuối đoạn hay không?

Gọi \(opt[i][j]\) là vị trí cắt \(k\) tốt nhất của đoạn \([i, j]\). Vì hàm chi phí tính tổng có tính chất cộng dồn tăng dần, vị trí cắt tối ưu của đoạn \([i, j]\) luôn bị chặn bởi điểm cắt tối ưu của hai đoạn con ngắn hơn:
\(opt[i][j-1] \le opt[i][j] \le opt[i+1][j]\)

Tính chất thu hẹp này gọi là tối ưu Knuth (Knuth's optimization). Nhờ bất đẳng thức trên, thay vì duyệt toàn bộ từ \(i\) đến \(j-1\), vòng lặp \(k\) chỉ cần chạy trong đoạn hẹp từ \(opt[i][j-1]\) đến \(opt[i+1][j]\), giúp tổng số thao tác trên toàn bảng giảm xuống chỉ còn khoảng \(O(n^2)\).

Các bước cài đặt chính cho bài toán:

• Dựng mảng tiền tố pref[i] để tính nhanh \(\text{sum}(i, j) = pref[j] - pref[i-1]\).
• Khởi tạo cơ sở với đoạn độ dài \(1\): gán dp[i][i] = 0 và opt[i][i] = i cho mọi \(i\) từ \(1\) đến \(n\).
• Duyệt độ dài đoạn \(len\) tăng dần từ \(2\) đến \(n\), duyệt đầu mút trái \(i\) từ \(1\) đến \(n - len + 1\) và đặt \(j = i + len - 1\).
• Cho biến \(k\) chạy từ \(opt[i][j-1]\) đến \(\min(j-1, opt[i+1][j])\), cập nhật giá trị nhỏ nhất vào \(dp[i][j]\), lưu lại chỉ số \(k\) tối ưu vào \(opt[i][j]\), rồi in ra dp[1][n].

Tóm tắt: Xác định đúng những cạnh mang chi phí 0 hoặc 1 giúp ta tối ưu thuật toán tìm đường đi ngắn nhất về thời gian tuyến tính.

Xét một đồ thị có các cạnh chỉ mang trọng số \(0\) hoặc \(1\), ví dụ như thao tác giữ nguyên trạng thái (chi phí \(0\)) hoặc thực hiện một lần đổi hướng (chi phí \(1\)). Giả sử ta đang xét đỉnh \(u\) có khoảng cách ngắn nhất hiện tại là \(d[u] = 2\). Từ \(u\), ta có một cạnh nối sang \(v\) với trọng số \(0\) và một cạnh sang \(w\) với trọng số \(1\). Khoảng cách mới tới \(v\) vẫn là \(2\), trong khi khoảng cách tới \(w\) tăng lên \(3\).

Dữ liệu nào cần được ghi nhớ? Nếu dùng hàng đợi ưu tiên priority_queue thông thường, ta phải tốn thêm chi phí \(O(\log V)\) cho mỗi lần cập nhật. Tuy nhiên, các giá trị khoảng cách được sinh ra từ \(u\) chỉ có thể là \(d[u]\) hoặc \(d[u] + 1\).

Nhận xét này dẫn trực tiếp tới kỹ thuật BFS 0-1 sử dụng deque (hàng đợi hai đầu). Ta luôn lấy đỉnh ở đầu hàng đợi để duyệt tiếp. Khi tối ưu được đỉnh \(v\) qua cạnh trọng số \(0\), ta đưa \(v\) vào đầu bằng push_front(v). Khi tối ưu đỉnh \(w\) qua cạnh trọng số \(1\), ta đưa \(w\) vào cuối bằng push_back(w).

Điều luôn đúng cần duy trì: khoảng cách của các đỉnh nằm trong deque luôn chênh lệch không quá \(1\) và không giảm từ đầu đến cuối. Danh sách thao tác cốt lõi gồm:

1. Xét cạnh \((u, v)\) trọng số \(0\): nếu \(d[v] > d[u]\), gán \(d[v] = d[u]\) và gọi push_front(v).
2. Xét cạnh \((u, w)\) trọng số \(1\): nếu \(d[w] > d[u] + 1\), gán \(d[w] = d[u] + 1\) và gọi push_back(w).

Mỗi khi tiếp cận một bài đồ thị có trọng số, bạn hãy thử phân tích xem mỗi bước chuyển trạng thái có thật sự cần một giá trị bất kỳ hay chỉ nhận hai mức chi phí \(0\) và \(1\). Nếu chỉ có hai mức, việc thay priority_queue bằng deque sẽ lập tức đưa độ phức tạp về \(O(V + E)\).