Hi. Recently, I decided to understand and solve some high quality problems which are a little above my level. So, I decided to start off with topcoder div1 500s. This is the first problem I picked, but unfortunately, it had no editorial. I searched over the internet and found an explanation in chinese here. I tried translating it, but the translated version was incomprehensible to me, because of the jumbled words ( and also my current level ). But I am determined to understand and solve the Div1 500s. So, I will be very thankful to you, if you could help me get started by providing an overview of the approach used to solve this problem. Thanks. Here is a link to the problem: Problem
It's easy to think of a solution that binary search the answer, so we can use an algorithm of O(nlogn) to verify the correctness of the answer.
Yes, I got the idea about binary search, and in the chinese blog I mentioned, I still was not able to figure out how to check whether a given value of additional boost given to the missile can be verified as being the answer or not. Will be really helpful, if you can describe how to verify the correctness.
Maybe my solution will help you?
I believe the code is pretty clear , if you still dont get it , ask , but try to imagine the whole problem pictorically , that is view every attack as a "blast" that covers some part of the coordinate plane and try to imagine how to iterations are done..
In your code, in the while loop at line 20, you're not updating the value of either i or j (I think that's a slight mistake). But anyways, I'll seriously appreciate if you could provide me a brief explanation of how the while loop at line 16 is working. I read a similar sort of loop in the chinese blog but was not able to figure out how it was working. Thanks.
Oooops my bad, sorry there should be a j++ there, updated code
Loop at line 16:
Basically , we are traversing from the back , the planet with the highest 'x' coordinate first and then the lower ones... Consider the first element in our vector 'v' .. it has the highest 'x' coordinate .. in order to destroy it .. we need to either deploy a missile directly to this position.. OR .. deploy a missile so some position whose 'x' coordinante is at most at a distance of 'x' to it...
Consider all the elements in the vector 'v' whose 'x' coordinate are at most at a difference of 'T' from the 1st (largest x coordinate) planet .. the greedy argument here is that WE MUST ALWAYS CHOSE some planet whose 'y' coordinate is the highest..
WHY?
Because since the point we just considered were no far than the 1st element of vector by 'T' then attack on the one with the highest height would destroy the 1st element , all the elements that we just iterated over , (in line 16) and since the array is sorted in a reverse order , all the upcoming elements will have x coordinate smaller than what we have seen now , and some of them will also be destroyed because we chose our height to be the maximum!
Hope this helps, please read it more than once if necessary, and experiment a little yourself to get an idea of solution!
Thanks a lot for the clear explanation and also for helping me solve my first div1 500 problem. But I know I will have to practice harder to be able to come up with the solutions for these problems on my own. I'll try my best. Thanks a lot once again. :)