Задача

Девочка Маша гуляла в лесу и нашла полное бинарное дерево высоты n и перестановку $p$ длины $m$ = $2^n$.

Перестановка — это последовательность длины n целых чисел от 1 до $n$, в которой все числа встречаются ровно по одному разу. Например, $[1, 3, 5, 2, 4]$, $[3,4,2,1]$, $[1,3,2]$ — перестановки, а $[2,3,2]$, $[4,3,1]$, $[0]$ — нет.

Пронумеруем m листьев этого дерева слева направо. В листе с номером $i$ записано значение $pi (1 ≤ i ≤ m)$. Например, если $n$=2, $p$=$[3,1,4,2]$, дерево будет выглядеть так:

Маша считает дерево красивым, если значения в его листьях упорядочены слева направо по возрастанию.

За одну операцию Маша может выбрать произвольную не являющуюся листом вершину дерева и поменять местами ее левого и правого сына (вместе с их поддеревьями).

Помогите Маше понять, сможет ли она за некоторое количество операций сделать дерево красивым. Если сможет, то выведите минимальное количество операций, чтобы сделать дерево красивым.

Алгоритм решения

Наше дерево мы можем представить просто в виде массива $p$. Тогда операция смены сыновей - перемещение элементов в массиве.

Разделим наш массив на группы по 2 элемента. (Это всегда получится сделать, т. к. количество элементов перестановки - это степень двойки) Получим все поддеревья с двумя сыновьями. Теперь проверяем элементы в группах: если они не идут в порядке возрастания, то сортируем их и увеличиваем счётчик операций на 1.

Теперь мы будем сравнивать группы элементов (увеличиваем размер поддеревьев). Если первый элемент первой группы больше первого элемента второй группы (сравниваем по первому элементу, т. к. он будет минимальным для каждой группы), то увеличиваем счётчик операций на один, меняем группы местами и объединяем их в одну, при этом порядок элементов в группе сохраняется.
Например, $[ [7, 8], [1, 2], [5, 6], [3, 4] ]$ - наш массив с группами, тогда при сравнении групп получим - $[ [1, 2, 7, 8], [3, 4, 5, 6] ]$.

После объединения длина групп стала равна четырём. Рекурсивно повторяем, пока количество элементов в группе не станет равно длине изначального массива.

После всех этих преобразований массив будет либо отсортированным (тогда мы выводим количество операций), либо неотсортированным (тогда выводим $-1$).

Псевдокод

Функция разделить_на_части(список):  
    Если длина(список) <= 2:  
        Вернуть [список]  
      
    первая_половина = список[:длина(списка)//2]  
    вторая_половина = список[длина(списка)//2:]  
    Вернуть разделить_на_части(первая_половина) + разделить_на_части(вторая_половина)  
  
Функция отсортировать_пары(список, счетчик):  
    Если длина(список) <= 1:  
        Вернуть список[0], счетчик  
      
    новый_список = []  
    Для i от 0 до длина(списка) - 1 с шагом 2:  
        Если список[i][0] > список[i + 1][0]:  
            новый_список.добавить(список[i + 1] + список[i])  
            счетчик += 1  
        Иначе:  
            новый_список.добавить(список[i] + список[i + 1])  
      
    Вернуть отсортировать_пары(новый_список, счетчик)  
  
Функция решить():  
    m = Ввести_целое_число()  
    список = Ввести_список_целых_чисел()  
      
    Если список == отсортировать(список):  
        Вернуть(0)  
      
    список = разделить_на_части(список)  
    счетчик = 0  
      
    Для i от 0 до длина(списка):  
        Если список[i][0] > список[i][1]:  
            список[i] = [список[i][1], список[i][0]]  
            счетчик += 1  
      
    новый_список, счетчик = отсортировать_пары(список, счетчик)  
    Если новый_список == отсортировать(новый_список):  
        Вернуть(счетчик)  
    Иначе:  
        Вернуть(-1)  
      
    Вернуться

Реализация на Python

Аннотация:  
split_p - функция рекурсивно разбивает массив на подмассивы  
p - неотсортированный массив  
first - первая половина массива  
second - вторая половина массива  
sort_p - функция сортирует список пар, где каждая пара представляет два элемента, и считает количество инверсий  
cnt - счетчик инверсий  
new_p - новый список пар, где пары отсортированы  
solve - функция решает задачу сортировки списка целых чисел, используя инверсии, и проверяет, возможно ли отсортировать список с помощью подсчета  
m - количество элементов в списке

def split_p(p):    
    if len(p) <= 2:    
        return [p]    
          
    first, second = p[:len(p)//2], p[len(p)//2:]    
    return split_p(first) + split_p(second)    
    
  
def sort_p(p, cnt):    
    if len(p) <= 1:    
        return p[0], cnt    
          
    new_p = []    
    for i in range(0, len(p) - 1, 2):    
        if p[i][0] > p[i + 1][0]:    
            new_p.append(p[i + 1] + p[i])    
            cnt += 1    
              
        else:    
            new_p.append(p[i] + p[i + 1])    
              
    return sort_p(new_p, cnt)    
    
    
def solve():    
    m = int(input())    
    p = list(map(int, input().split()))   
       
    if p == list(sorted(p)):    
        print(0)    
        return    
    
    p = split_p(p)      
    cnt = 0    
      
    for i in range(0, len(p)):    
        if p[i][0] > p[i][1]:    
            p[i] = [p[i][1], p[i][0]]    
            cnt += 1    
    
    new_p, cnt = sort_p(p, cnt)    
    if new_p == list(sorted(new_p)):    
        print(cnt)    
          
    else:    
        print(-1)    
          
    return

Олимпиадная реализация на C++

Аннотация:  
typedef - переопределение имени типа данных  
split_p - функция рекурсивно разбивает массив на подмассивы  
p - неотсортированный массив  
res - список, который накапливает пары целых чисел  
sort_p - функция сортирует список пар, где каждая пара представляет два элемента, и считает количество инверсий  
cnt - счетчик инверсий  
new_p - новый список пар, где пары отсортированы  
curr - текущая отсортированная пара  
solve - функция решает задачу сортировки списка целых чисел, используя инверсии, и проверяет, возможно ли отсортировать список с помощью подсчета  
p_sort - копия неотсортированного массива, отсортированного для проверки  
digit - текущий элемент, считываемый из ввода  
res_p - результат сортировки  
sort_res_p - отсортированный результат сортировки  
s - кортеж, содержащий отсортированный вектор и количество инверсий

typedef vector<int> vi;  
typedef vector<vector<int>> vvi;  
  
vvi split_p(vi p) {  
  if (p.size() <= 2) return {p};  
  
  vvi res;  
  for (int i = 0; i < p.size() - 1; i += 2) {  
    res.push_back({p[i], p[i + 1]});  
  }  
  return res;  
}  
  
pair<vector<int>, int> sort_p(vvi p, int cnt) {  
  if (p.size() <= 1) return {p[0], cnt};  
  
  vvi new_p;  
  for (int i = 0; i < p.size() - 1; i += 2) {  
    if (p[i][0] > p[i + 1][0]) {  
      vi curr;  
      curr.insert(curr.end(), p[i + 1].begin(), p[i + 1].end());  
      curr.insert(curr.end(), p[i].begin(), p[i].end());  
      new_p.push_back(curr);  
      cnt++;  
    }  
  
    else {  
      vi curr;  
      curr.insert(curr.end(), p[i].begin(), p[i].end());  
      curr.insert(curr.end(), p[i + 1].begin(), p[i + 1].end());  
      new_p.push_back(curr);  
    }  
  }  
  return sort_p(new_p, cnt);  
}  
  
void solve() {  
  int m;  
  std::cin >> m;  
  vi p;  
  vi p_sort;  
  
  for (int i = 0; i < m; i++) {  
    int digit;  
    cin >> digit;  
    p.push_back(digit);  
    p_sort.push_back(digit);  
  }  
  
  sort(p_sort.begin(), p_sort.end());  
  if (p == p_sort) {  
    cout << 0 << endl;  
    return;  
  }  
  
  vvi new_p;  
  new_p = split_p(p);  
  
  int cnt = 0;  
  for (int i = 0; i < new_p.size(); i++) {  
    if (new_p[i][0] > new_p[i][1]) {  
      new_p[i] = {new_p[i][1], new_p[i][0]};  
      cnt++;  
    }  
  }  
  
  vi res_p, sort_res_p;  
  pair<vector<int>, int> s = sort_p(new_p, cnt);  
  res_p = s.first;  
  sort_res_p = s.first;  
  cnt = s.second;  
  
  sort(sort_res_p.begin(), sort_res_p.end());  
  
  if (res_p == sort_res_p) {  
    cout << cnt << endl;  
  }  
  
  else {  
    cout << -1 << endl;  
  }  
  return;  
}

Продуктовая реализация на C++

Аннотация:  
split_array - функция Делит вектор целых чисел на векторы пар целых чисел  
array - неотсортированный массив  
result - пары целых чисел  
sort_array - функция сортирует список пар, где каждая пара представляет два элемента, и считает количество инверсий  
count - счетчик инверсий  
new_array - новый список пар, где пары отсортированы  
merge_array - текущая отсортированная пара  
solve - функция решает задачу сортировки списка целых чисел, используя инверсии, и проверяет, возможно ли отсортировать список с помощью подсчета  
len_array - количество элементов в списке  
array_sort - копия списка, отсортированного для проверки  
digit - текущий элемент, считываемый из ввода  
sort_result - отсортированный результат сортировки  
final_array_and_count - кортеж, содержащий отсортированный вектор и количество инверсий

std::vector<std::vector<int>> split_array(std::vector<int> array) {  
  if (array.size() <= 2) return {array};  
  
  std::vector<std::vector<int>> result;  
  for (int i = 0; i < array.size() - 1; i += 2) {  
    result.push_back({array[i], array[i + 1]});  
  }  
  
  return result;  
}  
  
std::pair<std::vector<int>, int> sort_array(std::vector<std::vector<int>> array,  
                                            int count) {  
  if (array.size() <= 1) return {array[0], count};  
  
  std::vector<std::vector<int>> new_array;  
  for (int i = 0; i < array.size() - 1; i += 2) {  
    if (array[i][0] > array[i + 1][0]) {  
      std::vector<int> merge_array;  
      merge_array.insert(merge_array.end(), array[i + 1].begin(),  
                         array[i + 1].end());  
      merge_array.insert(merge_array.end(), array[i].begin(), array[i].end());  
      new_array.push_back(merge_array);  
      count++;  
    }  
  
    else {  
      std::vector<int> merge_array;  
      merge_array.insert(merge_array.end(), array[i].begin(), array[i].end());  
      merge_array.insert(merge_array.end(), array[i + 1].begin(),  
                         array[i + 1].end());  
      new_array.push_back(merge_array);  
    }  
  }  
  
  return sort_array(new_array, count);  
}  
  
void solve() {  
  int len_array;  
  std::cin >> len_array;  
  std::vector<int> array;  
  std::vector<int> array_sort;  
  
  for (int i = 0; i < len_array; i++) {  
    int digit;  
    std::cin >> digit;  
    array.push_back(digit);  
    array_sort.push_back(digit);  
  }  
  
  std::sort(array_sort.begin(), array_sort.end());  
  if (array == array_sort) {  
    std::cout << 0 << std::endl;  
    return;  
  }  
  
  std::vector<std::vector<int>> new_array;  
  new_array = split_array(array);  
  
  int count = 0;  
  for (int i = 0; i < new_array.size(); i++) {  
    if (new_array[i][0] > new_array[i][1]) {  
      new_array[i] = {new_array[i][1], new_array[i][0]};  
      count++;  
    }  
  }  
  
  std::vector<int> result, sort_result;  
  std::pair<std::vector<int>, int> final_array_and_count =  
      sort_array(new_array, count);  
  result = final_array_and_count.first;  
  sort_result = final_array_and_count.first;  
  count = final_array_and_count.second;  
  
  std::sort(sort_result.begin(), sort_result.end());  
  
  if (result == sort_result) {  
    std::cout << count << std::endl;  
  }  
  
  else {  
    std::cout << -1 << std::endl;  
  }  
  return;  
}