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

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

View Solution →

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element

View Solution →

Jesse and Cookies

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with: sweetness Least sweet cookie 2nd least sweet cookie). He repeats this procedure until all the cookies in his collection have a sweetness > = K. You are given Jesse's cookies. Print t

View Solution →

Find the Running Median

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then: If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set { 1, 2, 3 } , 2 is the median.

View Solution →

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

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

Queries with Fixed Length

QHEAP1

Jesse and Cookies

Find the Running Median

Minimum Average Waiting Time

Merging Communities