Phân tích

Trong bài toán này, mọi người được chào đón bằng một bài toán quy hoạch động (dynamic programming) khá cơ bản.

Từ chúng ta muốn tìm là S = "welcome to code jam", trong một chuỗi dài T. Thực tế, giải pháp không có nhiều khác biệt khi chúng ta muốn tìm bất kỳ chuỗi S nào. Việc hình dung các trường hợp cho các từ ngắn sẽ rất trực quan.

Trong trường hợp S chỉ là một ký tự duy nhất, bạn chỉ cần đếm số lần ký tự này xuất hiện trong T. Nếu S = "xy" là một chuỗi có độ dài 2, thay vì duyệt vét cạn tất cả các vị trí có thể, ta có thể thực hiện trong thời gian tuyến tính, bắt đầu từ trái sang phải. Với mỗi lần xuất hiện của 'y', ta cần biết có bao nhiêu chữ 'x' đã xuất hiện trước chữ 'y' đó.

Giải pháp tổng quát tuân theo mô hình này. Hãy lấy lại ví dụ S = "welcome to code jam". Giải pháp chính thức sẽ rõ ràng từ ví dụ này; và bạn luôn có thể tải các lời giải tốt (với những kỹ thuật lập trình hay) từ bảng điểm.

Vì vậy, hãy định nghĩa, đối với mỗi vị trí \(i\) trong T, \(T^{(i)}\) là chuỗi gồm \(i\) ký tự đầu tiên của T. Và đặt:

• Dp[i,1]: Có bao nhiêu cách tìm thấy "w" trong \(T^{(i)}\)?
• Dp[i,2]: Có bao nhiêu cách tìm thấy "we" trong \(T^{(i)}\)?
• Dp[i,3]: Có bao nhiêu cách tìm thấy "wel" trong \(T^{(i)}\)?
• Dp[i,4]: Có bao nhiêu cách tìm thấy "welc" trong \(T^{(i)}\)?
• ...
• Dp[i,18]: Có bao nhiêu cách tìm thấy "welcome to code ja" trong \(T^{(i)}\)?
• Dp[i,19]: Có bao nhiêu cách tìm thấy "welcome to code jam" trong \(T^{(i)}\)?

Giả sử Dp[i,j] đã được tính cho mỗi \(j\), hãy xem việc tính Dp[i+1,4] dễ dàng như thế nào:

1. Nếu ký tự thứ (i+1) của T không phải là 'c', thì Dp[i+1,4] = Dp[i,4].
2. Nếu ký tự thứ (i+1) của T là 'c', thì chúng ta có thể bao gồm tất cả các chuỗi "welc" đã tìm thấy trong \(T^{(i)}\), cũng như những chuỗi "welc" kết thúc đúng tại ký tự thứ (i+1), do đó Dp[i+1,4] = Dp[i,4] + Dp[i,3].

Cuối cùng, gọi n là độ dài của văn bản T, Dp[n,19] sẽ là câu trả lời của chúng ta.

Chỉ vậy thôi. Chào mừng đến với Code Jam; và chúng tôi hy vọng bạn đã tận hưởng vòng thi này.

Lưu ý: Vì bài toán chỉ yêu cầu 4 chữ số cuối, tất cả các phép cộng nên được thực hiện theo modulo 10000.

Độ phức tạp

Gọi \(L_S\) là độ dài của chuỗi mục tiêu (19) và \(L_T\) là độ dài của chuỗi đầu vào (tối đa 500).
Độ phức tạp thời gian là \(O(L_S \times L_T)\) cho mỗi bộ test, hoàn toàn nằm trong giới hạn cho phép.

Dựa trên phân tích chính thức của Google Code Jam.