Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя krish2004

Автор krish2004, история, 2 месяца назад, По-английски

https://codeforces.me/contest/1983/problem/D

In this problem. Count inversion concept comes into play but why ?? What is the exact intuition behind it? Like why only count inversion. and what are the other type of problems where this concept is used.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

If the two arrays can be transformed to the same one, then they can also be transformed to where they are both sorted in ascending order. The number of swaps of consecutive elements to sort an array in ascending order is the number of inversions. For the sake of the explanation, let the first array have less inversions. So we sort it and still have to use more swaps to sort the second array, so if $$$inv_b - inv_a \equiv 0 \ (mod \ 2)$$$, then you can just repeatedly swap some two elements in the first array until the second array is sorted.