Editorial for Bedao Regular Contest 10 - BATTLESHIP


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

Gọi vị trí ~p~ là tốt nếu bỏ kí tự ở vị trí ~p~ thì dãy trở thành dãy đối xứng.

Thuật toán trâu ta có thể sử dụng ý tưởng đồ thị vô hướng với ~n~ đỉnh tương ứng với mỗi vị trí và với mỗi vị trí tốt ~p~, ta nối thêm ~\lfloor n/2\rfloor~ cạnh sao cho các cạnh nối 2 vị trí ~i~ và ~j~ phải bằng nhau. Cụ thể với ~1 \le p \le \lfloor \frac{n+1}{2}\rfloor~ thì ta nối cách cạnh từ ~(1 \longrightarrow p-1)~ tới ~(n \longrightarrow n-p+2)~ và các vị trí trong đoạn ~(p+1 \longrightarrow n-p+1)~ nối đối xứng với nhau. Cách nối tương tự nhưng ngược lại với ~\lfloor \frac{n+1}{2}\rfloor < p \le n~.

Sau khi nối cạnh, đơn giản ta chỉ cần gán mỗi thành phần liên thông một giá trị khác nhau. Thuật toán trên có độ phức tạp ~O(n\times m)~.

Để giảm độ phức tạp bài toán, ta cần giảm số cạnh cần nối. Ta có nhận xét rằng nếu hai vị trí tốt ~p~ và ~q~ thoả mãn ~1 \le p \le q \le \lfloor \frac{n+1}{2}\rfloor~, toàn bộ vị trí thuộc đoạn ~[p, q]~ đều tốt. Điều tương tự xảy ra với ~\lfloor \frac{n+1}{2}\rfloor < p \le q \le n~. Phần chứng minh để lại cho đọc giả.

Từ đó ta có thuật toán, với các vị trí tốt không vượt quá ~\lfloor \frac{n+1}{2}\rfloor~, tìm vị trí nhỏ nhất và lớn nhất, Ta chỉ cần quan tâm đến việc xử lý ~2~ vị trí tốt này vì sau khi xử lý thì những vị trị nằm giữa chúng đều sẽ được xử lý. Tương tự với các vị trí lớn hơn ~\lfloor \frac{n+1}{2}\rfloor~. Vậy thuật toán của ta chỉ còn ~O(n)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.