We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Either the pet will eat it or battle it.
Eating any mandragora wont make a difference since eating each mandragora increments S by 1.
So, after eating x mandragoras, it will battle the remaining mandragoras such that the value of P((x+1)*sum_of_remaining_mandragora_exp) is maximum.
Now you consider each case, where in you go on eating mandragoras one by one with least exp. points first and calculate the value P in each case. This value will increase till a particular point. After this, the value of P will start to decrease. (This is what @dongyaoli means by, "until it will cause the experience to decrease"). Once you reach this point, the maximum value of P is achieved and you need not check the rest of the cases.
your solution is so much confusing. could you please elaborate it more.
what do you mean by "Now you consider each casee, where in you go on eating mandeagora one by one with least exp. point firat and calculate the value of P in each case" ??
I also used this approach, my explanation in my words:
Sort the array.
Eat the monsters with the lowest health points first until a certain point X.
Why does this work? Consider the extreme cases:
a. We dont eat any monster: Then we only gain 1*(Health of all monsters) points.
b. We eat all monsters: Then we gain 0 points.
Now 3b. is bad. 0 points is not good. But can we do better than a? yes, by already eating one monster, we have 2 strength and gain in total 2*(Health of all monsters - the weakest monster we ate).
And so on... So you see that we improve by eating monsters. But can we improve forever? No! in 3b. we see that we gain 0 points when we eat all monsters. So the best solution is somewhere in the middle.
I am using pypy3 and the sort causes a timeout. All the other cases are accepted so my dozen lines of python are fine. I may try simply finding the highest n mandragons and increase the number until I pass. This is not a useful way to spend my time, unless I am in a contest and this is the final challenge. Switched from pypy3 to Python 3 and passed. Funny, pypy3 runs so much faster on my ancient laptop that I do not understand why Python 3 works faster on HackerRank.
10 seconds for python or python3, 3 seconds for pypy, 4 seconds for pypy3. I believe that during contests all 4 share the 10 second time out.
It's also possible, though unlikely, that the list of healths is being run in worst-case time for the sort algorithm that pypy is using and python is using a better choice for the given data set.
I know this is a late response, but I had a timeout issue in python2 following the same approach. It wasn't the sort; it was that I was recalculating sum(H[i:]) on each loop iteration instead of doing it once and subtracting the next term. ie: hs = sum(H); hs -= H[i-1] if i>0
can i please know how do you calculate the experience when you eat a mandragora and know if its increasing or decreasing?
my doubt is, if you eat the first mandragora your experience will be p=0 and strength becomes s=2, now in this case how do you calculate experience? and how do you compare?
am sorry, if my questions sounds dumb, i am an amatuer programmer. thanks in advance!
Even I was gettin the same error. For me it was because i didnt consider the case where all were defeated and none were eaten i.e. s=1 and experience = (sum of all h)*1
This is DP because the optimal solution builds on previously solved subproblems to build up the final solution.
This can not be considered Greedy because at any given point in the algorithm (including the one that some have proposed on this thread - sort the array, start with the smallest one and see when it starts decreasing...) you can't say authoritatively that this is the optimal answer at that point for that subproblem. It needs to be for it to conform to being a Greedy algorithm.
Agreed. The DP part of this problem is in how you store the sum of the health points of the mandragoras that you battle. You can simply decrement the amount as you go through the split points in the sorted list (or increment, depending on which way you're working), rather than recomputing the sum.
Sort the mandragoras
while (adding the largest mandragora remaining to the battled set does not decrease the score):
add the largest mandragora remaining to the battled set
return (sum of mandragoras in battled set) * (# of mandragoras not in battled set)
That's textbook greedy. And it doesn't have any repeated subproblems, so it's not DP (barring a definition where all iterative or recursive problems, i.e. all non-trivial problems, are DP).
Look how i use an arry to store the cummulative sum of the creature's HP after sorting. So while trying to find the break in the sorted array the remaining array's sum doesn't need to be calculatted each time. Thus call it uses both DP and Greedy :)
Mandragora Forest
You are viewing a single comment's thread. Return to all comments →
This should be greedy, not DP IMO.
Could you explain how. Dp seems right.
There exists an optimal solution: eat the next smallest one until it will cause the experience to decrease.
Yeah .I came up with a similar approach.
What do you mean with "until it will cause the experience to decrease." ?
I need more clarification. Thanks in advane :)
@Reeeeeeeeeee
Either the pet will eat it or battle it. Eating any mandragora wont make a difference since eating each mandragora increments S by 1.
So, after eating x mandragoras, it will battle the remaining mandragoras such that the value of P((x+1)*sum_of_remaining_mandragora_exp) is maximum.
Now you consider each case, where in you go on eating mandragoras one by one with least exp. points first and calculate the value P in each case. This value will increase till a particular point. After this, the value of P will start to decrease. (This is what @dongyaoli means by, "until it will cause the experience to decrease"). Once you reach this point, the maximum value of P is achieved and you need not check the rest of the cases.
I hope this helps.
your solution is so much confusing. could you please elaborate it more. what do you mean by "Now you consider each casee, where in you go on eating mandeagora one by one with least exp. point firat and calculate the value of P in each case" ??
I also used this approach, my explanation in my words:
Sort the array.
Eat the monsters with the lowest health points first until a certain point X.
Why does this work? Consider the extreme cases:
a. We dont eat any monster: Then we only gain 1*(Health of all monsters) points.
b. We eat all monsters: Then we gain 0 points.
Now 3b. is bad. 0 points is not good. But can we do better than a? yes, by already eating one monster, we have 2 strength and gain in total 2*(Health of all monsters - the weakest monster we ate).
And so on... So you see that we improve by eating monsters. But can we improve forever? No! in 3b. we see that we gain 0 points when we eat all monsters. So the best solution is somewhere in the middle.
I am using pypy3 and the sort causes a timeout. All the other cases are accepted so my dozen lines of python are fine. I may try simply finding the highest n mandragons and increase the number until I pass. This is not a useful way to spend my time, unless I am in a contest and this is the final challenge. Switched from pypy3 to Python 3 and passed. Funny, pypy3 runs so much faster on my ancient laptop that I do not understand why Python 3 works faster on HackerRank.
pypy3 is still faster (I assume). The time limits are lower for pypy than for python per https://www.hackerrank.com/environment
10 seconds for python or python3, 3 seconds for pypy, 4 seconds for pypy3. I believe that during contests all 4 share the 10 second time out.
It's also possible, though unlikely, that the list of healths is being run in worst-case time for the sort algorithm that pypy is using and python is using a better choice for the given data set.
I know this is a late response, but I had a timeout issue in python2 following the same approach. It wasn't the sort; it was that I was recalculating sum(H[i:]) on each loop iteration instead of doing it once and subtracting the next term. ie: hs = sum(H); hs -= H[i-1] if i>0
did you stop when the experience started to decrease..?
Yes, you can stop then. I did not prove it mathematically (which is bad, should do that as practice), but my feeling told me I can stop then.
Or in more correct, more general words: I assumed there is a global optimum.
can i please know how do you calculate the experience when you eat a mandragora and know if its increasing or decreasing?
my doubt is, if you eat the first mandragora your experience will be p=0 and strength becomes s=2, now in this case how do you calculate experience? and how do you compare?
am sorry, if my questions sounds dumb, i am an amatuer programmer. thanks in advance!
I didn't believe this at first, and was annoyed that noone gave a proof, so here.
Sort the mandradora by hp, from lowest to highest. Eat lowest hp mandradora first.
let exp(k) mean 'exp for eating the first k mandradora and battling the rest'
After eating the kth mandradora, the strength is (k+1).
exp(k) = exp(k-1) - hp(k)*k + sumhp(k+1...n);
lets assume that exp(k) < exp(k-1).
hp(k)*k > sumhp(k+1...n).
hp(k+1)*(k+1) > hp(k)*k.
sumhp(k+2...n) < sumhp(k+1...n).
therefore, hp(k+1)*(k+1) > sumhp(k+2...n)
exp(k+1) = exp(k) - hp(k+1)*(k+1) + sumhp(k+2...n) < exp(k).
Thank you for this clear and easy explanation.
I used the same algorithm but i am getting wrong answer in tc#2,3,4,5. can you help? here is my code: http://ideone.com/HqE3JC
Use long long int instead of int for the vars.
thanks. that's why I got all pass but #2
Even I was gettin the same error. For me it was because i didnt consider the case where all were defeated and none were eaten i.e. s=1 and experience = (sum of all h)*1
This is DP because the optimal solution builds on previously solved subproblems to build up the final solution.
This can not be considered Greedy because at any given point in the algorithm (including the one that some have proposed on this thread - sort the array, start with the smallest one and see when it starts decreasing...) you can't say authoritatively that this is the optimal answer at that point for that subproblem. It needs to be for it to conform to being a Greedy algorithm.
Agreed. The DP part of this problem is in how you store the sum of the health points of the mandragoras that you battle. You can simply decrement the amount as you go through the split points in the sorted list (or increment, depending on which way you're working), rather than recomputing the sum.
At its most basic, the algorithm is:
That's textbook greedy. And it doesn't have any repeated subproblems, so it's not DP (barring a definition where all iterative or recursive problems, i.e. all non-trivial problems, are DP).
Here is the heart of my logic
Look how i use an arry to store the cummulative sum of the creature's HP after sorting. So while trying to find the break in the sorted array the remaining array's sum doesn't need to be calculatted each time. Thus call it uses both DP and Greedy :)
No..... You will need to apply DP here as well. Otherwise most the test cases will fail. I used memorization and it helped.