In this post, we will solve HackerRank Drive Problem Solution.
HackerRank is starting a bus service in MountainView, California. The bus starts at time T = 0 at station1 and goes through station2, station3, station4 in that order and reaches the headquarters located at stationn. At every station, the bus waits for various commuters to arrive before it departs to the next station. Ignoring the acceleration, the bus moves at 1 meter / second. i.e., if stationi and stationj are 1000 meters apart, the bus takes 1000 seconds to travel from stationi to stationj.
The bus is equipped with K units of Nitro (N2O). If going from stationi to stationj takes x seconds, then using t units of nitro can decrease the time taken to max(x-t, 0) seconds where max(a,b) denotes the greater of the two values between a & b. The Nitro can be used all at once or in multiples of 1 unit.
If the bus driver travels optimally, what is the minimum sum of travelling time for all commuters? The travelling time equals to the time he/she arrived at the destination minus the time he/she arrived the start station.
Please remember that the driver must take all passengers to their destination.
Input Format
The first line contains 3 space separated integers n, m and K which indicate the number of stations, total number of people who board the bus at various stations and the total units of Nitro (N2O) present in the bus.
The second line contains n-1 space separated integers where the ith integer indicates the distance between station(i-1) to stationi.
m lines follow each containing 3 space separated integers. The ith line contains ti, si and ei in that order indicating the arrival time of the commuter at si at time ti with his destination being ei.
n m K
d1 d2 ... dn-1 // di: the distance between station_i to station_(i+1).
t1 s1 e1 // commuter 1 arrives at his boarding point at s1 and his destination is e1
t2 s2 e2
...
tm sm em
Constraints
0 < n <= 100000
0 < m <= 100000
0 <= K <= 10000000
0 < di <= 100
0 <= ti <= 10000000
1 <= si < ei <= n
Output Format
The minimal total travel time.
Sample Input
3 3 2
1 4
1 1 3
2 1 2
5 2 3
Sample Output
9
Explanation
The bus waits for the 1st and the 2nd commuter to arrive at station1 and travels to station2 carrying 2 passengers. The travel time from station1 to station2 is 1 second. It then waits for the 3rd commuter to board the bus at time = 5, 2nd commuter deboards the bus. The 3rd commuter boards the bus at t = 5. The bus now uses 2 units of nitro, this reduces the commute time to travel to station3 from 4 to 2.
Hence, the total time spent by each of the passengers on the bus is
- 1 (time spent waiting for commuter 2) + 1 (travel time from station1 to station2) + 2 (time spent waiting for commuter 3) + 2 (travel time from station2 to station3) = 6
- 1 (travel time from station1 to station2)
- 2 (travel time from station2 to station3)6+1+2 = 9
hence the answer.
Timelimits
Timelimits for this challenge can be seen here
Drive C Solution
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int u;
int cur;
int w;
int c;
}node;
int last_arrive[100000], drop[100001], d[100000], heap_list[100001];
node heap[100001];
void heap_insert(node *elem, int *size)
{
(*size)++;
int index = (*size);
while( index > 1 && elem -> w < heap[index/2].w )
{
heap[index] = heap[index/2];
heap_list[heap[index].u] = index;
index /= 2;
}
heap[index] = (*elem);
heap_list[elem -> u] = index;
return;
}
void heap_update(node *elem, int *size)
{
int index = heap_list[elem -> u];
while( index * 2 <= *size && elem -> w > heap[index*2].w || index * 2 + 1 <= *size && elem -> w > heap[index*2+1].w )
{
index = ( index * 2 + 1 <= *size && heap[index*2].w > heap[index*2+1].w ) ? index * 2 + 1 : index * 2;
heap[index/2] = heap[index];
heap_list[heap[index].u] = index / 2;
}
heap[index] = (*elem);
heap_list[elem -> u] = index;
return;
}
void heap_read(int *size, node *ans)
{
(*ans) = heap[1];
int index = 1;
while( index * 2 < *size && heap[*size].w > heap[index*2].w || index * 2 + 1 < *size && heap[*size].w > heap[index*2+1].w )
{
index = ( heap[index*2].w > heap[index*2+1].w ) ? index * 2 + 1 : index * 2;
heap[index/2] = heap[index];
heap_list[heap[index].u] = index / 2;
}
heap[index] = heap[*size];
heap_list[heap[index].u] = index;
(*size)--;
return;
}
int main()
{
int n, m, k, x, y, z, total_use, last_time, heap_size, i;
long long start, ans;
node elem;
scanf("%d%d%d", &n, &m, &k);
for( i = 0 ; i < n - 1 ; i++ )
{
scanf("%d", d + i);
}
for( i = start = 0 ; i < m ; i++ )
{
scanf("%d%d%d", &x, &y, &z);
start += x;
if( x > last_arrive[y-1] )
{
last_arrive[y-1] = x;
}
drop[z-1]++;
}
for( i = n - 2 ; i >= 0 ; i-- )
{
drop[i] += drop[i+1];
}
for( i = ans = total_use = last_time = heap_size = 0 ; i < n ; i++ )
{
if(i)
{
total_use += d[i-1];
}
ans += ( drop[i] - drop[i+1] ) * (long long)last_time;
if( last_arrive[i] > last_time )
{
if(i)
{
elem.u = elem.cur = i;
elem.w = drop[i] - drop[i+1];
elem.c = last_arrive[i] - last_time;
heap_insert(&elem, &heap_size);
}
last_time = last_arrive[i];
}
}
elem.u = elem.cur = n - 1;
elem.w = drop[n-1] - drop[n];
elem.c = 100000000;
heap_insert(&elem, &heap_size);
if( total_use <= k )
{
printf("%lld", ans - start);
return 0;
}
k = total_use - k;
while(k)
{
elem = heap[1];
if( elem.c <= d[elem.cur-1] && elem.c <= k )
{
ans += elem.w * (long long)elem.c;
k -= elem.c;
d[elem.cur-1] -= elem.c;
heap_read(&heap_size, &elem);
}
else if( d[elem.cur-1] <= elem.c && d[elem.cur-1] <= k )
{
ans += elem.w * (long long)d[elem.cur-1];
k -= d[elem.cur-1];
elem.c -= d[elem.cur-1];
d[elem.cur-1] = 0;
for( ; elem.cur > 0 && !d[elem.cur-1] ; elem.cur-- );
if(elem.cur)
{
elem.w = drop[elem.cur] - drop[elem.u+1];
heap_update(&elem, &heap_size);
}
else
{
heap_read(&heap_size, &elem);
}
}
else
{
ans += elem.w * (long long)k;
k = 0;
}
}
printf("%lld", ans - start);
return 0;
}Drive C++ Solution
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k;
int dist[100100];
int late[100100];
int bin[100100];
int bout[100100];
int arrival[100100];
vector<long long> peop[100100];
long long ans;
void gen() {
cout << 100 << " " << 100 << " " << 1000 << endl;
for(int i = 0; i < 99; ++i) {
cout << rand() % 1000 << " ";
}
for(int i = 0; i < 100; ++i) {
int y = rand() % 100 + 1, x = rand() % y;
cout << rand() % (x * 1000 + 100) << " " << x << " " << y << endl;
}
exit(0);
}
struct st {
int i, j;
long long saved;
int spend;
st(int i, int j, long long saved, int spend) : i(i), j(j), saved(saved), spend(spend) {}
bool operator < (st a) const {
if (saved != a.saved) {
return saved < a.saved;
}
return spend < a.spend;
}
};
priority_queue<st> q;
int add(int i) {
if (i == n) return n;
int spend = 1000000000;
int j = i + 1;
if (dist[i]) {
spend = min(spend, dist[i]);
long long saved = 0;
for(j = i + 1; j <= n; ++j) {
--arrival[j];
saved += bout[j];
if (late[j] > arrival[j]) {
break;
}
spend = min(spend, arrival[j] - late[j] + 1);
}
if (j > n) j = n;
//cout << i << " = " << j << endl;
st w(i, j, saved, spend);
q.push(w);
for(int q = i + 1; q <= j; ++q) {
++arrival[q];
}
}
return j;
}
int main() {
//gen();
cin >> n >> m >> k;
--n;
for(int i = 0; i < n; ++i) {
cin >> dist[i];
}
for(int i = 0; i < m; ++i) {
int t, s, e;
cin >> t >> s >> e;
--s;
--e;
late[s] = max(late[s], t);
++bout[e];
peop[s].push_back(t);
}
late[n] = -1000000000;
long long nowt = 0, carry = 0;
for(int i = 0; i < n; ++i) {
arrival[i] = nowt;
for(int j = 0; j < peop[i].size(); ++j) {
if (peop[i][j] < nowt) {
ans += nowt - peop[i][j];
} else {
ans += carry * (peop[i][j] - nowt);
}
++carry;
nowt = max(peop[i][j], nowt);
}
ans += carry * dist[i];
nowt += dist[i];
carry -= bout[i + 1];
}
arrival[n] = nowt;
int cur = 0;
while(cur < n) {
cur = add(cur);
}
while(k && !q.empty()) {
st w = q.top();
q.pop();
if (w.spend >= k)
{
ans -= w.saved * k;
break;
}ans -= w.saved * w.spend;
k -= w.spend;
dist[w.i] -= w.spend;
for(int i = w.i + 1; i <= w.j; ++i) {
arrival[i] -= w.spend;
}
int x = w.i;
while(x < w.j)
{
x = add(x);
}
}
cout << ans << endl;
return 0;
}Drive Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Drive {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
step[] steps = new step[scan.nextInt()];
passenger[] passengers = new passenger[scan.nextInt()];
int nitro = scan.nextInt();
loadStuff(scan,steps,passengers);
addPassengers(steps,passengers);
calcDepartures(steps);
Queue<run> runs = new PriorityQueue();
findruns(runs,steps);
saveNitro(steps,runs,nitro);
calcDepartures(steps);
System.out.println(passengerTime(steps,passengers));
}
static void saveNitro(step[] steps,Queue<run> runs,int nitroLimit){
long targetSaving = totalDistance(steps) - nitroLimit;
run r;
int s;
int x;
while(0<targetSaving){
r = runs.poll();
s = r.station;
x = steps[s].distance - steps[s].travelTime;
if(x>r.deadline){x=r.deadline;}
if(x>targetSaving){x=(int)targetSaving;}
steps[s].travelTime += x;
r.deadline -= x;
targetSaving -= x;
if ((0<s) && (0 < r.deadline)){
r.carrying += steps[s].dropped;
r.station--;
runs.add(r);
}
}
}
static long totalDistance(step[] steps){
long distance=0;
for(step s : steps){
distance += s.distance;
}
return distance;
}
static void printruns(Queue<run> runs){
for(run r : runs){
System.out.println("~~~~~~~~");
System.out.println("station : "+String.valueOf(r.station));
System.out.println("deadline : "+String.valueOf(r.deadline));
System.out.println("tocarry : "+String.valueOf(r.carrying));
}
}
static void findruns(Queue<run> runs,step[] steps){
steps[steps.length-1].departure = 2000000000;
for(int i=0;i<steps.length-1;i++){
if(steps[i].departure < steps[i+1].departure){
run r = new run();
r.station = i;
r.deadline = steps[i+1].departure - steps[i].departure;
r.carrying = steps[i+1].dropped;
runs.add(r);
}
}
}
static long passengerTime(step[] steps,passenger[] passengers){
long total = 0;
for(passenger p : passengers){
total += steps[p.dest-1].departure + steps[p.dest-1].travelTime - p.arrival;
}
return total;
}
static void calcDepartures(step[] steps){
int t = 0;
for (step s : steps){
if(s.departure < t){
s.departure = t;
}else{
t = s.departure;
}
t+=s.travelTime;
}
}
static void addPassengers(step[] steps, passenger[] passengers){
for (passenger p : passengers) {
if(steps[p.start].departure < p.arrival){
steps[p.start].departure = p.arrival;
}
steps[p.start].pickedUp++;
steps[p.dest].dropped++;
}
int load=0;
for (step s : steps){
load += s.pickedUp - s.dropped;
s.carried = load;
}
}
static void loadStuff(Scanner scan,step[] steps, passenger[] passengers){
for(int i=0;i<steps.length-1;i++){
steps[i] = new step();
steps[i].distance = scan.nextInt();
steps[i].departure = 0;
steps[i].travelTime = 0;
steps[i].carried = 0;
steps[i].pickedUp = 0;
steps[i].dropped = 0;
}
steps[steps.length-1] = new step();
for(int i=0;i<passengers.length;i++){
passengers[i] = new passenger();
passengers[i].arrival = scan.nextInt();
passengers[i].start = scan.nextInt()-1;
passengers[i].dest = scan.nextInt()-1;
}
}
static void printStations(step[] steps){
for(step s : steps){
System.out.println("-------");
System.out.println("departure : "+String.valueOf(s.departure));
System.out.println("distance : "+String.valueOf(s.distance));
System.out.println("travel time : "+String.valueOf(s.travelTime));
System.out.println("picked up : "+String.valueOf(s.pickedUp));
System.out.println("dropped : "+String.valueOf(s.dropped));
System.out.println("carried : "+String.valueOf(s.carried));
}
}
}
class passenger{
public
int arrival;
int start;
int dest;
}
class step{
public
int departure;
int distance;
int carried;
int pickedUp;
int dropped;
int travelTime;
}
class run implements Comparable<run>{
public
int station;
int deadline;
int carrying;
@Override public int compareTo(run r2){
return (this.carrying - r2.carrying);
}
}
