Robot – 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++ replace HackerRank Solution
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, long long> pii;
#define INF 1000000000
#define pb push_back
#define itr iterator
#define sz size()
#define mp make_pair
multiset<long long> values;
vector< long long> adj[6000000];
int v, p;
int n;
int main() {
scanf("%d", &n);
adj[1].push_back(0);
values.insert(0);
long long tot = 0;
for (int i = 0; i < n; i++) {
scanf("%d %d", &v, &p);
tot += v;
for (int k = 0; k < adj[i].size(); k++) {
values.erase(values.find(adj[i][k]));
}
long long cur = -v + *values.rbegin();
//printf("cur = %lld %d %lld\n", tot, -v, *values.rbegin());
values.insert(cur);
int will_rem = min(n, i + p + 1);
adj[will_rem].push_back(cur);
if (i == n-1) {
printf("%lld\n", tot + cur + v);
return 0;
}
}
}
Java rep HackerRank Solution
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Egor Kulikov (egor@egork.net)
*/
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);
Robot solver = new Robot();
solver.solve(1, in, out);
out.close();
}
}
class Robot {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int count = in.readInt();
int[] value = new int[count];
int[] energy = new int[count];
IOUtils.readIntArrays(in, value, energy);
IntervalTree tree = new LongIntervalTree(count) {
@Override
protected long joinValue(long left, long right) {
return Math.max(left, right);
}
@Override
protected long joinDelta(long was, long delta) {
return was + delta;
}
@Override
protected long accumulate(long value, long delta, int length) {
return value + delta;
}
@Override
protected long neutralValue() {
return Long.MIN_VALUE / 2;
}
@Override
protected long neutralDelta() {
return 0;
}
};
tree.update(count - 1, count - 1, value[count - 1] - Long.MIN_VALUE / 2);
for (int i = count - 2; i >= 0; i--) {
if (energy[i] > 0) {
tree.update(i, i, tree.query(i + 1, i + energy[i]) - Long.MIN_VALUE / 2);
}
tree.update(i + 1, count - 1, value[i]);
}
out.printLine(tree.query(0, 0));
}
}
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void printLine(long i) {
writer.println(i);
}
}
class IOUtils {
public static void readIntArrays(InputReader in, int[]... arrays) {
for (int i = 0; i < arrays[0].length; i++) {
for (int j = 0; j < arrays.length; j++)
arrays[j][i] = in.readInt();
}
}
}
abstract class IntervalTree {
protected int size;
protected IntervalTree(int size) {
this(size, true);
}
public IntervalTree(int size, boolean shouldInit) {
this.size = size;
int nodeCount = Math.max(1, Integer.highestOneBit(size) << 2);
initData(size, nodeCount);
if (shouldInit)
init();
}
protected abstract void initData(int size, int nodeCount);
protected abstract void initAfter(int root, int left, int right, int middle);
protected abstract void initBefore(int root, int left, int right, int middle);
protected abstract void initLeaf(int root, int index);
protected abstract void updatePostProcess(int root, int left, int right, int from, int to, long delta, int middle);
protected abstract void updatePreProcess(int root, int left, int right, int from, int to, long delta, int middle);
protected abstract void updateFull(int root, int left, int right, int from, int to, long delta);
protected abstract long queryPostProcess(int root, int left, int right, int from, int to, int middle, long leftResult, long rightResult);
protected abstract void queryPreProcess(int root, int left, int right, int from, int to, int middle);
protected abstract long queryFull(int root, int left, int right, int from, int to);
protected abstract long emptySegmentResult();
public void init() {
if (size == 0)
return;
init(0, 0, size - 1);
}
private void init(int root, int left, int right) {
if (left == right) {
initLeaf(root, left);
} else {
int middle = (left + right) >> 1;
initBefore(root, left, right, middle);
init(2 * root + 1, left, middle);
init(2 * root + 2, middle + 1, right);
initAfter(root, left, right, middle);
}
}
public void update(int from, int to, long delta) {
update(0, 0, size - 1, from, to, delta);
}
protected void update(int root, int left, int right, int from, int to, long delta) {
if (left > to || right < from)
return;
if (left >= from && right <= to) {
updateFull(root, left, right, from, to, delta);
return;
}
int middle = (left + right) >> 1;
updatePreProcess(root, left, right, from, to, delta, middle);
update(2 * root + 1, left, middle, from, to, delta);
update(2 * root + 2, middle + 1, right, from, to, delta);
updatePostProcess(root, left, right, from, to, delta, middle);
}
public long query(int from, int to) {
return query(0, 0, size - 1, from, to);
}
protected long query(int root, int left, int right, int from, int to) {
if (left > to || right < from)
return emptySegmentResult();
if (left >= from && right <= to)
return queryFull(root, left, right, from, to);
int middle = (left + right) >> 1;
queryPreProcess(root, left, right, from, to, middle);
long leftResult = query(2 * root + 1, left, middle, from, to);
long rightResult = query(2 * root + 2, middle + 1, right, from, to);
return queryPostProcess(root, left, right, from, to, middle, leftResult, rightResult);
}
}
abstract class LongIntervalTree extends IntervalTree {
protected long[] value;
protected long[] delta;
protected LongIntervalTree(int size) {
this(size, true);
}
public LongIntervalTree(int size, boolean shouldInit) {
super(size, shouldInit);
}
protected void initData(int size, int nodeCount) {
value = new long[nodeCount];
delta = new long[nodeCount];
}
protected abstract long joinValue(long left, long right);
protected abstract long joinDelta(long was, long delta);
protected abstract long accumulate(long value, long delta, int length);
protected abstract long neutralValue();
protected abstract long neutralDelta();
protected long initValue(int index) {
return neutralValue();
}
protected void initAfter(int root, int left, int right, int middle) {
value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
delta[root] = neutralDelta();
}
protected void initBefore(int root, int left, int right, int middle) {
}
protected void initLeaf(int root, int index) {
value[root] = initValue(index);
delta[root] = neutralDelta();
}
protected void updatePostProcess(int root, int left, int right, int from, int to, long delta, int middle) {
value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
}
protected void updatePreProcess(int root, int left, int right, int from, int to, long delta, int middle) {
pushDown(root, left, middle, right);
}
protected void pushDown(int root, int left, int middle, int right) {
value[2 * root + 1] = accumulate(value[2 * root + 1], delta[root], middle - left + 1);
value[2 * root + 2] = accumulate(value[2 * root + 2], delta[root], right - middle);
delta[2 * root + 1] = joinDelta(delta[2 * root + 1], delta[root]);
delta[2 * root + 2] = joinDelta(delta[2 * root + 2], delta[root]);
delta[root] = neutralDelta();
}
protected void updateFull(int root, int left, int right, int from, int to, long delta) {
value[root] = accumulate(value[root], delta, right - left + 1);
this.delta[root] = joinDelta(this.delta[root], delta);
}
protected long queryPostProcess(int root, int left, int right, int from, int to, int middle, long leftResult, long rightResult) {
return joinValue(leftResult, rightResult);
}
protected void queryPreProcess(int root, int left, int right, int from, int to, int middle) {
pushDown(root, left, middle, right);
}
protected long queryFull(int root, int left, int right, int from, int to) {
return value[root];
}
protected long emptySegmentResult() {
return neutralValue();
}
}
Python 3 rep HackerRank Solution
import sys
from operator import itemgetter
N = int(input())
V, P = [None] * N, [None] * N
for i in range(N):
v_item, p_item = input().split()
V[i] = int(v_item)
P[i] = int(p_item)
games = []
for i in range(N):
maxVal = -1
games.sort(key=itemgetter(1))
for j in range(len(games) - 1, -1, -1):
game = games[j]
if game[1] == 0:
del games[0:j+1]
break
if maxVal < game[0]:
maxVal = game[0]
else:
del games[j]
game[0] += V[i]
game[1] += -1
if maxVal == -1:
maxVal = 0
games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])
Python 2 rep HackerRank Solution
import heapq
h =[]
N=int(raw_input())
p=[]
v=[]
for i in xrange(N):
vi,pi = (int(s) for s in raw_input().split())
v.append(vi)
p.append(pi)
current_up = p[0]
current_val = v[0]
for current_ind in xrange(1,N-1):
heapq.heappush(h,[current_val+v[current_ind], current_ind+p[current_ind]])
if current_ind >= current_up:
best_segment=heapq.heappop(h)
while best_segment[1]<=current_ind:
best_segment=heapq.heappop(h)
current_val = best_segment[0]
current_up = best_segment[1]
print sum(v)-current_val
C rep HackerRank Solution
/*
4
4 2
0 2
4 0
3 4
7
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int w;
} node;
void heap_insert(node *heap,node *elem,int *size,int idx);
void heap_read(node *heap,int *size,int idx);
long long get_val(int w,int idx,int *flag);
int *V,*P;
long long *sum,*dp;
int main(){
int N,i,heap_size=0,flag;
long long ans,max,t;
node *heap,elem;
scanf("%d",&N);
V=(int*)malloc(N*sizeof(int));
P=(int*)malloc(N*sizeof(int));
sum=(long long*)malloc(N*sizeof(long long));
dp=(long long*)malloc(N*sizeof(long long));
heap=(node*)malloc(2*N*sizeof(heap));
for(i=0;i<N;i++)
scanf("%d%d",V+i,P+i);
for(i=0;i<N;i++)
if(i==0)
sum[i]=V[i];
else
sum[i]=sum[i-1]+V[i];
for(i=0;i<N-1;i++){
max=0;
if(heap_size)
do{
t=get_val(heap[1].w,i,&flag);
if(flag>0 && t>max)
max=t;
else if(flag==0 && P[i] && t-V[i]>max){
max=t-V[i];
heap_read(heap,&heap_size,i);
}
else if(flag<=0)
heap_read(heap,&heap_size,i);
}while(flag<=0 && heap_size);
dp[i]=max;
elem.w=i;
heap_insert(heap,&elem,&heap_size,i);
}
max=0;
if(heap_size)
do{
t=get_val(heap[1].w,i,&flag);
if(flag>=0 && t>max)
max=t;
else if(flag<0)
heap_read(heap,&heap_size,i);
}while(flag<0 && heap_size);
printf("%lld",max);
return 0;
}
void heap_insert(node *heap,node *elem,int *size,int idx){
(*size)++;
int index=(*size);
while(index>1 && get_val(elem->w,idx,0)>get_val(heap[index/2].w,idx,0)){
heap[index]=heap[index/2];
index/=2;
}
heap[index]=(*elem);
return;
}
void heap_read(node *heap,int *size,int idx){
int index=1;
while(index*2<*size && get_val(heap[*size].w,idx,0)<get_val(heap[index*2].w,idx,0) || index*2+1<*size && get_val(heap[*size].w,idx,0)<get_val(heap[index*2+1].w,idx,0)){
index=(get_val(heap[index*2].w,idx,0)<get_val(heap[index*2+1].w,idx,0))?index*2+1:index*2;
heap[index/2]=heap[index];
}
heap[index]=heap[*size];
(*size)--;
return;
}
long long get_val(int w,int idx,int *flag){
if(flag){
if(idx-w>P[w])
*flag=-1;
else if(idx-w==P[w])
*flag=0;
else
*flag=1;
}
long long ans;
if(!w)
ans=0;
else
ans=dp[w-1];
return ans+sum[idx]-sum[w];
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below