[Codeforces] 1490D. Permutation Transformation explained

Problem

1490D. Permutation Transformation

Approach

We never have to contruct the actual binary tree here.
Below is the solution based on divide and conquer.

\(depth \leftarrow [0, 0, … 0]\)
In helper function findDepth(left, right, currentDepth),

1. Find maximum value in \([left, right]\) and update depth value depth[mid] to currentDepth.
2. Call findDepth(left, mid-1, currentDepth+1) recursively.
3. Call findDepth(mid+1, right, currentDepth+1) recursively.

In main function, simply call helper function findDepth(0, n-1, 0) and print out the depth array.

Code

cpp

/**
 * author: jooncco
 * written: 2021. 3. 1. Mon. 17:58:38 [UTC+9]
 **/

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <cmath>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef deque<int> di;
typedef deque<ii> dii;

int t,n,arr[110],d[110];

void dfs(int l, int r, int cur) {

    int mx= 0, mxIdx;
    for (int i=l; i <= r; ++i) {
        if (mx < arr[i]) {
            mx= arr[i];
            mxIdx= i;
        }
    }
    d[mxIdx]= cur;

    if (mxIdx > l) dfs(l,mxIdx-1,cur+1);
    if (mxIdx < r) dfs(mxIdx+1,r,cur+1);
}

int main() {

    FAST_IO;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i=0; i < n; ++i) cin >> arr[i];
        dfs(0,n-1,0);
        for (int i=0; i < n; ++i) {
            if (i) cout << " ";
            cout << d[i];
        }
        cout << '\n';
    }
}

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private final static FastScanner sc= new FastScanner();
    private static int t,n;

    public static void main(String[] args) {
        t= sc.nextInt();
        while (t-- > 0) {
            n= sc.nextInt();
            int arr[]= new int[n];
            for (int i=0; i < n; ++i) {
                arr[i]= sc.nextInt();
            }
            int ans[]= new int[n];
            findDepth(arr, ans, 0, n-1, 0);
            StringBuilder sb= new StringBuilder();
            for (int i=0; i < n; ++i) {
                if (i > 0) sb.append(" ");
                sb.append(ans[i]);
            }
            System.out.println(sb);
        }
    }

    private static void findDepth(final int[] arr, int[] depth, int l, int r, int d) {
        if (r < 0 || l >= n) return;
        if (l == r) {
            depth[l]= d;
            return;
        }
        int maxVal= 0, idx= -1;
        for (int i=l; i <= r; ++i) {
            if (arr[i] > maxVal) {
                idx= i;
                maxVal= arr[i];
            }
        }
        depth[idx]= d;
        if (l < idx) findDepth(arr, depth, l, idx-1, d+1);
        if (r > idx) findDepth(arr, depth, idx+1, r, d+1);
    }
}

class FastScanner {
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer("");
    String next() {
        while (!st.hasMoreTokens()) {
            try {
                st= new StringTokenizer(br.readLine());
            } catch (IOException ex) {}
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
}

Complexity

• Time: \(O(n^2)\)
• Space: \(O(n)\)