HackerRank Inverse RMQ Problem Solution

HackerRank Inverse RMQ Problem Solution

Posted on By Yashwant Parihar No Comments on 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 ʼ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 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.

HackerRank Inverse RMQ Problem Solution
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 Tags:, , , , , ,

Related Posts

HackerRank LCS Returns Problem Solution HackerRank LCS Returns Problem Solution c
HackerRank P-sequences Problem Solution HackerRank P-sequences Problem Solution c
Add an Custom Snippet for Javascript in Visual Studio Code developer guide
HackerRank Requirement Problem Solution HackerRank Requirement Problem Solution c
HackerRank Largest Permutation Problem Solution HackerRank Largest Permutation Problem Solution c
HackerRank Common Child Problem Solution HackerRank Common Child Problem Solution c

Leave a Reply

Your email address will not be published. Required fields are marked *