Задача

Поликарпу недавно подарили перестановку $A[1…n]$ длины $n$. Поликарпу деревья нравятся больше, чем перестановки, поэтому он хочет превратить перестановку $A$ в корневое бинарное дерево. Массив различных целых чисел он превращает в дерево следующим образом:

• Максимальный элемент массива становится корнем дерева;

• Все элементы слева от максимума — образуют левое поддерево (которое строится по тем же правилам, но применяемым для левого участка массива), но если слева от максимума элементов нет, то у корня нет левого сына;

• Все элементы справа от максимума — образуют правое поддерево (которое строится по тем же правилам, но применяемым для правого участка массива), но если справа от максимума элементов нет, то у корня нет правого сына.

Например, если он строит дерево по перестановке $A$ = $[3,5,2,1,4]$, то корнем будет элемент $A[2]$ = 5, левым поддеревом будет дерево, которое будет построено для подмассива $A[1…1]$ = $[3]$, а правым — для подмассива $A[3…5]$ = $[2,1,4]$. В итоге будет построено следующее дерево: 

Другой пример: пусть перестановка имеет вид $A$=$[1,3,2,7,5,6,4]$. В этом случае дерево выглядит так:

Обозначим за $d[v]$ глубину вершины $A[v]$, то есть количество ребер на пути от корня до вершины с номером $A[v]$. Заметьте, что глубина корня равна нулю. По заданной перестановке $A$ для каждой вершины найдем значение $d[v]$.

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

Будем рекурсивно строить дерево: первый этап находим корень/максимум и удаляем его из текущего массива. Далее делим массив на левую и правую части. Если длина левой части больше нуля, тогда связываем корень с максимумом левой части, продолжаем строить дерево от левой части. Аналогично поступаем с правой частью.

После построения дерева, необходимо найти глубины вершин. Искать их будем поиском в ширину. Создадим массив глубин. По умолчанию глубина корня дерева - нуль, а глубина остальных вершин - $число~~вершин~~дерева + 1$.

Для каждой вершины графа: если $глубина~~вершины < глубина~~её~~соседа$, тогда $глубина~~соседа = глубина~вершины + 1$.

Ответ - результат вычислений в нужном порядке.

Псевдокод

Функция построить_дерево(массив, дерево):  
    корень = максимальный элемент(массив)  
    индекс_корня = индекс(корень в массиве)  
    удалить(корень из массива)  
  
    левая_часть = массив[:индекс_корня]  
    правая_часть = массив[индекс_корня+1:]  
  
    Если длина(левая_часть) > 0:  
        добавить(максимум(левая_часть)) в дерево[корень]  
        построить_дерево(левая_часть, дерево)  
  
    Если длина(правая_часть) > 0:  
        добавить(максимум(правая_часть)) в дерево[корень]  
        построить_дерево(правая_часть, дерево)  
  
    Вернуть дерево  
  
Функция обход_в_ширину(граф, старт):  
    глубины = [бесконечность] * (длина(граф) + 1)  
    глубины[старт] = 0  
      
    очередь = очередь()  
    добавить(старт) в очередь  
  
    Пока очередь не пуста:  
        узел = извлечь(первый элемент из очереди)  
        Для каждого соседа в граф[узел]:  
            Если глубины[сосед] > глубины[узел] + 1:  
                глубины[сосед] = глубины[узел] + 1  
                добавить(сосед) в очередь  
  
    Вернуть глубины  
  
Функция решить():  
    n = Ввести_целое_число()  
    массив = Ввести_список_целых_чисел()  
  
    старт = максимальный элемент(массив)  
  
    дерево = словарь()  
    Для каждого элемента i в массиве:  
        дерево[i] = []  
  
    построить_дерево(массив, дерево)  
    глубины = обход_в_ширину(дерево, старт)  
  
    Для каждого элемента i в дереве:  
        Вернуть(глубины[i], без перехода на новую строку)  
    Вернуться

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

Аннотация:  
build_tree - функция рекурсивно строит дерево, используя максимальный элемент массива в качестве корня и деля массив на левую и правую части  
arr - текущий массив для построения дерева  
tree - словарь, представляющий дерево, где ключи — это узлы, а значения — списки детей  
root - максимальный элемент текущего массива, который будет использоваться как корень дерева  
index_root - индекс корня в массиве  
left - элементы массива до индекса корня  
right - элементы массива после индекса корня  
bfs - функция выполняет поиск в ширину для нахождения кратчайших расстояний от стартовой вершины до всех остальных вершин графа  
graph - словарь смежности, представляющий граф  
start - Стартовая вершина для BFS  
deeps - список, где индекс представляет вершину, а значение — кратчайшее расстояние до этой вершины  
queue - очередь для BFS  
solve - функция для считывания входных данных, построения дерева, выполнения BFS и вывода глубин  
n - количество элементов в массиве

def build_tree(arr: list, tree):    
    root = max(arr)    
    index_root = arr.index(root)    
    arr.remove(root)    
    
    left = arr[:index_root]    
    right = arr[index_root:]    
    
    if len(left) > 0:    
        tree[root].append(max(left))    
        build_tree(left, tree)    
    
    if len(right) > 0:    
        tree[root].append(max(right))    
        build_tree(right, tree)    
    
    return tree    
    
    
def bfs(graph, start):    
    deeps = [math.inf] * (len(graph) + 1)    
    deeps[start] = 0  
        
    queue = deque()    
    queue.append(start)    
    
    while queue:    
        node = queue.popleft()    
        for neighbour in graph[node]:    
            if deeps[neighbour] > deeps[node] + 1:    
                deeps[neighbour] = deeps[node] + 1    
                queue.append(neighbour)    
    
    return deeps    
    
    
def solve():    
    n = int(input())    
    
    arr = list(map(int, input().split()))    
    
    start = max(arr)    
    
    tree = {}    
    for i in arr:    
        tree[i] = []    
    
    build_tree(arr, tree)    
    deeps = bfs(tree, start)    
    
    for i in tree:    
        print(deeps[i], end=' ')    
    print()    
    return

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

Аннотация:  
typedef - переопределение имени типа данных  
build_tree - функция рекурсивно строит дерево, используя максимальный элемент массива в качестве корня и деля массив на левую и правую части  
arr - текущий массив для построения дерева  
tree - словарь, представляющий дерево, где ключи — это узлы, а значения — списки детей  
root - максимальный элемент текущего массива, который будет использоваться как корень дерева  
itr - итератор, указывающий на корень дерева  
i_root - индекс корня в массиве  
l - элементы массива до индекса корня  
r - элементы массива после индекса корня  
new_root - новый корень для поддерева  
bfs - функция выполняет поиск в ширину для нахождения кратчайших расстояний от стартовой вершины до всех остальных вершин графа  
graph - словарь смежности, представляющий граф  
start - Стартовая вершина для BFS  
d - список, где индекс представляет вершину, а значение — кратчайшее расстояние до этой вершины  
q - очередь для обработки вершин  
node - текущая вершина, извлеченная из очереди  
i - вершина-сосед текущей вершины  
solve - функция для считывания входных данных, построения дерева, выполнения BFS и вывода глубин  
n - количество элементов в массиве  
a - список элементов массива

typedef vector<int> vi;  
typedef map<int, vector<int>> map_ivi;  
  
map_ivi build_tree(vi arr, map_ivi& tree) {  
  int root = *max_element(arr.begin(), arr.end());  
  
  vi::iterator itr = find(arr.begin(), arr.end(), root);  
  
  int i_root = distance(array.begin(), itr);  
  arr.erase(arr.begin() + i_root);  
  
  vi l;  
  vi r;  
  
  l.insert(l.end(), arr.begin(), arr.begin() + i_root);  
  r.insert(r.end(), arr.begin() + index_root, arr.end());  
  
  if (l.size() > 0) {  
    int new_root = *max_element(l.begin(), l.end());  
    tree[root].push_back(new_root);  
    build_tree(l, tree);  
  }  
  
  if (r.size() > 0) {  
    int new_root = *max_element(r.begin(), r.end());  
    tree[root].push_back(new_root);  
    build_tree(r, tree);  
  }  
  
  return tree;  
}  
  
vi bfs(map_ivi graph, int start) {  
  vi d(graph.size() + 1, graph.size());  
  d[start] = 0;  
  queue<int> q;  
  q.push(start);  
  
  while (q.empty() != 1) {  
    int node = q.front();  
    q.pop();  
  
    for (int i : graph[node]) {  
      if (d[i] > d[node] + 1) {  
        d[i] = d[node] + 1;  
        q.push(i);  
      }  
    }  
  }  
  return deeps;  
}  
  
void solve() {  
  int n;  
  std::cin >> n;  
  
  std::vector<int> a;  
  for (int i = 0; i < n; i++) {  
    int digit;  
    std::cin >> digit;  
    a.push_back(digit);  
  }  
  
  int start = *max_element(a.begin(), a.end());  
  
  map_ivi tree;  
  for (int i : a) {  
    vi v;  
    tree[i] = v;  
  }  
  
  build_tree(a, tree);  
  
  vi d = bfs(tree, start);  
  
  for (int i : a) {  
    cout << d[i] << " ";  
  }  
  cout << endl;  
}

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

Аннотация:  
build_tree - функция рекурсивно строит дерево, используя максимальный элемент массива в качестве корня и деля массив на левую и правую части  
array - текущий массив для построения дерева  
tree - словарь, представляющий дерево, где ключи — это узлы, а значения — списки детей  
root - максимальный элемент текущего массива, который будет использоваться как корень дерева  
itr - итератор, указывающий на корень дерева  
index_root - индекс корня в массиве  
left - элементы массива до индекса корня  
right - элементы массива после индекса корня  
new_root - новый корень для поддерева  
bfs - функция выполняет поиск в ширину для нахождения кратчайших расстояний от стартовой вершины до всех остальных вершин графа  
graph - словарь смежности, представляющий граф  
start - Стартовая вершина для BFS  
deeps - список, где индекс представляет вершину, а значение — кратчайшее расстояние до этой вершины  
queue - очередь для обработки вершин  
node - текущая вершина, извлеченная из очереди  
neighbour - вершина-сосед текущей вершины  
solve - функция для считывания входных данных, построения дерева, выполнения BFS и вывода глубин  
len_permutation - количество элементов в массиве  
permutation - список элементов массива

std::map<int, std::vector<int>> build_tree(  
    std::vector<int> array, std::map<int, std::vector<int>>& tree) {  
  int root = *std::max_element(array.begin(), array.end());  
  
  std::vector<int>::iterator itr = std::find(array.begin(), array.end(), root);  
  
  int index_root = std::distance(array.begin(), itr);  
  array.erase(array.begin() + index_root);  
  
  std::vector<int> left;  
  std::vector<int> right;  
  
  left.insert(left.end(), array.begin(), array.begin() + index_root);  
  right.insert(right.end(), array.begin() + index_root, array.end());  
  
  if (left.size() > 0) {  
    int new_root = *std::max_element(left.begin(), left.end());  
    tree[root].push_back(new_root);  
    build_tree(left, tree);  
  }  
  
  if (right.size() > 0) {  
    int new_root = *std::max_element(right.begin(), right.end());  
    tree[root].push_back(new_root);  
    build_tree(right, tree);  
  }  
  return tree;  
}  
  
std::vector<int> bfs(std::map<int, std::vector<int>> graph, int start) {  
  std::vector<int> deeps(graph.size() + 1, graph.size());  
  deeps[start] = 0;  
  std::queue<int> queue;  
  queue.push(start);  
  
  while (queue.empty() != 1) {  
    int node = queue.front();  
    queue.pop();  
  
    for (int neighbour : graph[node]) {  
      if (deeps[neighbour] > deeps[node] + 1) {  
        deeps[neighbour] = deeps[node] + 1;  
        queue.push(neighbour);  
      }  
    }  
  }  
  return deeps;  
}  
  
void solve() {  
  int len_permutation;  
  std::cin >> len_permutation;  
  
  std::vector<int> permutation;  
  for (int i = 0; i < len_permutation; i++) {  
    int digit;  
    std::cin >> digit;  
    permutation.push_back(digit);  
  }  
  
  int start = *std::max_element(permutation.begin(), permutation.end());  
  
  std::map<int, std::vector<int>> tree;  
  for (int i : permutation) {  
    std::vector<int> v;  
    tree[i] = v;  
  }  
  
  build_tree(permutation, tree);  
  
  std::vector<int> deeps = bfs(tree, start);  
  
  for (int i : permutation) {  
    std::cout << deeps[i] << " ";  
  }  
  std::cout << std::endl;  
}