GCJ Manage Your Energy Problem with pieguy's submission

general
1

I was reading the submissions and came along a neat submission by the very own @pieguy (You know him, as he is setter of many problems in the Contests here at Codechef).

I am pasting the code snippets where I have doubt, if anyone or @pieguy himself can explain this, then it will really be helpful.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int E, R;
long long solve(int* start, int length, int se, int ee) {
   	if(length == 0)
    	return 0;
    long long pos = max_element(start, start+length) - start;
    long long ie = pos*R+se;
    if(ie > E)
    	ie=E;
    long long re = ee-(length-pos)*R;
    if(re < 0)
 		re=0;
    long long res=(ie-re)*start[pos];
    res+=solve(start, pos, se, ie);
    res+=solve(start+pos+1, length-pos-1, re+R, ee);
    return res;
}

int main(){
    int T;
    scanf("%d", &T);
    for(int t=1; t<=T; t++) {
    	int N, v[10000];
    	scanf("%d%d%d", &E, &R, &N);
	    for(int i=0; i<N; i++)
		    scanf("%d", v+i);
	    printf("Case #%d: %lld\n", t, solve(v, N, E, R));
    }
}

This was the solve() that he used, the intitial call was made by

solve(v, N, E, R)

For meaning of symbols refer to the [problem.][1]

v is the array to store each vi.

I did not understand the

ie = pos*R + se;

part, why is he multiplying regain amount to the position of the max element and then adding to the initial energy.
Again, while calculating re, he is doing something similar.

Please clarify this.
[1]: https://code.google.com/codejam/contest/2418487/dashboard#s=p1

1 Like
2

@bugkiller would need a little more code

but here is what i get from this…

he finds the position for the maximum element to make sure he has full E available for that task…
he is multiplying pos*R because he want to know how much energy is available till he reaches that position…

which will be E+pos*R … so pos*R is the energy he can use between 1st and max position task…
(amount of energy, R, the amount you regain after each activity)

1 Like
3

Edited, full code added.
How is the energy he can use between 1st and max position pos*R? Can you please explain the idea a bit in detail?

4

Problem statement:
you start with E amount of energy…
and you get R energy after doing every task…

the best way to maximize gain is to use maximum energy on most important task…

till he reach his most important task he will have R*pos energy from doing pos amount of tasks…
then he divide his problem into two halves
(1,max_pos) && (max_pos+1 N)

and the first half can use R*pos+E amount of energy where pos task will consume E energy

and second half can use R*(N-pos) amount of energy

1 Like
5

“the first half can use R*pos+E amount of energy where pos task will consume E energy” Is it always possible to spend E amount of energy to the max element? So should I assume that from elements 1 through pos, I am spending R amount of energy always and then spending E on the pos element, right?

6

yes because you start with E amount of energy so you can have E at any task position if you dont spend on any task