HackerRank Inverse RMQ Problem Solution

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 ŉ 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 Format
The 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 0
This is the same segment tree shown in the Problem Statement above.

Sample Input 1

2
1 1 1

Sample Output 1

NO

Explanation 1
A 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.

Table of Contents

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 C cpp CSharp Hackerrank Solutions java javascript python

HackerRank Inverse RMQ Problem Solution

Inverse RMQ C Solution

Inverse RMQ C++ Solution

Inverse RMQ C Sharp Solution

Inverse RMQ Java Solution

Inverse RMQ JavaScript Solution

Inverse RMQ Python Solution

Pages

Our Tools

Engineering Subjects

Programming Tutorials

NCERT