Editorial for Bedao Mini Contest 12 - MODSORT


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.

Nhận xét #1 : Điều kiện ~|a_i - a_{i+1}|~ chia hết cho ~k~ tương đương ~a_i~ và ~a_{i+1}~ đồng dư khi chia cho ~k~, vậy ta không thể thay đổi thứ tự của các phần tử nếu chúng đồng dư khi chia cho ~k~.

Nhận xét #2 : Theo thuật toán kinh điển merge sort, luôn tồn tại cách để hợp nhất ~2~ dãy không giảm thành ~1~ dãy không giảm ~(~dãy sau khi hợp nhất chứa tất cả phần tử của ~2~ dãy ban đầu và không làm thay đổi thứ tự gốc của chúng~)~

Từ ~2~ nhận xét trên, với mỗi số ~x~ thỏa mãn ~0 \leq x < k~, ta lọc ra các phần tử ~a_j~ sao cho ~a_j \equiv x \pmod{k}~ rồi kiểm tra xem liệu chúng có được xếp theo thứ tự không giảm trong dãy ~a~ ban đầu. Nếu điều kiện này đúng với mọi ~x~ ~(0 \leq x < k)~ thì đáp án là Yes, không thì đáp án là No.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.