Bài này mình ra đề từ thời thi VNOI Marathon 2012, hôm nay lục lại máy tính thấy có lời giải, nên đăng lại lên đây để các bạn tham khảo.

Tóm tắt đề bài:

• Cho một cây gồm N đỉnh, trên mỗi đỉnh có 1 nhãn.
• Với u là một đỉnh lá, gọi dãy số thu được khi di chuyển từ gốc đến u là T(u).
• Cho Q truy vấn, mỗi truy vấn có dạng một dãy số A = (a1, a2, ..., ak). Hỏi là có đường đi từ gốc đến lá nào chứa A là dãy con không.

Lời giải:

30% test đầu tiên:

Với N, Q và K không quá 100, ta có thể giải bài toán với độ phức tạp O(Q*N*K).

Nhận xét là ta cần xét không quá N đường đi: mỗi đường đi có dạng từ một đỉnh đi ngược về gốc của cây. Vì vậy, với mỗi truy vấn, ta có thể duyệt qua tất cả các đường đi này, với mỗi đường đi ta mất O(K) để kiểm tra 2 xâu giống nhau.

Đáng tiếc là có nhiều bạn để mất điểm do duyệt đường đi từ gốc xuống (có quá nhiều đường đi) hoặc cài đặt sai.

20% test tiếp theo:

Để giải được 20% tiếp theo, vì K nhỏ, nên ta chỉ cần quan tâm đến O(N*K) đường đi. Bằng việc tiền xử lý, tính trước hash value của các xâu này, ta có thể so sánh các xâu trong O(1). Nhờ vậy, ta dễ dàng có được thuật toán O(N*K + Q*K).

20% test tiếp theo:

Với cây có dạng đường thẳng, ta có thể dùng suffix array:

Nối tất cả các truy vấn cùng với xâu đường đi từ gốc đến lá của cây. Tính mảng suffix array và lcp. Kết hợp với một cấu trúc dữ liệu (chẳng hạn interval tree) để tìm giá trị nhỏ nhất giữa một suffix thể hiện truy vấn và một suffix thể hiện một đường đi của cây, ta có thể giải được bài toán trong O((N+sumK) log(N+sumK))

30% test cuối cùng:

Để giải quyết trọn vẹn bài toán, có 3 hướng đi: hash, suffix array và Aho-corasick. Ở đây mình chỉ trình bày cách giải dùng hash và suffix array. Các bạn muốn học về Aho-corasick có thể tìm hiểu trên wiki.

Hash:

Nhận xét: chỉ có tối đa sqrt(Q), tức là khoảng 200 giá trị khác nhau của K. Vì vậy, nếu xử lý offline, ta chỉ cần tính trước O(sqrt(Q) * N) giá trị khác nhau của hash, khá nhỏ, tuy nhiên vẫn vô cùng khó để có thể qua được hết test với time limit 3s. (Lời giải của yenthanh132 được 75 điểm do bị quá thời gian 5 test). Tuy nhiên để qua toàn bộ test với hash không phải là điều không thể, do giới hạn thời gian khá lỏng. Để qua được các test lớn, các bạn cần có một số heuristic tốt (và cách đánh giá thời gian với các truy vấn đó) giúp trả lời nhanh các truy vấn.

Một số heuristic có thể dùng:

• Thay vì duyệt tất cả các đường đi từ các đỉnh, chỉ duyệt từ những đỉnh có nhãn bằng với số thứ nhất trong truy vấn.

• Với các truy vấn có số không xuất hiện trên cây, hoặc số lần xuất hiện của một số lớn hơn tổng số lần xuất hiện trên cây, kết quả luôn là không giống. Có thể làm mạnh hơn heuristic này bằng việc kiểm tra thêm khoảng cách giữa 2 lần xuất hiện của một số, khoảng cách từ lá và gốc đến số đó trên cây.

Nếu cài đặt tốt, kết hợp hash với 2 heuristic trên, các bạn có thể đạt trọn vẹn 100 điểm.

Suffix array:

Tư tưởng chính vẫn giống như cách làm với 20% trước: Các bạn cần sort lại các suffix của truy vấn cùng với các đường đi trên cây. Tuy nhiên các bạn cần hiểu tương đối rõ về suffix array.

Mấu chốt của thuật toán suffix array là từ việc sắp xếp các xâu độ dài L, ta có thể sắp xếp các xâu độ dài 2L. Với một mảng quy hoạch động lưu lại cha thứ 2^j của đỉnh i (giống như cách làm LCA), ta có thể tìm kiếm nhanh chóng cha của các đỉnh trong O(logN). Các thao tác so sánh để sắp xếp ta có thể làm tương tự thuật toán suffix array thông thường. Từ đấy thu được một thuật toán áp dụng tư tưởng suffix array trong O((N+sumK)logNlog(N+sumK)). Để tính mảng lcp, cách trực quan nhất là chặt nhị phân kết hợp với hash.

Nhận xét của tác giả

Bài này là một bài khá khó, được ra với mục đích kiểm tra xem các bạn sẽ xoay sở thế nào khi không nghĩ được thuật toán tốt. Nếu cài đặt kết hợp được nhiều heuristic tốt, các bạn cũng có thể đạt được khá nhiều điểm cho bài này. Đáng tiếc là không có bạn nào đi theo con đường này.