Robot
Problem Statement :
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.
Constraints
1 <= N <= 5*10^5
0 <= Vi <= 10^9
0 <= Pi <- 10^5
Output Format
Derive the maximum score given by return (score);.
Solution :
Solution in C :
In C++ :
#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;
}
}
}
In Java :
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
public class Solution {
private static Reader in;
private static PrintWriter out;
public static void main(String[] args) throws IOException {
in = new Reader();
out = new PrintWriter(System.out, true);
int N = in.nextInt();
long[] V = new long[N + 1];
int[] P = new int[N + 1];
for (int i = 1; i <= N; i++) {
V[i] = in.nextInt();
P[i] = in.nextInt();
}
long[] dp = new long[N + 1];
long[] psum = new long[N + 1];
for (int i = 1; i <= N; i++)
psum[i] = psum[i - 1] + V[i];
dp[N] = V[N];
SegmentTree root = new SegmentTree(1, N);
root.update(N, dp[N] + psum[N - 1]);
for (int i = N - 1; i >= 1; i--) {
int zero = Math.min(N, i + P[i]);
dp[i] = zero > i ? (root.query(i + 1, zero) - psum[i]) : -(1l << 60);
root.update(i, dp[i] + psum[i - 1]);
}
out.println (dp[1]);
out.close();
System.exit(0);
}
static class SegmentTree {
public SegmentTree left, right;
public int start, end;
public long max;
public SegmentTree(int start, int end) {
this.start = start;
this.end = end;
if (start != end) {
int mid = (start + end) >> 1;
left = new SegmentTree(start, mid);
right = new SegmentTree(mid + 1, end);
}
}
public void update(int pos, long v) {
if (start == pos && end == pos) {
this.max = v;
return;
}
int mid = (start + end) >> 1;
if (mid >= pos) left.update(pos, v);
else right.update(pos, v);
max = Math.max(max, v);
}
public long query (int s, int e) {
if (start == s && end == e) {
return max;
}
int mid = (start + end) >> 1;
if (mid >= e) return left.query(s, e);
else if (mid < s) return right.query(s, e);
else return Math.max(left.query(s, mid), right.query(mid + 1, e));
}
}
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[1024];
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.')
while ((c = read()) >= '0' && c <= '9')
ret += (c - '0') / (div *= 10);
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
}
In C :
/*
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];
}
In Python3 :
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])
View More Similar Problems
Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →Palindromic Subsets
Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t
View Solution →