That should have worked. I had used the same logic.
My complexity was coming out to be O(t*(5^(n-1))) [where t is the number
of test cases and n is the number of activities on his calendar ].
With small optimisations such as checking whether the given calculated
values of 'to spend energy' are valid or not, the code worked within the
time limit.
Also make sure ,that to get the maximum possible gain, the person has to
spend all the energy he gains , that is E+R*(N-1) = TOTAL .
So for n = 10 activities(worst case) , you only had to calculate the amount
of energy spent on the first 9 activities (x1,x2....x9). The energy spent
on the last one would be x10 = TOTAL - (x1+x2...+x9)
Another approach that I read in other codes was the use of dp.
(I am not sure if this works, please correct me if I am wrong)
Let F(n,l) be the gain after going through n activities with l amount of
energy left, then
F(n,l) = max{ F(n-1, l + used - R) + v[n-1]*used} over all values of 'used'
from 0 to e.
On Sun, Apr 28, 2013 at 8:56 PM, Vaibhav Tulsyan
<[email protected]>wrote:
> I tried to compute all possible gains, summed them, found the max. Worked
> too slow. Can you guys explain your methods?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
