Inverse RMQ

Problem Statement :

Range Minimum Query is a well-known problem: given an array of distinct integers with size n=2^k and m queries, find the minimum element on subsegment [Li,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 2.n-1 elements. The left child of the ith node is in the (2.i+1)th cell, and the right child is in the (2.i+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, i, in A and the second number denotes the value stored at index i (which corresponds to the minimum value in that node's subtree):

example1_graph.png

You've just used n distinct integers to construct your first segment tree and saved it as an array, A, of 2.n-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.

Constraints
1 <= n <= 2^18
n is a power of two.
Each value in the segment tree is between -10^9 and 10^9.
Output Format

Print NO if this array could not be constructed by shuffling some segment tree. Otherwise, print YES on the first line, and 2.n-1 space-separated integers describing the respective values of the original array on the second line. If there are several possible answers, print the lexicographically smallest one.

Solution :

                            Solution in C :

In C++ :





/*
*/

//#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 1500031;

int n;
map<int, int> cnt;
map<int, int>::iterator it;

int ANS[N];
set<int> set_sz[N];
int DEP[N * 2];
set<int>::iterator it2;

void run_builder(int v, int tl, int tr,int dep)
{
	if (tl == tr)
	{
		set_sz[dep].insert(v);
		DEP[v] = dep;
		return;
	}
	int tm = tl + tr;
	tm /= 2;
	run_builder(v * 2, tl, tm, dep + 1);
	run_builder(v * 2 + 1, tm + 1, tr, dep + 1);
}

int used[N * 2];

void remove_vertex(int v)
{
	int here = DEP[v];
	//used[v] = 1;
	if (v>=n)
		set_sz[here].erase(v);
}

void add_vertex(int v, int val)
{
	DEP[v] = val;
	if (v>=n)
		set_sz[val].insert(v);
}

void DFS(int vert, int D)
{
	if (used[vert])
		return;
	remove_vertex(vert);
	add_vertex(vert, D);
	if (vert<n)
	{
		DFS(vert * 2, D + 1);
		DFS(vert * 2 + 1, D + 1);
	}
}

void run_updates(int vert)
{
	while (vert > 1 && used[vert] == 0)
	{
		remove_vertex(vert);
		used[vert] = 1;
		if (vert < n)
		{
			DFS(vert * 2, 1);
			DFS(vert * 2 + 1, 1);
		}
		vert /= 2;
	}
	if (vert == 1)
	{
		used[vert] = 1;
		remove_vertex(vert);
	}

	if (vert < n)
	{
		DFS(vert*2, 1);
		DFS(vert * 2 + 1, 1);
	}
}

int T[N * 2];

void TRACE(int v, int l, int r)
{
	if (l == r)
	{
		T[v] = ANS[v];
		return;
	}
	int m = l + r;
	m /= 2;
	TRACE(v * 2, l, m);
	TRACE(v * 2 + 1, m + 1, r);
	T[v] = min(T[v * 2], T[v * 2 + 1]);
}

int main(){
	//freopen("fabro.in","r",stdin);
	//freopen("fabro.out","w",stdout);
	//freopen("F:/in.txt", "r", stdin);
	//freopen("F:/output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);
	
	cin >> n;

	for (int i = 1; i < 2 * n; i++)
	{
		int val;
		cin >> val;
		cnt[val]++;
	}

	run_builder(1,1,n,1);

	for (it = cnt.begin(); it != cnt.end(); ++it)
	{
		int am = (*it).second;
		int val = (*it).first;
		
	//	cout << val << "%" << am << endl;

		/*for (int i = 4; i <= 7; i++)
		{
			cout << DEP[i] << " ";
		}
		cout << endl;
	*/	//cout << set_sz[1].size() << endl;

		if (set_sz[am].size() == 0)
		{
			cout << "NO" << endl;
			return 0;
		}

		it2 = set_sz[am].begin();
		int vert = (*it2);
		//cout << "$$" << vert << endl;

		run_updates(vert);
		//cout << vert << "%%" << val << endl;

		ANS[vert] = val;
	}

	TRACE(1,1,n);

	cout << "YES" << endl;
	for (int i = 1; i < n * 2; i++)
	{
		if (i>1)
			cout << " ";
		cout << T[i];
	}
	cout << endl;

	cin.get(); cin.get();
	return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n = sc.nextInt();
        int faken = 1;
        int d = 1;
        while (faken < n) {
            faken <<= 1;
            d++;
        }
        sc.nextLine();
        String[] nums = sc.nextLine().split(" ");
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int i = 0; i < 2*n-1; i++) {
            int j = Integer.parseInt(nums[i]);
            if (!hm.containsKey(j))
                hm.put(j, 0);
            hm.put(j, hm.get(j)+1);
        }
        ArrayList<TreeSet<Integer>> tms = new ArrayList<TreeSet<Integer>>();
        for (int i = 0; i <= d; i++)
            tms.add(new TreeSet<Integer>());
        for (int j : hm.keySet()) {
            if (hm.get(j) > d) {
                System.out.println("NO");
                return;
            }
            tms.get(hm.get(j)).add(j);
        }
        int arrind = 0;
        int[] tree = new int[2*n-1];
        int expectation = 1;
        for (int i = 0; i < d; i++) {
            if (tms.get(d-i).size()!=expectation) {
                System.out.println("NO");
                return;
            }
            for (int j = 0; j < expectation; j++) {
                Integer value;
                if (i==0) {
                    value = tms.get(d-i).first();
                } else {
                    value = tms.get(d-i).ceiling(tree[arrind-1]);
                }
                if (value == null) {
                    System.out.println("NO");
                    return;
                }
                tms.get(d-i).remove(value);
                int val = value;
                int temparrind = arrind;
                for (int k = 0; k < d-i; k++) {
                    tree[temparrind] = val;
                    temparrind = temparrind*2+1;
                }
                arrind += 2;
            }
            if (i > 0)
                expectation *= 2;
        }
        boolean valid = true;
        for (int i = 0; i < n-1; i++) {
            if (arrind<2*n-1||tree[i]!=tree[2*i+1]||tree[2*i+1]>=tree[2*i+2]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            System.out.println("YES");
            StringBuilder ans = new StringBuilder();
            String space = "";
            for (int i = 0; i < 2*n-1; i++) {
                ans.append(space+tree[i]);
                space = " ";
            }
            System.out.println(ans);
        } else {
            System.out.println("NO");
        }
    }
}








In C :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct mul_t {
    int el;
    int mul;
};


int cmpmul(const void* a_in, const void* b_in) {
    const struct mul_t* a = a_in;
    const struct mul_t* b = b_in;
    if (a->mul < b->mul) return 1;
    if (a->mul > b->mul) return -1;

    if (a->el < b->el) return -1;
    if (a->el > b->el) return 1;
    return 0;    
}

int cmpint(const void* a_in, const void* b_in) {
    const int* a = a_in;
    const int* b = b_in;
    if (*a < *b) return -1;
    if (*a > *b) return 1;
    return 0;
}

int main() {
    int n;
    scanf("%d\n", &n);
    int tn = n + n - 1;
    int els[tn];
    for (int i = 0; i < tn; i++) {
        scanf("%d", els + i);
    }
    struct mul_t muls[tn];
    memset(muls, 0, sizeof(muls));
    qsort(els, tn, sizeof(int), cmpint);
    int nmuls = 0;
    for (int i = 0; i < tn; i++) {
        if (nmuls == 0 || muls[nmuls-1].el != els[i]) nmuls++;
        muls[nmuls-1].el = els[i];
        muls[nmuls-1].mul++;
    }
    qsort(muls, nmuls, sizeof(struct mul_t), cmpmul);
    // Check if this is a segment tree -- multiplicities must work for that
    int depth = log2(n) + 1;
    int expel = 1;
    int mp = 0;
    for (int expmul = depth; expmul > 0; expmul--) {
        for (int i = 0; i < expel; i++) {
            if (muls[mp++].mul != expmul) {
                printf("NO\n");
                exit(0);
            }
        }
        if (expmul < depth) expel *= 2;
    }
    
    int tl = 2;
    mp = 1;
    int st[tn];
    int sp = 0;
    st[sp++] = muls[0].el;
 //   fprintf(stderr, "%d ", st[sp - 1]);
    while (mp < nmuls) {
        int tp = sp / 2;
        int emp = mp + tl;
        for (int tc = 0; tc < tl; tc += 2) {
            st[sp++] = st[tp++];
            for (int i = mp; i < emp; i++) {
                if (muls[i].el > st[(sp-1)/2]) {
                    if (i != mp) {
                        struct mul_t tmp = muls[i];
                        memmove(muls + mp + 1, muls + mp, (i - mp) * sizeof(struct mul_t));
                        muls[mp] = tmp;
                    }
                    break;
                }
            }
            st[sp++] = muls[mp++].el;
            if (st[(sp - 2)/2] > st[sp - 1]) exit(-1);
 //           fprintf(stderr, "%d %d ", st[sp - 2], st[sp - 1]);
 //           if (st[(sp - 2)/2] != st[sp - 2]) exit(-1);
        }
        tl*=2;
    }
    printf("YES\n");
    for (sp = 0; sp < tn; sp++) {
        printf("%d ", st[sp]);
    }
    printf("\n");
    return 0;
}









In Python3 :





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

# test #############    
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)))

View More Similar Problems

Mr. X and His Shots

A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M

View Solution →

Jim and the Skyscrapers

Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space

View Solution →

Palindromic Subsets

Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t

View Solution →

Counting On a Tree

Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n

View Solution →

Polynomial Division

Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficie

View Solution →

Costly Intervals

Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the

View Solution →

Our Effort to provide you the best solutions requires some appreciation

Please disable your adblocker and refresh

Inverse RMQ

Problem Statement :

Solution :

View More Similar Problems

Mr. X and His Shots

Jim and the Skyscrapers

Palindromic Subsets

Counting On a Tree

Polynomial Division

Costly Intervals