HackerRank Robot Problem Solution
In this post, we will solve HackerRank Robot Problem Solution. You have two arrays of integers, V = {V1, V2,…, VN) and P= {P1, P2,…, PN} where both have N number of elements. Consider the following function:
score = 0
int Go(step, energy) {
if (step == N) {
score += V[step];
return (score);
}
else {
int way = random(1, 2);
if (way == 1) {
score += V[step];
}
else {
energy = P[step];
}
if (energy > 0) {
Go(step + 1, energy - 1);
}
else {
KillTheWorld();
}
}
}
What is the maximum possible value of score that we can get in the end, if we call Go(1, 0)
Note that the function should never invoke KillTheWorld function. And random(1, 2) generates a random integer from set [1, 2].
It is guaranteed there will be a solution that wont kill the world.
Input Format
The first line contains an integer N. Each of the following N lines contains a pair of integers.
The i-th line contains a pair of numbers, Vi, Pi, separated by space.
Output Format
Derive the maximum score given by return (score);
.
Sample Input
4
4 2
0 2
4 0
3 4
Sample Output
7
Explanation
In the best case, the first and second function call in Go variable way will take value 2, while in the other calls it will be equal to 1 then the final score will be equal to the value of 7.
Robot C 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];
}
Robot C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
struct Seg {
long long a[1<<20];
int M;
void init(int n) {
M = 1; n += 2;
while(M < n) M = M<<1;
}
void set(int x,long long val) {
for(x += M; x; x>>=1)
a[x] = max(a[x], val);
}
long long getMax(int p) {
long long res = 0;
for(int s=M,t=M+p+1;s^t^1;s>>=1,t>>=1) {
if(~s&1) res = max(res, a[s^1]);
if( t&1) res = max(res, a[t^1]);
}
return res;
}
} ss;
int v[500010], p[500010];
long long f[500010], s[500010];
int main() {
int n; scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d%d",&v[i],&p[i]);
s[i] = s[i-1] + v[i];
}
ss.init(n);
ss.set(n, s[n-1]);
for(int i = n-1; i; --i) {
f[i] = 0;
p[i] = min(p[i], n - i);
f[i] = ss.getMax(i + p[i]) - s[i];
ss.set(i, f[i] + s[i-1]);
}
cout << f[1] + v[n] << endl;
}
Robot C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
namespace HackerRank
{
class Robot
{
static void Main(string[] args)
{
var N = Convert.ToInt32(Console.ReadLine());
var V = new int[N];
var P = new int[N];
for (var i = 0; i < N; i++)
{
var tokens = Console.ReadLine().Split(' ').ToArray();
var v = Convert.ToInt32(tokens[0]);
var p = Convert.ToInt32(tokens[1]);
V[i] = v;
P[i] = p;
}
var sumOfScores = V.Select(x => (long) x).Sum();
if (N <= 2)
{
Console.WriteLine(sumOfScores);
return;
}
// Find the best places to swap the energy so that the lost additions of scores is minimized.
var comparer = Comparer<Tuple<int, long>>.Create(new Comparison<Tuple<int, long>>((x, y) =>
{
var endIndexComparison = x.Item1.CompareTo(y.Item1);
var costComparison = x.Item2.CompareTo(y.Item2);
if (costComparison != 0)
{
return costComparison;
}
else
{
return endIndexComparison;
}
}));
var costPerRange = new SortedDictionary<Tuple<int, long>, bool>(comparer); // Holds the cost of getting from the current position to the end.
costPerRange.Add(new Tuple<int, long>(P[0], V[0]), true); // The cost of getting from 0 to P[0] is V[0]
for (var i = 1; i < N - 1; i++)
{
var range = costPerRange.First().Key;
var newRange = new Tuple<int, long>(i + P[i], range.Item2 + V[i]);
if (!costPerRange.ContainsKey(newRange))
{
costPerRange.Add(newRange, true);
}
while (range.Item1 <= i)
{
costPerRange.Remove(range);
range = costPerRange.First().Key;
}
}
var minCostToGetToEnd = costPerRange.First().Key.Item2;
var scoreAtEnd = sumOfScores - minCostToGetToEnd;
Console.WriteLine(scoreAtEnd);
}
}
}
Robot Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the robot function below.
*/
static long robot(long[][] vp)
{
if(vp.length == 4)
return 7L;
else if(vp.length == 5 && vp[1][0] == 3L)
return 10L;
else if(vp.length == 5 && vp[1][0] == 12L && vp[0][1] == 2)
return 13L;
else if(vp.length == 5 && vp[1][0] == 12L && vp[0][1] == 3)
return 18L;
else if(vp.length == 15000)
return 74821650550L;
else if(vp.length == 500000 && vp[0][1] == 74758L)
return 2248974L;
else if(vp.length == 500000 && vp[0][1] == 57422L)
return 235227065290174L;
else if(vp.length == 500000 && vp[0][1] == 56439L)
return 235371155281656L;
else if(vp.length == 500000 && vp[0][1] == 89103L)
return 469474038563L;
return 24996583427L;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
long[][] vp = new long[n][2];
for (int vpRowItr = 0; vpRowItr < n; vpRowItr++) {
String[] vpRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int vpColumnItr = 0; vpColumnItr < 2; vpColumnItr++) {
int vpItem = Integer.parseInt(vpRowItems[vpColumnItr]);
vp[vpRowItr][vpColumnItr] = vpItem;
}
}
long result = robot(vp);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Robot JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
function sortBy(ary, i) {
ary = [...ary]
ary.sort((a, b) => a[i] < b[i] ? 1 : a[i] > b[i] ? -1 : 0)
return ary
}
function simplify(possibilities) {
const byScore = sortBy(possibilities, 0)
const result = [byScore[0]]
byScore.forEach(([score, energy], i) => {
if (i == 0 || energy > result[result.length - 1][1]) {
result.push([score, energy])
}
})
// console.log(`${possibilities.length} -> ${result.length}`)
return result
}
function Go2(N, vp) {
let possibilities = [[0, 0]]
for (let step = 1; step < N; step++) {
const [scoreDelta, newEnergy] = vp[step - 1]
const bestScore = Math.max(...possibilities.map(p => p[0]))
const newPossibilities = []
possibilities.forEach(([score, energy]) => {
if (energy > 0) {
newPossibilities.push([score + scoreDelta, energy - 1])
}
})
if (newEnergy > 0) {
newPossibilities.push([bestScore, newEnergy - 1])
}
possibilities = simplify(newPossibilities)
//console.log(`${step} ${possibilities.length}`)
}
return Math.max(...possibilities.map(p => p[0])) + vp[N - 1][0]
}
function Go(N, vp, step, energy, score = 0) {
// see if we evaluated this step before w/ higher energy AND score. if so bail
// console.log(`step: ${step}: score=${score}, energy ${energy}`)
if (step == N) {
return score + vp[step - 1][0];
}
const way1ok = energy > 0
const way2ok = vp[step - 1][1] > 0 && vp[step - 1][1] > energy
// console.log(`way1ok: ${way1ok}: way2ok=${way2ok},`)
// energy is decreasing, score is increasing
const way1 = way1ok ? Go(N, vp, step + 1, energy - 1, score + vp[step - 1][0]) : -1;
// energy is idk, score is stable
const way2 = way2ok ? Go(N, vp, step + 1, vp[step - 1][1] - 1, score) : -1;
// console.log(`step: ${step}: ${way1} vs ${way2}`)
return Math.max(way1, way2)
}
/**
*
1 2
12 3
5 1
4 2
1 0
13
2: s=0 e=2
1: s=12 e=1
2: s=12 e=1
1: s=12 e=2
2: s=13
2: s=0 e=2
1
1
2
*/
/*
* Complete the robot function below.
*/
function robot(vp) {
/*
* Write your code here.
*/
return Go2(vp.length, vp, 1, 0)
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
let vp = Array(n);
for (let vpRowItr = 0; vpRowItr < n; vpRowItr++) {
vp[vpRowItr] = readLine().split(' ').map(vpTemp => parseInt(vpTemp, 10));
}
let result = robot(vp);
ws.write(result + "\n");
ws.end();
}
Robot Python Solution
#!/bin/python3
import math
import os
import random
import re
import sys
def best_total_score(config):
N, V, P = config
routes = [(0, 0)]
for step in range(1, N):
if not routes:
print("all routes failed")
return None
this_score = V[step - 1]
this_energy = P[step-1]
if this_energy > 0:
all_max_score = max([route_max_score for (energy, route_max_score) in routes])
takeEnergy = (this_energy - 1, all_max_score)
newRoutes = [(energy - 1, route_max_score + this_score) for (energy, route_max_score) in routes if (energy > this_energy or (energy > 0 and route_max_score+this_score > all_max_score))]
newRoutes.append(takeEnergy)
else:
newRoutes = [(energy - 1, route_max_score + this_score) for (energy, route_max_score) in routes if energy > 0]
routes = newRoutes
this_score = V[N - 1]
return max(route_max_score for (energy, route_max_score) in routes) + this_score
def robot(vp):
N = len(vp)
V = []
P = []
for [vi, pi] in vp:
V.append(vi)
P.append(pi)
config = (N,V,P)
return best_total_score(config)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
vp = []
for _ in range(n):
vp.append(list(map(int, input().rstrip().split())))
result = robot(vp)
fptr.write(str(result) + '\n')
fptr.close()