In this HackerRank Airports, problem-solution Airports are being built on a straight road according to a new construction plan. For convenience, imagine a number line on which at different points airports can be positioned. Because a plane can't take off and start landing immediately, there will be flying between two airports in locations x and y if and only if |x - y| >= d, where d is a constant.
Changing the position of an airport from x to y costs |x-y|. The cost to fix a certain plan is the minimum total cost of changing the positions of airports. After the changes, it should be possible to travel between any pair of airports, possibly taking flights through some intermediate airports. Note that it's possible that two airports have the same initial position, and this can be the case after changes too.
On an ith day, a plan to build a new airport with position xi is announced. On each day that a new airport is announced, print the smallest cost to fix the set of airports announced so far.
Problem solution in Python.
import math
import os
import random
import re
import sys
from heapq import heappop, heappush, heapify
#
# Complete the 'airports' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
# 1. INTEGER d
# 2. INTEGER_ARRAY x
#
def airports(min_dist, airports):
road = sorted(set(airports))
len_road = len(road)
answers = []
airport_indices = dict()
for i, a in enumerate(road):
airport_indices[a] = i
qty = [0] * len_road
for a in airports:
qty[airport_indices[a]] += 1
safe = []
near_left = []
near_right = []
near_both = []
for i in range(len_road - 1):
gap = (i, i + 1)
safe.append(gap)
heapify(near_left)
heapify(near_right)
heapify(near_both)
left_airport = 0
right_airport = len_road - 1
second_left = 1
second_right = len_road - 2
next_airport = list(range(1, len_road)) + ['N']
prev_airport = ['N'] + list(range(len_road - 1))
for ap in reversed(airports):
road_left_airport, road_right_airport = road[left_airport], road[right_airport]
while safe and (road[safe[-1][1]] - road_left_airport < min_dist or road_right_airport - road[safe[-1][0]] < min_dist):
gap = safe.pop()
if road[gap[1]] - road_left_airport < min_dist:
heappush(near_left,(0 - road[gap[1]],gap))
else:
heappush(near_right,(road[gap[0]],gap))
while near_left and road_right_airport - road[near_left[0][1][0]] < min_dist:
gap = heappop(near_left)[1]
heappush(near_both,(road[gap[0]] - road[gap[1]], gap))
while near_right and road[near_right[0][1][1]] - road_left_airport < min_dist:
gap = heappop(near_right)[1]
heappush(near_both,(road[gap[0]] - road[gap[1]], gap))
while near_both and (near_both[0][1][0] < left_airport or near_both[0][1][1] > right_airport):
heappop(near_both)
if safe:
answers.append(0)
else:
possible_answers = [min_dist]
if left_airport != right_airport:
if qty[left_airport] == 1:
possible_answers.append(min_dist + road_left_airport - road[second_left])
if qty[right_airport] == 1:
possible_answers.append(min_dist + road[second_right] - road_right_airport)
if near_left:
possible_answers.append(max(0, min_dist + road_left_airport - road[near_left[0][1][1]]))
if near_right:
possible_answers.append(max(0, min_dist + road[near_right[0][1][0]] - road_right_airport))
if near_both:
possible_answers.append(0)
nb = near_both[0][1]
possible_answers[-1] += max(0,min_dist + road_left_airport - road[nb[1]])
possible_answers[-1] += max(0,min_dist + road[nb[0]] - road_right_airport)
answers.append(min(possible_answers))
ai = airport_indices[ap]
qty[ai] -= 1
if qty[ai]:
continue
while second_left < len_road - 1 and qty[second_left] == 0:
second_left += 1
while second_right > 0 and qty[second_right] == 0:
second_right -= 1
if ai == left_airport or ai == right_airport:
while left_airport < len_road - 1 and qty[left_airport] == 0:
left_airport += 1
while right_airport > 0 and qty[right_airport] == 0:
right_airport -= 1
second_left = max(second_left, left_airport + 1)
second_right = min(second_right, right_airport - 1)
while second_left < len_road - 1 and qty[second_left] == 0:
second_left += 1
while second_right > 0 and qty[second_right] == 0:
second_right -= 1
else:
l = prev_airport[ai]
r = next_airport[ai]
next_airport[l] = r
prev_airport[r] = l
gap = (l, r)
safe.append(gap)
answers.reverse()
answers[0] = 0
return answers
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
q = int(input().strip())
for q_itr in range(q):
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
d = int(first_multiple_input[1])
x = list(map(int, input().rstrip().split()))
result = airports(d, x)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static class Gap {
int start;
int size;
int end;
boolean outdated = false;
Gap(int start, int size) {
this.start = start;
this.size = size;
this.end = start + size - 1;
}
void split(int cut) {
if (size == 1) {
return;
}
if (cut == start) {
Gap split = new Gap(start + 1, size - 1);
gaps.add(split);
topGaps.add(split);
return;
}
if (cut == start + size - 1) {
Gap split = new Gap(start, size - 1);
gaps.add(split);
topGaps.add(split);
return;
}
Gap split = new Gap(start, cut - start);
gaps.add(split);
topGaps.add(split);
split = new Gap(cut + 1, size - (cut - start) - 1);
gaps.add(split);
topGaps.add(split);
}
public int getStart() {
return start;
}
public int getSize() {
return size;
}
}
static int d;
static int[] positions;
static int index = 0;
static int minIndex;
static int maxIndex;
static TreeSet<Gap> gaps = new TreeSet<>(Comparator.comparing(Gap::getStart));
static PriorityQueue<Gap> topGaps = new PriorityQueue<>(Comparator.comparing(Gap::getSize).reversed());
static int oldLeft;
static int oldRight;
static void init() {
minIndex = 0;
maxIndex = 0;
index = 0;
gaps.clear();
topGaps.clear();
Gap rootGap = new Gap(-1000000000, 2000000000);
gaps.add(rootGap);
topGaps.add(rootGap);
oldLeft = -1000000000;
oldRight = 1000000000;
}
static int solveNext() {
int x = positions[index++];
if (index == 1) {
return 0;
}
int newSplitPoint = Integer.MAX_VALUE;
if (x < positions[minIndex]) {
if (minIndex != maxIndex) {
newSplitPoint = positions[minIndex];
}
minIndex = index - 1;
} else if (x > positions[maxIndex]) {
if (minIndex != maxIndex) {
newSplitPoint = positions[maxIndex];
}
maxIndex = index - 1;
} else {
newSplitPoint = x;
}
if (positions[maxIndex] - positions[minIndex] >= 2 * d - 1) {
return 0;
}
int left = positions[maxIndex] - d + 1;
if (left > oldLeft) {
for (Iterator<Gap> iterator = gaps.iterator(); iterator.hasNext();) {
Gap gap = iterator.next();
if (left <= gap.start) {
break;
}
gap.outdated = true;
iterator.remove();
if (left < gap.start + gap.size) {
Gap newGap = new Gap(left, gap.size - (left - gap.start));
gaps.add(newGap);
topGaps.add(newGap);
break;
}
}
oldLeft = left;
}
int right = positions[minIndex] + d - 1;
if (right < oldRight) {
for (Iterator<Gap> iterator = gaps.descendingIterator(); iterator.hasNext();) {
Gap gap = iterator.next();
if (right >= gap.end) {
break;
}
gap.outdated = true;
iterator.remove();
if (right >= gap.start) {
Gap newGap = new Gap(gap.start, right - gap.start + 1);
gaps.add(newGap);
topGaps.add(newGap);
break;
}
}
oldRight = right;
}
if (newSplitPoint >= left && newSplitPoint <= right) {
Gap floor = gaps.floor(new Gap(newSplitPoint, 0));
if (floor != null) {
if (newSplitPoint <= floor.end) {
floor.outdated = true;
gaps.remove(floor);
floor.split(newSplitPoint);
}
}
}
if (index == 2) {
return Math.max(0, d - (positions[maxIndex] - positions[minIndex]));
}
while (!topGaps.isEmpty() && topGaps.peek().outdated) {
topGaps.poll();
}
return right - left + 1 - (topGaps.isEmpty() ? 0 : topGaps.peek().size);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
positions = new int[n];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
positions[j] = Integer.parseInt(st.nextToken());
}
init();
for (int j = 0; j < n; j++) {
int res = solveNext();
bw.write(res + " ");
}
bw.write('\n');
}
br.close();
bw.close();
}
}
Problem solution in C++.
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
struct seg_t {
int xmin;
int xmax;
int dmax;
seg_t() : xmin(0), xmax(0), dmax(-1) {
}
seg_t(int xmin, int xmax, int dmax) : xmin(xmin), xmax(xmax), dmax(dmax) {
}
};
seg_t combine(seg_t const& lhv, seg_t const& rhv) {
if (lhv.dmax < 0) return rhv;
if (rhv.dmax < 0) return lhv;
return seg_t(lhv.xmin, rhv.xmax,
std::max(std::max(lhv.dmax, rhv.dmax), rhv.xmin - lhv.xmax));
}
struct ds_t {
std::vector<int> const& uxs;
std::unordered_map<int, int> idxs;
int size;
std::vector<seg_t> ss;
ds_t(std::vector<int> const& uxs) : uxs(uxs) {
int nux = (int)(uxs.size());
for (int i = 0; i < nux; ++i) {
idxs[uxs[i]] = i;
}
size = 2;
while (size < nux) {
size *= 2;
}
ss.resize(size * 2);
}
void add(int x) {
int pos = size + idxs[x];
ss[pos].xmin = x;
ss[pos].xmax = x;
ss[pos].dmax = 0;
while (pos > 1) {
int par = pos / 2;
int lch = par * 2;
int rch = lch + 1;
ss[par] = combine(ss[lch], ss[rch]);
pos = par;
}
}
seg_t query(int left, int right) {
int lpos = size + left;
int rpos = size + right;
seg_t lres;
seg_t rres;
while (lpos <= rpos) {
if ((lpos ^ 1) < lpos) lres = combine(lres, ss[lpos]);
if (rpos < (rpos ^ 1)) rres = combine(ss[rpos], rres);
lpos = (lpos + 1) / 2;
rpos = (rpos - 1) / 2;
}
return combine(lres, rres);
}
};
struct solver_t {
int n;
int d;
std::vector<int> xs;
std::set<int> xset;
std::vector<int> uxs;
std::vector<int> anss;
void solve() {
xs.clear();
xset.clear();
scanf("%d", &n);
scanf("%d", &d);
xs.reserve(n);
anss.reserve(n);
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
xs.push_back(x);
xset.insert(x);
}
int nux = (int)(xset.size());
uxs.reserve(nux);
for (auto x : xset) {
uxs.push_back(x);
}
int xmin = std::min(xs[0], xs[1]);
int xmax = std::max(xs[0], xs[1]);
int left = 0;
int right = nux - 1;
anss.push_back(0);
anss.push_back(((xmax - xmin) >= d) ? 0 : (d - (xmax - xmin)));
ds_t ds(uxs);
for (int i = 2; i < n; ++i) {
if (d == 0) {
anss.push_back(0);
continue;
}
int x = xs[i];
if (x < xmin) {
ds.add(xmin);
xmin = x;
} else if (x > xmax) {
ds.add(xmax);
xmax = x;
} else {
ds.add(x);
}
while (xmax - uxs[left] >= d) {
++left;
}
while (uxs[right] - xmin >= d) {
--right;
}
int xleft = xmax - d;
int xright = xmin + d;
if (xleft >= xright || left > right) {
anss.push_back(0);
continue;
}
auto qres = ds.query(left, right);
if (qres.dmax < 0) {
anss.push_back(0);
} else {
int dmax = std::max(qres.dmax,
std::max(qres.xmin - xleft, xright - qres.xmax));
anss.push_back(xright - xleft - dmax);
}
}
for (int i = 0; i < n; ++i) {
if (i > 0) printf(" ");
printf("%d", anss[i]);
}
printf("\n");
}
};
int main() {
int q;
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
solver_t solver;
solver.solve();
}
return 0;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
struct node{
long val;
struct node* left;
struct node* right;
int ht;
int descendants;
int low;
int high;
int longdist;
};
void reht(struct node *root){
if(root != NULL){
int lht = ((*root).left == NULL? -1 : (*(*root).left).ht);
int rht = ((*root).right == NULL? -1 : (*(*root).right).ht);
(*root).ht = (lht > rht? lht + 1 : rht + 1);
(*root).descendants = ((*root).left == NULL? 0 : (*(*root).left).descendants) + ((*root).right == NULL? 0 : (*(*root).right).descendants) + 1;
(*root).low = ((*root).left == NULL? (*root).val : (*(*root).left).low);
(*root).high = ((*root).right == NULL? (*root).val : (*(*root).right).high);
if((*root).descendants == 1){
(*root).longdist = -INT_MAX;
}
else{
if((*root).left == NULL){
(*root).longdist = (*(*root).right).val - (*root).val;
}
else if((*root).right == NULL){
(*root).longdist = (*root).val - (*(*root).left).val;
}
else{
int check1 = (*(*root).left).longdist;
int check2 = (*root).val - (*(*root).left).high;
int leftcheck = (check1 > check2? check1 : check2);
int check3 = (*(*root).right).longdist;
int check4 = (*(*root).right).low - (*root).val;
int rightcheck = (check3 > check4? check3 : check4);
(*root).longdist = (leftcheck > rightcheck? leftcheck : rightcheck);
}
}
}
}
struct node* rebalance(struct node* root){
int lht = ((*root).left == NULL? -1 : (*(*root).left).ht);
int rht = ((*root).right == NULL? -1 : (*(*root).right).ht);
if(lht - rht > 1){
struct node *l = (*root).left;
int llht = ((*l).left == NULL? -1 : (*(*l).left).ht);
int lrht = ((*l).right == NULL? -1 : (*(*l).right).ht);
if(lrht > llht){
struct node *lr = (*l).right;
(*l).right = (*lr).left;
(*lr).left = l;
(*root).left = lr;
}
l = (*root).left;
(*root).left = (*l).right;
(*l).right = root;
reht((*l).left);
reht((*l).right);
reht(l);
return l;
}
else if(rht - lht > 1){
struct node *r = (*root).right;
int rlht = ((*r).left == NULL? -1 : (*(*r).left).ht);
int rrht = ((*r).right == NULL? -1 : (*(*r).right).ht);
if(rlht > rrht){
struct node *rl = (*r).left;
(*r).left = (*rl).right;
(*rl).right = r;
(*root).right = rl;
}
r = (*root).right;
(*root).right = (*r).left;
(*r).left = root;
reht((*r).left);
reht((*r).right);
reht(r);
return r;
}
else{
reht(root);
return root;
}
}
struct node* insert(struct node * root, long val)
{
if(root == NULL){
struct node *newroot = malloc(sizeof(struct node));
newroot[0].ht = 0;
newroot[0].left = NULL;
newroot[0].right = NULL;
newroot[0].val = val;
newroot[0].descendants = 1;
newroot[0].low = val;
newroot[0].high = val;
newroot[0].longdist = -INT_MAX;
return newroot;
}
else{
if(val < (*root).val){
(*root).left = insert((*root).left, val);
return rebalance(root);
}
else{
(*root).right = insert((*root).right, val);
return rebalance(root);
}
}
}
struct node* delete(struct node* root, long val, int *successful){
if(root == NULL){
*successful = 0;
return NULL;
}
else if(val < (*root).val){
(*root).left = delete((*root).left, val, successful);
return rebalance(root);
}
else if(val > (*root).val){
(*root).right = delete((*root).right, val, successful);
return rebalance(root);
}
else{
*successful = 1;
if((*root).right == NULL && (*root).left == NULL){
free(root);
return NULL;
}
else if((*root).right == NULL){
(*root).val = (*(*root).left).val;
(*root).left = NULL;
reht(root);
return root;
}
else{
struct node *curr = (*root).right;
while((*curr).left != NULL){
curr = (*curr).left;
}
(*root).val = (*curr).val;
(*root).right = delete((*root).right, (*root).val, successful);
return rebalance(root);
}
}
}
int findprev(struct node *root, int data){
if(root == NULL){
return INT_MIN;
}
else{
if(data <= (*root).val){
return findprev((*root).left, data);
}
else{
int toreturn = findprev((*root).right, data);
return (toreturn == INT_MIN? (*root).val : toreturn);
}
}
}
int findnext(struct node *root, int data){
if(root == NULL){
return INT_MAX;
}
else{
if(data >= (*root).val){
return findnext((*root).right, data);
}
else{
int toreturn = findnext((*root).left, data);
return (toreturn == INT_MAX? (*root).val : toreturn);
}
}
}
void printtree(struct node *root){
if(root != NULL){
printtree((*root).left);
printf(" %ld ", (*root).val);
printtree((*root).right);
}
}
int* airports(int d, int n, int* x) {
int* toreturn = malloc(n*sizeof(int));
toreturn[0] = 0;
toreturn[1] = d - abs(x[1] - x[0]);
toreturn[1] = (toreturn[1] > 0? toreturn[1] : 0);
struct node *fulllist = insert(insert(NULL, x[0]), x[1]);
struct node *midlist = insert(insert(NULL, x[0]), x[1]);
for(int i = 2; i < n; i++){
int pos = x[i];
fulllist = insert(fulllist, pos);
midlist = insert(midlist, pos);
int low = findnext(fulllist, INT_MIN);
int high = findprev(fulllist, INT_MAX);
int temp;
while(findnext(midlist, INT_MIN) < high - d){
midlist = delete(midlist, findnext(midlist, INT_MIN), &temp);
}
while(findprev(midlist, INT_MAX) > low + d){
midlist = delete(midlist, findprev(midlist, INT_MAX), &temp);
}
midlist = delete(midlist, low, &temp);
midlist = delete(midlist, high, &temp);
if(midlist == NULL){
toreturn[i] = 0;
}
else{
int check1 = d - (high - findprev(midlist, low + d));
int check2 = d - (findnext(midlist, high - d) - low);
toreturn[i] = (check1 < check2? check1 : check2);
if((*midlist).descendants > 1){
int check = 2*d - (high - low) - (*midlist).longdist;
toreturn[i] = (check < toreturn[i]? check : toreturn[i]);
}
toreturn[i] = (toreturn[i] > 0? toreturn[i] : 0);
}
midlist = insert(midlist, low);
midlist = insert(midlist, high);
}
return toreturn;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char* q_endptr;
char* q_str = readline();
int q = strtol(q_str, &q_endptr, 10);
if (q_endptr == q_str || *q_endptr != '\0') { exit(EXIT_FAILURE); }
for (int q_itr = 0; q_itr < q; q_itr++) {
char** nd = split_string(readline());
char* n_endptr;
char* n_str = nd[0];
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
char* d_endptr;
char* d_str = nd[1];
int d = strtol(d_str, &d_endptr, 10);
if (d_endptr == d_str || *d_endptr != '\0') { exit(EXIT_FAILURE); }
char** x_temp = split_string(readline());
int* x = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
char* x_item_endptr;
char* x_item_str = *(x_temp + i);
int x_item = strtol(x_item_str, &x_item_endptr, 10);
if (x_item_endptr == x_item_str || *x_item_endptr != '\0') { exit(EXIT_FAILURE); }
*(x + i) = x_item;
}
int result_count;
int* result = airports(d, n, x);
for (int i = 0; i < n; i++) {
fprintf(fptr, "%d", *(result + i));
if (i != n - 1) {
fprintf(fptr, " ");
}
}
fprintf(fptr, "\n");
}
fclose(fptr);
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';
}
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