Editorial for HUSC

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: Yunan

Subtask 1: Ta đơn giản kiểm tra tất cả các chuỗi con liên tiếp và tìm kết quả.

Độ phức tạp: $O(N^3)$ ~O(N^3)~

Subtask 2: Với mỗi giá trị $l$ ~l~ ( $1 \le l \le N-3$ ~1 \le l \le N-3~), ta đếm số lượng chuỗi con liên tiếp thỏa mãn điều kiện đề bài và bắt đầu từ vị trí $l$ ~l~. Với mỗi giá trị $l$ ~l~, ta tìm giá trị $r$ ~r~ ( $l+3 \le r \le N$ ~l+3 \le r \le N~) nhỏ nhất sao cho chuỗi $S_lS_{l+1}...S_{r}$ ~S_lS_{l+1}...S_{r}~ thỏa mãn yêu cầu đề bài. Khi đó, số lượng chuỗi con liên tiếp thỏa mãn điều kiện đề bài và bắt đầu từ vị trí $l$ ~l~ là $N-r+1$ ~N-r+1~.

Độ phức tạp: $O(N^2)$ ~O(N^2)~

Editorial for HUSC

Comments