Editorial for Bedao Regular Contest 12 - PAPALIND


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1

Ta xét mọi xâu con của ~s~ và kiểm tra đó có là một papalindrome không.

Xét một xâu con từ ~i~ đến ~j~ của ~s~, ta kiểm tra xâu con này có là một papalindrome hay không bằng cách:

  • Kiểm tra xâu con từ ~i~ đến ~j~ có đối xứng hay không. Đặt ~len~ = ~j - i + 1~, để xâu con từ ~i~ đến ~j~ đối xứng, ~s_{i+k-1} = s_{j-k+1}~ với mọi ~1 \leq k \leq len~.
  • Kiểm tra mọi vị trí chẵn của xâu con từ ~i~ đến ~j~ có giống nhau hay không, tương đương với việc ~s_{i+1} = s_{i+3} = s_{i+5} = ...~.

Độ phức tạp: ~O(n^3)~.

Subtask 2

Ý tưởng giống như Subtask 1, tuy nhiên ta thực hiện prepare để có thể kiểm tra trong ~O(1)~.

Ta có mảng ~isPalin[i][j]~ = ~0~/~1~ với ý nghĩa xâu con từ ~i~ đến ~j~ có đối xứng hay không.

  • ~isPalin[i][i]~ = ~1~.
  • ~isPalin[i][i+1]~ = ~(s_i == s_{i+1})~.
  • ~isPalin[i][j]~ = ~(isPalin[i+1][j-1]~ ~\&\&~ ~s_i == s_j)~ với ~i + 1 < j~.

Nhận thấy các vị trí ~i+1, i+3, i+5, ...~ có tính chẵn lẻ giống nhau, ta chuẩn bị hai mảng ~odd~ và ~even~ với ~odd[i][j]~ là giá trị của các vị trí lẻ trong đoạn từ ~i~ đến ~j~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau, ~even[i][j]~ là giá trị của các vị trí chẵn trong đoạn từ ~i~ đến ~j~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau.

Ta tính mảng ~odd~ như sau:

  • ~odd[i][i+1]~ = ~s_i~ nếu ~i~ lẻ, ngược lại = ~s_{i+1}~.
  • ~odd[i][j]~ = ~odd[i][j-1]~ nếu ~j~ chẵn hoặc ~odd[i][j-1] == s_j~, ngược lại = ~-1~.

Ta tính mảng ~even~ giống mảng ~odd~.

Sử dụng ba mảng ~isPalin, odd, even~ ta có thể for mọi xâu con ~i~ đến ~j~ của ~s~ và check trong O(~1~).

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

Subtask 3

Xét một xâu papalindrome ~t~ có độ dài ~2*m~, ta có:

  • ~t_1 = t_{2*m}~, ~t_2 = t_{2*m-1}~, ~t_3 = t_{2*m-2}~, ...
  • Lại có ~t_2 = t_4 = ... = t_{2*m}~ ~\Rightarrow~ ~t_1 = t_2 = ... = t_{2*m}~.

~\Rightarrow~ Xâu papalindrome độ dài chẵn là xâu có tất cả các kí tự giống nhau, có thể dễ dàng tính được.

Với xâu papalindrome độ dài lẻ, với mỗi vị trí ~i~, ta đi tính ~len_i~ là giá trị lớn nhất sao cho xâu ~s_{i-len_i+1...i+len_i-1}~ là xâu palindrome. Để tính ~len_i~, ta có thể dùng thuật toán Manacher hoặc Binary Search kết hợp Hashing.

Ta sử dụng thuật toán RMQ để tính hai mảng ~odd~ và ~even~ với ~odd[i][j]~ là giá trị ở vị trí lẻ trong đoạn ~i...i+2^j-1~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau, ~even[i][j]~ là giá trị các vị trí chắn trong đoạn ~i...i+2^j-1~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau.

Chặt nhị phân tìm được vị trí ~p_1~ là vị trí chẵn nhỏ nhất ~\geq i - len_i + 1~ thỏa mãn ~l_1 = i - p_1 + 1~ thì tất cả các vị trí lẻ trong khoảng ~i - l_1 + 1 ... i + l_1 - 1~ bằng nhau, đáp án của ta cộng vào số lượng vị trí chẵn trong khoảng ~p_1...i~. Ta làm tương tự để tính ~p_2~ lẻ và tính đáp án.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.