Đề bài: Tối ưu hóa đường đi trên cây với điều kiện tô màu đỉnh

Mô tả bài toán

Giả sử có một cây với các đỉnh được tô màu đen hoặc trắng. Một đường đi tối ưu bắt đầu từ đỉnh x và kết thúc ở đỉnh y. Đường đi ngắn nhất từ x đến y được gọi là đường đi chính, và các cây con còn lại sau khi loại bỏ đường đi chính được gọi là cây phụ.

Mục tiêu là đi qua đường đi chính và đồng thời giải quyết các cây phụ (tô trắng tất cả các đỉnh) sao cho số bước di chuyển là ít nhất. Khi đến một nút trên đường đi chính có kết nối với cây phụ, ta nên giải quyết cây phụ ngay tại thời điểm đó.

Thuật toán giải quyết cây phụ

1. Xử lý cây phụ:

   • Cây phụ gốc tại một nút trên đường đi chính. Khi xử lý xong cây phụ, ta cần quay lại gốc để tiếp tục đi.
   • Mỗi lần di chuyển sẽ thay đổi tính chẵn lẻ của đỉnh màu đen, và mỗi cạnh được đi qua một số lần chẵn.
   • Nếu số đỉnh đen là chẵn, tô tất cả thành trắng.
   • Nếu số đỉnh đen là lẻ, để đỉnh gốc màu đen và đổi màu tất cả các đỉnh khác.

2. Các bước thực hiện:

   • Giải quyết đệ quy từng cây con.
   • Nếu cây con còn đỉnh đen sau khi xử lý, đi xuống và lên lại để chuyển màu thành trắng (đồng thời thay đổi trạng thái của nút hiện tại).
   • Làm tương tự khi di chuyển dọc theo đường đi chính.

Quy hoạch động

• Định nghĩa dp[i][j][k] là chi phí tối thiểu (số bước di chuyển) để giải quyết cây con gốc tại nút i, với:
  • j = 0 nếu nút i còn màu đen sau khi xử lý.
  • j = 1 nếu nút i màu trắng sau khi xử lý.
  • k đánh dấu đường đi chính có đi qua i hay không (k = 0 hoặc k = 1).

Trường hợp k = 0 (không có đường đi chính đi qua)

• Tổng chi phí là tổng các trạng thái dp của cây con với k = 0.
• Thêm số lần di chuyển qua các cạnh giữa i và các cây con của nó.
• Theo dõi số lần thay đổi trạng thái của i để xác định trạng thái cuối cùng.

Trường hợp k = 1 (đường đi chính đi qua)

• Có hai lựa chọn:
  1. Kế thừa đường đi chính từ một cây con.
  2. Bắt đầu đường đi chính từ nút i.
• Chuyển trạng thái:
  • Tổng chi phí của các cây con với k = 0, trừ một cây con có k = 1.
  • Hoặc tổng chi phí của tất cả các cây con với k = 0.

Xác định nút trung gian trên đường đi chính

• Mỗi đường đi chính có thể có một nút sao cho đường đi đi qua nó và cả hai đầu mút thuộc cây con của nó.
• Có hai lựa chọn:
  1. Lấy giá trị dp của nó với k = 1 và thêm số bước cần thiết để giải quyết phần cây phía trên.
  2. Lấy hai giá trị dp từ hai cây con có k = 1 và các cây con khác có k = 0.

Độ phức tạp

• Độ phức tạp tổng thể của thuật toán là O(n).

Một đoạn tốt là đoạn có tính chất: tồn tại một số xuất hiện đúng 1 lần, một số khác xuất hiện đúng 2 lần, ..., và một số xuất hiện đúng K lần.

Subtask 1:

• Duyệt từng đoạn và kiểm tra điều kiện với độ phức tạp ( O(N^2K) ).

Subtask 2:

• Nếu các phần tử thuộc đoạn ([1, K]), đoạn tốt phải có độ dài ( \frac{K(K+1)}{2} ).
• Kiểm tra ( O(N) ) đoạn.

Subtask 3:

• Đếm số đoạn mà phần tử tại vị trí ( i ) xuất hiện đúng một lần.
• Với mỗi ( i ), xác định:
  
  • ( Li ): vị trí xuất hiện gần nhất bên trái của ( a[i] ).
  • ( Ri ): vị trí xuất hiện gần nhất bên phải của ( a[i] ).
• Điều kiện để ( a[i] ) xuất hiện đúng 1 lần: ( Li < x \leq i \leq y < Ri ).
• Bài toán trở thành tính hợp nhất các hình chữ nhật trên mặt phẳng với độ phức tạp ( O(N \log N) ).

Subtask 4:

• Áp dụng bao hàm - loại trừ để tính giao của các tập hợp ( S1, S2, \ldots, S_K ).
• Độ phức tạp: ( O(2^K KN \log N) ).

Subtask 1 (30%, m, n ≤ 20; aᵢⱼ ≤ 10⁴)

Duyệt tất cả các hình chữ nhật, đếm xem nếu không có số nào xuất hiện 2 lần thì cập nhật kết quả.

Độ phức tạp: O(m³n³).

Subtask 2 (30%, 20 < m, n ≤ 100; aᵢⱼ ≤ 10⁴)

Duyệt khe chặn bởi hàng i và hàng j (ký hiệu: skew(i, j)), trượt sang trái cửa sổ là giao của cột k với skew(i, j).

Với mỗi giá trị v, duy trì thông tin cột gần nhất bên phải chứa v (chỉ xét trong skew(i, j)). Các thông tin này cho ta tổng hợp được hình chữ nhật có cạnh trái là cột k có thể mở rộng về bên phải nhiều nhất là đến cột nào, từ đó cập nhật kết quả.

Độ phức tạp: O(m³n).

Subtask 3 (40%, 100 < m, n ≤ 400)

Cải tiến thuật toán ở subtask 2 bằng cách áp dụng quy hoạch động.

Với mỗi skew(i, j), gọi f(i, j, k) = t là cột xa nhất về bên phải mà hình chữ nhật có cạnh trái là cột k, cạnh phải là cột t hợp lệ. Công thức quy hoạch động:

f[i][j][k] = min(f[i + 1][j][k], f[i][j - 1][k], f[i][j][k + 1])

Độ phức tạp: ~O(m^2n)~

Kí hiệu truy vấn với số tiền ~s~, có thể năng cấp các con đường giữa ~u~ và ~v~ đạt tốc độ nhỏ nhất cực đại là ~Q(u,v,s)~

Subtask 1: Có ~n, q~ đủ nhỏ, với mỗi truy vấn, có thể xây dựng danh sách cạnh trên đường nôi ~u,v~ ký hiệu ~P(u, v)~ trong thời gian ~O(n)~ bằng cách

• BFS/DFS từ ~u~ cho đến khi gặp ~v~
• Xây dựng trước các thông tin của nút cha (độ sâu của tất cả các đỉnh). Xác định mỗi ~P(u,v)~ bằng cách di chuyển dần qua từng cạnh từ u và v lên đến gốc cho đên khi gặp ~lca(u, v)~

Sau khi xác định được ~P(u, v)~, tính ~Q(u, v, s)~ bằng 1 trong 2 cách:

• Năng cấp các cạnh ~e(u, v, v_0, v_1, cost)~ thuộc ~P(u, v)~ theo thứ tự ~v_0~ tăng dần cho đến khi số tiền còn lại không đủ để nâng cấp cạnh tiếp theo. Kết quả truy vấn nhận được là

min(v_1) của các cạnh đã năng cấp 
max(v_0) của các cạnh chưa năng cấp

• Tìm kiếm nhị phân tốc độ tối thiểu ~x~, với mỗi ~x~, duyệt qua các cạnh ~e(u, v, v_0, v_1, cost)~ thuộc ~P(u, v)~, có 3 khả năng
  • ~x \le v_0~: chi phí cho cạnh này bằng 0
  • ~v_0 < x \le v_1~: chi phí cho cạnh này bằng cost
  • ~v_1 < x~: không thể đạt tốc độ tối thiểu ~x~, chi phí cạnh này là ~inf~ x chấp nhận được khi tổng chi phí ~\le s~

ĐPT: ~O(nqlog(n))~

Subtask 2, 3: ~n ,q \le 10^5~ Ta thấy không thể tìm được hết ~P(u, v)~ vì ĐPT là ~O(n)~ cho một bộ

Thực hiện TKNP ~Q(u,v,s)~. Với mỗi tốc độ ~x~, ta cần tính nhanh tổng chi phí nâng cấp các cạnh thuộc ~P(u,v)~ mà tốc độ ban đầu ~v_0 < x~.

Sử dụng mảng thưa, có thể xác định nhanh ~z=lca(u,v)~ trong ~O(logn)/O(1)~

Ký hiệu ~f(t)~ là tổng chi phí nâng cấp đường từ nút gốc đến t sao cho tốc độ tối thiểu ~\ge x~. Chi phí cho con đường từ ~u~ đến ~v~ là ~f(u) + f(v) - 2f(z)~

Nếu có thể tính ~f(t)~ trong ~O(log n)~ thì chi phí tính ~Q(u, v, s)~ sẽ là ~O(log n log maxV)~.

Với mỗi cạnh ~e(u, v, v0, v1, cost)~, tạo hai sự kiện
• ~(v0, cost, id)~: thể hiện cạnh ~id~ cần chi phí ~cos~t nếu ~v0 < x ≤ v1~ • ~(v1, +∞, id)~: thể hiện cạnh ~id~ cần chi phí ~+∞~ nếu ~v1 < x~

Tiếp theo cần xây dựng cấu trúc dữ liệu cho phép tính toán tổng chi phí nâng cấp các con đường từ gốc (1) đến đỉnh ~t~ tuỳ ý sao cho tốc độ tối thiểu ~≥ x~.

Dùng mảng chứa Euler tour của cây (~2n – 2~ phần tử), cần duy trì segment tree quản lý tổng chi phí trên mảng này. Tuy nhiên, mỗi sự kiện (trong ~2n – 2~ sự kiện) cho ta một segment tree, cần gộp chúng lại bằng persistent segment tree. Sắp xếp các sự kiện tăng dần theo tốc độ, segment tree ứng với ~event[i + 1]~ được tính toán theo segment-tree ứng với ~event[i]~ (chỉ sai khác trên đường từ gốc segment tree xuống đúng hai lá).

Kết hợp tất cả các kĩ thuật/phân tích trên, tổng chi phí tính toán là ~O(n log n + q log n log maxV)~.

Chi phí bộ nhớ:~O(n log n)~, tổng số nút trong persistent segment tree đạt đến ~2(2n – 2) log₂(2n – 2)~, khoảng ~8·10⁶~ nút.

Mục tiêu của bài toán là giúp Minh đến được đích đúng thời gian, trong các trường hợp đó, tìm thời gian Quang đến N sớm nhất

Gán nhãn khoảng cách từ 1 đến tất cả các đỉnh còn lại, ta có mảng dist1[1], dist1[2], ..., dist1[n]

Xét trên đồ thị đảo ngược cạnh (tức là chiều của tất cả các cạnh trên đồ thị bị đảo ngược), gán nhãn khoảng cách từ ~K~ và từ ~N~ đến các đỉnh còn lại ta có mảng ~distK~ và ~distN~

Subtask 2: K = N, ta sử dụng Dijkstra từ đỉnh 1, kết quả là ~dist1[n]~

ĐPT: ~O(nlogn)~

Subtask 1, 3: Ta thực hiện Dijkstra từ 3 đỉnh: từ 1 với đồ thị xuôi, ~N, K~ trên đồ thị ngược.

Xét các đỉnh ~u~ có dist1[u] + distK[u] \le X Kết quả của bài toán là min(dist1[u] + distN[u])

ĐPT: ~O(nlogn)~

Bài này gồm 3 subtask là 3 bài toán con khác nhau

Subtask 1: Sử dụng vòng lặp khi k được sắp xếp không tăng, ta có thể đưa ra nhận xét là các game được chọn để chơi là các game ở đầu với ~k_i \ge k_{i+1}~, và chơi cho đến hết thời gian ~t~

ĐPT: ~O(n)~

Subtask 2: DP Knapsack để chọn game chơi, với trạng thái sau

dp[i][j] = max(dp[i - 1][j - b], dp[i - 1][j - a] + k[i]);

với ~i, j~ lần lượt là số game và thời gian được sử dụng để chơi/xem đến game thứ ~i~

ĐPT: ~O(n * t)~

Subtask 3: Chiến lược tham lam khi ~k~ được sắp xếp không giảm là chọn các trò chơi liền kề nhau, các trò cọn để chơi luôn nằm sau các trò chỉ tìm hiểu mà không chơi.

Giả sử tổng độ hấp dẫn là ~S~, Việt chọn chơi trò ~i~ và không chơi trò ~i+1~ thì tổng độ hấp dẫn là ~S+k_i~. Trong khi vẫn sử dụng thời gian như vậy, nhưng không chơi ~i~, chơi ~i+1~ thì độ hấp dẫn là ~S+k_{i+1}~

Để có độ hấp dẫn tối đa, các game mà không chơi sẽ nằm trước các game được chợn để chơi

Nếu bỏ qua ~x~ game đầu tiên, thì thời gian còn lại để chơi là ~t - x * b~. Ta dễ dàng có thể tính được số game chơi là ~y=floor((t - b * x) / a)~. Có thể tính được hấp dẫn trong ~O(1)~ sử dụng prefixsum.

ĐPT: ~O(n)~