1490D - Permutation Transformation - CodeForces Solution

dfs and similar divide and conquer implementation *1200

Please click on ads to support us..

Python Code: 

testcases = int(input())

def depth_function(input_list, depth_list, current_depth, index_left, index_right):

    if index_left == index_right:
        return None

    max_sublist = max(input_list[index_left:index_right])
    max_index = input_list.index(max_sublist)

    depth_list[max_index] = current_depth

    depth_function(input_list, depth_list, current_depth+1, index_left, max_index)
    depth_function(input_list, depth_list, current_depth+1, max_index+1, index_right)

for i in range(testcases):
    n = int(input())
    input_2 = input().split()
    permutation = list(map(int, input_2))

    depths = [0]*n

    depth_function(permutation, depths, 0, 0, n)

    print(' '.join(map(str, depths)))

C++ Code: 

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pl;

#define N 110

ll n, a[N], dep[N];

void dfs(ll l, ll r, ll d) {
    if(l > r) return;
    ll ind = -1, mx = -1;
    for(ll i = l; i <= r; i++) if(a[i] > mx) ind = i, mx = a[i];
    dep[ind] = d;
    dfs(l, ind - 1, d + 1);
    dfs(ind + 1, r, d + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        cin >> n;
        for(ll i = 0; i < n; i++) cin >> a[i];
        dfs(0, n - 1, 0);
        for(ll i = 0; i < n; i++) cout << dep[i] << " \n"[i == n - 1];
    }
}


Comments

Submit
0 Comments
More Questions

1217. Minimum Cost to Move Chips to The Same Position
347. Top K Frequent Elements
1503. Last Moment Before All Ants Fall Out of a Plank
430. Flatten a Multilevel Doubly Linked List
1290. Convert Binary Number in a Linked List to Integer
1525. Number of Good Ways to Split a String
72. Edit Distance
563. Binary Tree Tilt
1306. Jump Game III
236. Lowest Common Ancestor of a Binary Tree
790. Domino and Tromino Tiling
878. Nth Magical Number
2099. Find Subsequence of Length K With the Largest Sum
1608A - Find Array
416. Partition Equal Subset Sum
1446. Consecutive Characters
1618A - Polycarp and Sums of Subsequences
1618B - Missing Bigram
938. Range Sum of BST
147. Insertion Sort List
310. Minimum Height Trees
2110. Number of Smooth Descent Periods of a Stock
2109. Adding Spaces to a String
2108. Find First Palindromic String in the Array
394. Decode String
902. Numbers At Most N Given Digit Set
221. Maximal Square
1200. Minimum Absolute Difference
1619B - Squares and Cubes
1619A - Square String