In this HackerRank Inverse RMQ problem solution, we have given an array of distinct integers with size n = 2k and m queries. we need to find the minimum element on subsegment [Li, Ri].
Problem solution in Python.
import sys
import heapq
n = int(input())
a = list(map(int, input().split()))
freq = dict()
for i in a:
if i not in freq:
freq[i] = 0
freq[i] += 1
if len(freq) < n:
print("NO")
sys.exit()
exp_freq = 1
depth = 1
while 2**(depth - 1) < n:
depth += 1
prev = dict()
ans = [0] * (n + n - 1)
while exp_freq <= n:
v = list()
v1 = list()
for key in prev:
v1.append((key, prev[key]))
for key in freq:
if freq[key] == depth:
v.append(key)
if len(prev) == 0:
ans[0] = v[0]
prev[v[0]] = 0
freq[v[0]] -= 1
exp_freq *= 2
depth -= 1
continue
v.sort()
v1.sort()
cur = exp_freq // 2 - 1
pq = list()
j = 0
for i in v:
if i in prev:
ans[prev[i] * 2 + 1] = i
prev[i] = prev[i] * 2 + 1
freq[i] -= 1
else:
while j < len(v1):
if v1[j][0] < i:
heapq.heappush(pq, v1[j][1])
j += 1
else:
break
if len(pq) == 0:
print("NO")
sys.exit()
temp = heapq.heappop(pq)
ans[temp * 2 + 2] = i
prev[i] = temp * 2 + 2
freq[i] -= 1
exp_freq *= 2
depth -= 1
print("YES")
for i in ans:
print(i, end=" ")
Problem solution in Java.
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());
}
}
}
Problem solution in C++.
#include<bits/stdc++.h>
using namespace std;
void Q(){
cout << "NO" << endl;
exit(0);
}
set<int> Adj[(1 << 21)];
int Ar[(1 << 20)] , X , nn;
vector<int> Ans[(1 << 20)];
void build(int lvl , int V , bool F){
if(lvl == nn)return ;
set<int> :: iterator no = Adj[lvl].upper_bound(V);
if(F && (no == Adj[lvl].end() || *no <= V)){
Q();
}
if(F){
int x = *no;
Ans[lvl].push_back(x);
Adj[lvl].erase(no);
build(lvl + 1 , x , 0);
build(lvl + 1 , x , 1);
}
else {
Ans[lvl].push_back(V);
build(lvl + 1 , V , 0);
build(lvl + 1 , V , 1);
}
}
int main()
{
int n;
cin >> n;
vector<int> A(2 * n - 1);
map<int , int > mp ;
map<int , set<int> > mp1;
if(n == 1){
cin >> n;
cout << "YES\n" << n << endl;;
return 0;
}
int N = 2 * n - 1 , mx = 0 , idx = 0;
for(int i = 0 ;i < N ; i ++){
cin >> A[i] , mp[A[i]] ++;
if(mp[A[i]] > mx)
mx = mp[A[i]] , idx = A[i];
}
//if(mp.begin() -> first != idx) Q();
set<int> S;
for(int i = 0 ;i < N ;i ++)
mp1[mp[A[i]]].insert(A[i]), S.insert(A[i]);
for(int m = n / 2 , x = 1; m ; m >>= 1 , x ++){
if(mp1[x].size() != m)
Q();
}
for(auto no : S)
Adj[mx - mp[no] + 1].insert(no);
nn = mx + 1 ;
int KK = *Adj[1].begin();
Adj[1].erase(Adj[1].begin());
build(1 , KK , 0);
cout << "YES\n";
for(int i = 1; i <= mx ;i ++)
for(int l = 0; l < Ans[i].size() ;l ++)
cout << Ans[i][l] << " ";
}
Problem solution in C.
#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;
}
0 Comments