Editorial for Bedan Contest #05 - F - Đảo ngược


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.

Authors: flo

Cách giải

Hint
  • Với mỗi i thỏa mãn 1 \le i \le n, ta sẽ tìm cách để đảo ngược sao cho a_i = b_i. Khi đó thì tại mỗi vị trí i, các phần tử từ 1 đến i-1 rõ ràng đã thỏa mãn đề bài.
Solution
  • Từ nhận xét trên, với mỗi vị trí i thỏa mãn 1 \le i \le n, ta sẽ tìm vị trí j thỏa mãn a_j = b_i (i \le j \le n) và đảo ngược đoạn [i, j] của dãy a. Khi đó, a_i = a_ja_j = b_i nên a_i = b_i. Bởi thao tác này chỉ được áp dụng tối đa 1 lần lên các phần tử nên tổng số thao tác sẽ không vượt quá n.
  • Độ phức tạp của ý tưởng trên là O(n^2), việc đảo ngược đoạn con cũng tốn độ phức tạp là O(n) nhé.
  • Sự thật là bài này mình lấy ý tưởng từ bài CSES - Reversal Sorting nên đừng thắc mắc tại sao nó lại khá giống nhau.


Comments

There are no comments at the moment.