HackerRank Drive problem solution

In this HackerRank Drive problem solution, The bus is equipped with K units of Nitro (N2O). If going from station one to station two 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 traveling time for all commuters? The traveling time equals the time he/she arrived at the destination minus the time he/she arrived at the start station.

Problem solution in Java.

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);
    }
}

Problem solution in C++.

#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;
}

Problem solution in C.

#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;
}