HackerRank Inverse RMQ Problem Solution Yashwant Parihar, June 19, 2023August 1, 2024 In this post, we will solve HackerRank Inverse RMQ Problem Solution. Range Minimum Query is a well-known problem: given an array of distinct integers with size n = 2 and m queries, find the minimum element on subsegment [L₁, Ri]. One of the most efficient and famous solutions to this problem is a segment tree. A segment tree is a full binary tree with 2. n – 1 nodes where the leaves contain the values of the original array and each non-leaf node contains the minimum value of its entire subtree.Usually, a segment tree is represented as an array of integers with 2n-1 elements. The left child of the ith node is in the (2i+1)th cell, and the right child is in the (2- ¿ + 2)th cell. For example, A = [1, 1, 3, 1, 2, 3, 4] represents the following segment tree where the first number in a node describes the array Index, &, in A and the second number denotes the value stored at index i (which corresponds to the minimum value in that node’s subtree): You’ve just used ʼn distinct integers to construct your first segment tree and saved it as an array, A. of 2n-1 values. Unfortunately, some evil guy came and either shuffled or altered the elements in your array. Can you use the altered data to restore the original array? If no, print NO on a new line; otherwise, print two lines where the first line contains the word YES and the second line contains 2. n-1 space-separated integers denoting the array’s original values. If there are several possible original arrays, print the lexicographically smallest one.Input FormatThe first line contains a single integer, n. denoting the size of the array. The second line contains 2. n-1 space-separated integers denoting the shuffled values of the segment tree. Sample Input 0 4 3 1 3 1 2 4 1 Sample Output 0 YES 1 1 3 1 2 3 4 Explanation 0This is the same segment tree shown in the Problem Statement above. Sample Input 1 2 1 1 1 Sample Output 1 NO Explanation 1A segment tree with three nodes would consist of a root, a left child, and a right child. Because all three numbers in this array are the same and the leaves of the segment tree must be N distinct integers, it’s not possible to reconstruct the original array. HackerRank Inverse RMQ Problem Solution Inverse RMQ C Solution #include <assert.h> #include <stddef.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> char* readline(); char** split_string(char*); int* canTree(int n, int* arr){ int logn = 0; while(n >> logn > 1){ logn++; } int sortarr[2*n - 1]; for(int i = 0; i < 2*n - 1; i++){ sortarr[i] = arr[i]; int curr = i; int inplace = 0; while(curr > 0 && inplace == 0){ int next = (curr - 1)/2; if(sortarr[next] < sortarr[curr]){ int temp = sortarr[curr]; sortarr[curr] = sortarr[next]; sortarr[next] = temp; curr = next; } else{ inplace = 1; } } } for(int i = 0; i < 2*n - 1; i++){ int temp = sortarr[0]; sortarr[0] = sortarr[2*n - i - 2]; sortarr[2*n - i - 2] = temp; int curr = 0; int reheaped = 0; while(reheaped == 0){ int next = curr; if(2*curr + 1 < 2*n - i - 2 && sortarr[2*curr + 1] > sortarr[next]){ next = 2*curr + 1; } if(2*curr + 2 < 2*n - i - 2 && sortarr[2*curr + 2] > sortarr[next]){ next = 2*curr + 2; } if(next != curr){ temp = sortarr[curr]; sortarr[curr] = sortarr[next]; sortarr[next] = temp; curr = next; } else{ reheaped = 1; } } } int *levellist[logn + 1]; int numatlevel[logn + 1]; int **numopen[logn + 1]; for(int i = 0; i <= logn; i++){ levellist[i] = malloc((1<<i)*sizeof(int)); assert(levellist[i] != NULL); for(int j = 0; j < 1<<i; j++){ levellist[i][j] = INT_MIN; } numopen[i] = malloc((1<<i)*sizeof(int*)); assert(numopen[i] != NULL); for(int j = 0; j <= (1<<i); j++){ numopen[i][j] = malloc((logn + 1)*sizeof(int)); assert(numopen[i][j] != NULL); for(int k = 0; k <= logn; k++){ numopen[i][j][k] = 0; } } numatlevel[i] = 0; } numopen[0][0][0] = 1; int index = 0; while(index < 2*n - 1){ int currval = sortarr[index]; int currindex = index; while(index < 2*n - 1 && sortarr[index] == currval){ index++; } int numreps = index - currindex; int level = (logn + 1) - numreps; int pos = 0; if(level < 0 || numopen[0][0][level] == 0){ return NULL; } for(int i = 0; i < level; i++){ assert(numopen[i][pos][level] > 0); numopen[i][pos][level] -= 1; for(int j = level + 1; j <= logn; j++){ numopen[i][pos][j] += 1; } if(i + 1 < level && numopen[i + 1][2*pos][level] > 0){ pos = 2*pos; } else{ pos = 2*pos + 1; } } for(int i = level; i <= logn; i++){ levellist[i][pos] = currval; for(int j = i + 1; j <= logn; j++){ numopen[i][pos][j] += 1; } pos = 2*pos; } } int *toreturn = malloc((2*n - 1)*sizeof(int)); assert(toreturn != NULL); index = 0; for(int i = 0; i <= logn; i++){ for(int j = 0; j < (1<<i); j++){ toreturn[index] = levellist[i][j]; index++; } } return toreturn; } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); char* n_endptr; char* n_str = readline(); int n = strtol(n_str, &n_endptr, 10); if(n_endptr == n_str || *n_endptr != '\0'){ exit(EXIT_FAILURE);} char** vals_str = split_string(readline()); int *treelist = malloc((2*n - 1) * sizeof(int)); for(int i = 0; i < 2*n - 1; i++){ char* currval_str = vals_str[i]; char* currval_endptr; int currval = strtol(currval_str, &currval_endptr, 10); if(currval_endptr == currval_str || *currval_endptr != '\0'){ exit(EXIT_FAILURE);} treelist[i] = currval; } int* arrlist = canTree(n, treelist); if(arrlist == NULL){ fprintf(fptr, "NO"); } else{ fprintf(fptr, "YES\n"); for(int i = 0; i < 2*n - 2; i++){ fprintf(fptr, "%d ", arrlist[i]); } fprintf(fptr, "%d", arrlist[2*n - 2]); } return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; } size_t new_length = alloc_length << 1; data = realloc(data, new_length); if (!data) { break; } alloc_length = new_length; } if (data[data_length - 1] == '\n') { data[data_length - 1] = '\0'; } if(data[data_length - 1] != '\0'){ data_length++; data = realloc(data, data_length); data[data_length - 1] = '\0'; } data = realloc(data, data_length); return data; } char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits; } Inverse RMQ C++ Solution #include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef pair<long long, int> lli; typedef long long ll; typedef unsigned long long ull; #define For(i,a,b) for(int i=a;i<=b;i++) #define Rep(i,a,b) for(int i=a;i>=b;i--) #define REP(i, n) for(int i = 0; i < n; i++) #define FOR(i, f) for(__typeof(f.begin()) i = f.begin(); i != f.end(); i++) #define fi first #define se second #define pb push_back #define sz(s) int(s.size()) #define reset(f, x) memset(f, x, sizeof(f)) #define all(x) x.begin(), x.end() #define two(x) (1LL << x) #define getbit(x, i) ((x >> (i-1)) & 1LL) #define onbit(x, i) (x | (1LL << (i-1))) #define offbit(x, i) (x & ~(1 << (i-1))) const int N = (1 << 18) + 10; int t[4*N], a[4*N], n, m; int b[N], cnt[N], nn, vmax; bool was[4*N]; int ans[4*N]; vector<ii> p; set<int> num[50]; bool cmp(ii a, ii b) { if (a.se != b.se) return a.se > b.se; return a.fi < b.fi; } bool check(int i) { if (2*i+1 >= m) return true; if (ans[i] != min(ans[i*2+1], ans[i*2+2])) return false; return (check(i*2+1) & check(i*2+2)); } bool solve() { REP(i, m) if (!was[i]) { int h = vmax-trunc(log(i+1)/log(2)); if (num[h].empty()) return false; int now = i; auto it = num[h].begin(); if (i) it = num[h].upper_bound(ans[(i-1)/2]); if (it == num[h].end()) return false; For(cnt, 1, h) { ans[now] = *it; was[now] = true; now = now*2 + 1; } num[h].erase(it); } return true; } int main() { //freopen("in.txt","r",stdin); cin >> n; m = 2*n-1; For(i, 1, m) cin >> a[i]; sort(a+1, a+m+1); a[0] = a[1] - 1; vmax = trunc(log(n) / log(2)) + 1; For(i, 1, m) if (a[i] != a[i-1]) p.pb(ii(a[i], 1)); else p.back().se++; sort(all(p), cmp); REP(i, sz(p)) if (p[i].se <= vmax) num[p[i].se].insert(p[i].fi); // FOR(i, p) cout << i->fi << ' ' << i->se << "\n"; if (sz(p) != n) cout << "NO"; else if (!solve()) cout << "NO"; else { cout << "YES\n"; REP(i, m) cout << ans[i] << ' '; } } Inverse RMQ C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static int[] GetCounts(int n){ var arr = new int[n]; int step = 1; while(step<=n){ for(int i=0;i<n;i+=step){ arr[i]++; } step*=2; } return arr; } //sorts val and ind after values static void Sort(ref int[] val,ref int[] ind){ var zipped = val.Zip(ind, (x,y)=>new {x,y}).OrderByDescending(pair=>pair.x).ToList(); val = zipped.Select(pair=>pair.x).ToArray(); ind = zipped.Select(pair=>pair.y).ToArray(); } static void Recursion(int[] res, int[] nums, int index, int a, int b, int n){ if (b >= n) { Console.WriteLine("YES"); Console.WriteLine(String.Join(" ", res)); } else { for (int i = 0; i < b - a; i++) { if (res[a + i] > nums[index + i]) { int j = index + i + 1; while (j < index + b - a && res[a + i] > nums[j]) { j++; } if (j == index + b - a) { Console.WriteLine("NO"); return; } else { int temp = nums[j]; for (int z = j; z >index+i; z--) { nums[z] = nums[z-1]; } nums[index + i] = temp; } } } for (int i = 0; i < b - a; i++) { if (b + 2 * i == 4018) { var cur = new int[b - a]; for(int q = 0; q < b-a; q++) { cur[q] = res[a + q]; } } if (b + 2 * i + 1 == 4018) { var cur = new int[b - a]; for (int q = 0; q < b - a; q++) { cur[q] = nums[index+q]; } } res[b + 2 * i] = res[a + i]; res[b + 2 * i + 1] = nums[index + i]; } Recursion(res, nums, index + b - a, b, b + 2 * (b - a), n); } } static void Solve(int n, int[] arr){ var idealcounts = GetCounts(n).OrderByDescending(t=>t).ToArray(); int N=arr.Length; Array.Sort(arr); var nums = new int[n]; var counts = new int[n]; int ind1=0,ind2=0; while(ind1<n){ nums[ind1]=arr[ind2]; while(ind2<N && nums[ind1]==arr[ind2]){ counts[ind1]++; ind2++; } ind1++; if(ind2==N && ind1!=n){ Console.WriteLine("NO"); return; } } Sort(ref counts, ref nums); for(int i=0;i<n;i++){ if(counts[i]!=idealcounts[i]){ Console.WriteLine("NO"); return; } } int[] res = new int[N]; int step =1; for(int i=0;i<n;){ res[i]=nums[0]; i+=step; step*=2; } Recursion(res, nums, 1, 0, 1, n); } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] nums = Console.ReadLine().Split(' '); int[] arr = Array.ConvertAll(nums, t=>Convert.ToInt32(t)); Solve(n,arr); } } Inverse RMQ Java Solution import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.HashMap; import java.io.IOException; import java.io.Reader; import java.io.InputStreamReader; import java.util.TreeSet; import java.util.TreeMap; import java.util.StringTokenizer; import java.util.Map; import java.util.Map.Entry; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.BufferedReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Solution { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); OutputWriter out = new OutputWriter(outputStream); InversedRMQ solver = new InversedRMQ(); solver.solve(1, in, out); out.close(); } static class InversedRMQ { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int k = 2 * n - 1; final Map<Integer, Integer> count = new TreeMap<>(); for (int i = 0; i < k; i++) { int x = in.readInt(); count.put(x, count.getOrDefault(x, 0) + 1); } final TreeSet<Integer>[] types = new TreeSet[k + 1]; final Map<Integer, Integer> result = new HashMap<>(); for (int i = 0; i < types.length; i++) { types[i] = new TreeSet<>(); } int log = 0, n_ = n; while (n_ > 0) { n_ >>= 1; log++; } types[log].add(1); for (Map.Entry<Integer, Integer> entry : count.entrySet()) { if (types[entry.getValue()].isEmpty()) { out.printLine("NO"); return; } int wh = types[entry.getValue()].pollFirst(); result.put(entry.getKey(), wh); for (int i = 0; i < entry.getValue() - 1; i++) { types[entry.getValue() - i - 1].add(wh * 2 + 1); wh <<= 1; } } final int[] ans = new int[k + 1]; for (Map.Entry<Integer, Integer> entry : result.entrySet()) { int wh = entry.getValue(), value = entry.getKey(); while (wh <= k) { ans[wh] = value; wh <<= 1; } } out.printLine("YES"); for (int i = 1; i <= k; i++) { out.print(ans[i], ' '); } out.printLine(); } } static class OutputWriter { private PrintWriter writer; public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); } public OutputWriter(OutputStream stream) { this(new OutputStreamWriter(stream)); } public void print(Object... args) { for (Object arg : args) { writer.print(arg); } } public void printLine(Object... args) { print(args); writer.println(); } void close() { writer.close(); } } static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(Reader reader) { this.reader = new BufferedReader(reader); } public InputReader(InputStream stream) { this(new InputStreamReader(stream)); } public String nextLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public String readWord() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(nextLine()); } return tokenizer.nextToken(); } public int readInt() { return Integer.parseInt(readWord()); } } } Inverse RMQ JavaScript Solution var VALUE = 0; var LEFT = 1; var RIGHT = 2; var UP = 3; var COLOR = 4; var WIDTH = 5; var RED = 0; var BLACK = 1; var MIN_SIZE = 4; var RBTree = function (cmp) { if (cmp === undefined) { cmp = function (a, b) { if (a < b) { return -1; } if (a > b) { return 1; } return 0; }; } this.cmp = cmp; this.nodes = []; this.size = 0; // total used and unused nodes this.next = null; //head of linked list of unused nodes this.count = 0; // number of used nodes this.root = null //the root index node }; RBTree.prototype.resize = function (new_size) { if (new_size > this.size) { var min_i = this.nodes.length; var i = new_size * WIDTH; var next = this.next; this.nodes.length = i; while (i > min_i) { i -= WIDTH; this.nodes[i] = next; next = i; } this.next = next; this.size = new_size; } else { } } RBTree.prototype.insert = function (x) { if (this.count >= this.size) { if (this.size < MIN_SIZE) { this.resize(MIN_SIZE); } else { this.resize(this.size * 2); } } var idx = this.next; this.next = this.nodes[idx]; this.nodes[idx + VALUE] = x; this.nodes[idx + LEFT] = null; this.nodes[idx + RIGHT] = null; this.nodes[idx + COLOR] = RED; this.count++; if (this.root === null) { this.nodes[idx + UP] = null; this.root = idx; } else { var parent = this.root; while (true) { if (this.cmp(x, this.nodes[parent + VALUE]) < 0) { var leaf = this.nodes[parent + LEFT]; if (leaf == null) { this.nodes[parent + LEFT] = idx; this.nodes[idx + UP] = parent; break; } else { parent = leaf; } } else { var leaf = this.nodes[parent + RIGHT]; if (leaf == null) { this.nodes[parent + RIGHT] = idx; this.nodes[idx + UP] = parent; break; } else { parent = leaf; } } } } this.fix_coloring_near(idx); }; RBTree.prototype.fix_coloring_near = function (idx) { var parent = this.nodes[idx + UP]; if (parent == null) { this.nodes[idx + COLOR] = BLACK; } else if (this.nodes[parent + COLOR] == RED) { var gramps = this.nodes[parent + UP]; var uncle = gramps; var g_dir; if (this.nodes[gramps + LEFT] == parent) { g_dir = LEFT; uncle = this.nodes[gramps + RIGHT]; } else { g_dir = RIGHT; uncle = this.nodes[gramps + LEFT]; } var uncle_color = BLACK; if (uncle !== null) { uncle_color = this.nodes[uncle + COLOR]; } if (uncle_color == RED) { this.nodes[uncle + COLOR] = BLACK; this.nodes[parent + COLOR] = BLACK; this.nodes[gramps + COLOR] = RED; this.fix_coloring_near(gramps); } else { if (this.nodes[parent + g_dir] !== idx) { var p_dir = LEFT + RIGHT - g_dir; var child = this.nodes[idx + g_dir]; this.nodes[parent + p_dir] = child; if (child !== null) { this.nodes[child + UP] = parent; } this.nodes[idx + g_dir] = parent; this.nodes[parent + UP] = idx; this.nodes[gramps + g_dir] = idx; this.nodes[idx + UP] = gramps; idx = parent; parent = this.nodes[parent + UP]; } this.nodes[gramps + COLOR] = RED; this.nodes[parent + COLOR] = BLACK; var c_dir = LEFT + RIGHT - g_dir; var child = this.nodes[parent + c_dir]; this.nodes[gramps + g_dir] = child; if (child !== null) { this.nodes[child + UP] = gramps; } var ggramps = this.nodes[gramps + UP]; if (ggramps === null) { this.nodes[parent + UP] = null; this.root = parent; } else { if (this.nodes[ggramps + LEFT] === gramps) { this.nodes[ggramps + LEFT] = parent; } else { this.nodes[ggramps + RIGHT] = parent; } this.nodes[parent + UP] = ggramps; } this.nodes[parent + c_dir] = gramps; this.nodes[gramps + UP] = parent; } } }; RBTree.prototype.remove = function (idx) { if (this.nodes[idx + LEFT] !== null && this.nodes[idx + RIGHT] !== null) { var single_parent = this.nodes[idx + RIGHT]; while (this.nodes[single_parent + LEFT] !== null) { single_parent = this.nodes[single_parent + LEFT]; } this.nodes[idx + VALUE] = this.nodes[single_parent + VALUE]; idx = single_parent; } var parent = this.nodes[idx + UP]; if (this.nodes[idx + COLOR] === RED) { if (this.nodes[parent + LEFT] === idx) { this.nodes[parent + LEFT] = null; } else { this.nodes[parent + RIGHT] = null; } } else { var child = this.nodes[idx + LEFT]; if (child === null) { child = this.nodes[idx + RIGHT]; } if (child !== null) { this.nodes[child + COLOR] = BLACK; if (parent === null) { this.nodes[child + UP] = null; this.root = child; } else { if (this.nodes[parent + LEFT] === idx) { this.nodes[parent + LEFT] = child; } else { this.nodes[parent + RIGHT] = child; } this.nodes[child + UP] = parent; } } else { if (parent === null) { this.root = null; } else { if (this.nodes[parent + LEFT] === idx) { this.nodes[parent + LEFT] = null; this.fix_short_branch(parent, LEFT); } else { this.nodes[parent + RIGHT] = null; this.fix_short_branch(parent, RIGHT); } } } } this.nodes[idx] = this.next; this.next = idx; this.count--; }; RBTree.prototype.fix_short_branch = function (idx, short_dir) { var long_dir = LEFT + RIGHT - short_dir; var short_child = this.nodes[idx + short_dir]; var long_child = this.nodes[idx + long_dir]; if (this.nodes[long_child + COLOR] === RED) { this.nodes[long_child + COLOR] = BLACK; this.nodes[idx + COLOR] = RED; var kid = this.nodes[long_child + short_dir]; var gramps = this.nodes[idx + UP]; if (gramps === null) { this.root = long_child; } else { if (this.nodes[gramps + LEFT] === idx) { this.nodes[gramps + LEFT] = long_child; } else { this.nodes[gramps + RIGHT] = long_child; } } this.nodes[long_child + UP] = gramps; this.nodes[long_child + short_dir] = idx; this.nodes[idx + UP] = long_child; this.nodes[idx + long_dir] = kid; this.nodes[kid + UP] = idx; long_child = kid; } var long_long = this.nodes[long_child + long_dir]; var long_short = this.nodes[long_child + short_dir]; var long_long_color = BLACK; if (long_long !== null && this.nodes[long_long + COLOR] === RED) { long_long_color = RED; } var long_short_color = BLACK; if (long_short !== null && this.nodes[long_short + COLOR] === RED) { long_short_color = RED; } if (this.nodes[idx + COLOR] === BLACK && long_long_color === BLACK && long_short_color === BLACK) { this.nodes[long_child + COLOR] = RED; var gramps = this.nodes[idx + UP]; if (gramps === null) { } else { if (this.nodes[gramps + LEFT] === idx) { this.fix_short_branch(gramps, LEFT); } else { this.fix_short_branch(gramps, RIGHT); } } } else if (this.nodes[idx + COLOR] === RED && long_long_color === BLACK && long_short_color === BLACK) { this.nodes[long_child + COLOR] = RED; this.nodes[idx + COLOR] = BLACK; } else { if (long_long_color === BLACK) { this.nodes[long_child + COLOR] = RED; this.nodes[long_short + COLOR] = BLACK; var kid = this.nodes[long_short + long_dir]; if (kid === null) { this.nodes[long_child + short_dir] = null; } else { this.nodes[long_child + short_dir] = kid; this.nodes[kid + UP] = long_child; } this.nodes[long_short + long_dir] = long_child; this.nodes[long_child + UP] = long_short; this.nodes[idx + long_dir] = long_short; this.nodes[long_short + UP] = idx; long_long = long_child; long_child = long_short; } this.nodes[long_child + COLOR] = this.nodes[idx + COLOR]; this.nodes[idx + COLOR] = BLACK; this.nodes[long_long + COLOR] = BLACK; var gramps = this.nodes[idx + UP]; var kid = this.nodes[long_child + short_dir]; if (gramps === null) { this.root = long_child; } else { if (this.nodes[gramps + LEFT] === idx) { this.nodes[gramps + LEFT] = long_child; } else { this.nodes[gramps + RIGHT] = long_child; } } this.nodes[long_child + UP] = gramps; this.nodes[long_child + short_dir] = idx; this.nodes[idx + UP] = long_child; if (kid === null) { this.nodes[idx + long_dir] = null; } else { this.nodes[idx + long_dir] = kid; this.nodes[kid + UP] = idx; } } }; RBTree.prototype.pop_min_over_x = function (x) { var best_idx = null; var best_value; var idx = this.root; while (idx !== null) { var value = this.nodes[idx + VALUE]; if (this.cmp(value, x) > 0) { best_idx = idx; best_value = value; idx = this.nodes[idx + LEFT]; } else { idx = this.nodes[idx + RIGHT]; } } if (best_idx !== null) { this.remove(best_idx); } return best_value; } var offset = 20000000000; function processData(input) { var lines = input.split('\n'); var n = Number(lines.shift()); var nodes = lines.shift().split(' '); var counts = nodes.reduce((acc, i) => { if (acc[i] === undefined) { acc[i] = 1; } else { acc[i]++; } return acc; }, {}); var levels = {}; var max_level = 0; var uniq_count = 0; for (var a in counts) { if (counts.hasOwnProperty(a)) { let level = counts[a]; if (levels[level] === undefined) { levels[level] = new RBTree(); levels[level].insert(Number(a)); } else { levels[level].insert(Number(a)); } uniq_count++; if (max_level < level) { max_level = level; } } } var level = max_level; if (uniq_count == n && Math.pow(2, level - 1) == n && nodes.length == (2 * n - 1)) { var tree = new Array(nodes.length); var good = true; var cur_level = levels[level]; tree[0] = cur_level.nodes[cur_level.root + VALUE]; counts[tree[0]]--; var p = 0; var i = 1; while (i < nodes.length) { var parent = tree[p]; p++; if (level > counts[parent]) { level = counts[parent]; cur_level = levels[level]; } tree[i] = parent; counts[parent]--; i++; var val = cur_level.pop_min_over_x(parent); if (val === undefined) { good = false; break; } else { tree[i] = val; counts[val]--; i++; } } if (good) { console.log('YES'); console.log(tree.join(' ')); } else { console.log('NO'); } } else { console.log('NO'); } } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); }); Inverse RMQ Python Solution import sys from bisect import bisect_right def z(a, b): B = sorted(b) r = [] for i in range(len(a)): ind = bisect_right(B, a[i]) r += [a[i], B[ind]] del B[ind] #print(a, b, r) return r n = int(input()) nl = 0 x = n while x: nl += 1 x >>= 1 a = list(map(int,input().split())) occ = {} for e in a: if not e in occ: occ[e] = 0 occ[e] += 1 cnt_occ = {} for i, v in occ.items(): if not v in cnt_occ: cnt_occ[v] = 0 cnt_occ[v] += 1 for i in range(1, nl): if not i in cnt_occ or cnt_occ[i] != (1 << (nl - 1 - i)): print('NO') sys.exit(0) ah = [[] for _ in range(nl + 2)] for i, v in occ.items(): ah[v].append(i) sofar = ah[nl] res = list(sofar) for i in range(1, nl): sofar = z(sofar, ah[nl - i]) res += sofar print('YES') print(' '.join(map(str,res))) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython