Topcoder SRM 580; The one that made me feel stupid

So my second SRM with me being in DIV-1. And yet again I dropped to DIV-2. I focused on just the easy problem, and it *was* easy, but needed a bit clarity in thought. Alas I couldn’t solve it. Though my thought process was on the right lines, but not good enough.

DIV-1 Easy; EelAndRabbit:

You can choose any two time instants, on which your rabbit can capture all fish right infront of him (having any part coincide with the “x” position on which rabbit is standing). All fish move with same speed. Thus their formation will be same at any given moment in time. Thus you can easily transform the problem into choosing two positions over the X-axis for your rabbit, instead of two time instants.

But problem is, X-axis is comprised of real numbers. How can you choose two positions in this interval of real numbers? Let one of the two positions which will give us an optimal answer, to be ‘x’. While standing over ‘x’, lets say our rabbit can capture ‘y’ number of fish, that all intersect the vertical line that crosses the stream starting from position ‘x’. How far to the left, or right, can you move this vertical line, such that it still intersects with ‘y’ number of fish? If you drag it to the left, you can move till you touch the tail of any one of the ‘y’ fish. If you move any further, you will not hit this fish anymore, and thus your solution won’t be optimal. Same is the case if you move it to the right (you can go as long as the first fish whose head you hit).

Thus all you need to do is iterate over either all the tails, or heads, and select two of them which give you highest hits over the fish. There are at most 50 fish. Thus you can search over all possible pairs of tails (or heads), and select the pair that gives you highest fish.

Conclusion:

I liked this problem. And I hope to be back to DIV-1 soon.

Be Sociable, Share!

Leave a Reply