Drive – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Drive HackerRank 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;
}
Java Drive HackerRank Solution
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 scan = new Scanner(System.in);
//try{scan = new Scanner(new File("input00.txt"));}catch(Exception e){}
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);
//printStations(steps);
//System.out.println(passengerTime(steps,passengers));
Queue<run> runs = new PriorityQueue();
findruns(runs,steps);
//printruns(runs);
//System.out.println(totalDistance(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;}
//System.out.println("Station "+String.valueOf(s)+", saved "+String.valueOf(x));
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){
// timeTaken should be 0 for all stations
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(" : "+String.valueOf(s));
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);
}
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below