StopFuture's blog

By StopFuture, history, 22 months ago, In English

Cute hamsters and an interesting problem ...

Hello everyone, I know that my rating does not inspire much confidence, but I'm sure that this will not be a reason to miss this blog.

I was faced with a problem from The 2010 All-Ukrainian Programming Contest, at the link you can find the condition and test your decisions for "Flight of the Hamsters".

A little below I will try to give a more formal condition and funny illustration.

Given a plane in which a certain number of vertical segments is given. The point object must be thrown at a certain angle to the horizon, and then calculate the maximum possible number of points at which the parabola of the object movement intersects with the segments.

Please do not consider it elementary until the moment of Accepted. I managed to come up with only a partial solution (82/100) , because I approached the problem from a physical point of view :)

Everyone knows that there are two independent movements on each of the axes, let's write simple formulas for this :  $$$x = v_0 * t * \ cos(\alpha) ;$$$ $$$y = v_0 * t * sin(\alpha) - \dfrac{g * t ^{2}}{2}$$$

Now let's make a small substitution and receive :

$$$y = x * \ tg(\alpha) - g * {\dfrac{x^2}{2 * v_0^2 \cos(\alpha)^2}}$$$

So, the condition of the problem does not say anything about the accuracy of the calculation, but the examples of input data make it clear that you need at least 6 decimal places to get the correct answer. Now we need iterate for everyone $$$ \alpha \in (0, \dfrac {\pi}{2})$$$ with step $$$10^{-6}$$$ radian. Next, for each x in which there is a vertical segment, we see if the object on it and increase the result.

However, this logic, unfortunately, does not give the maximum score: (I spent a lot of time trying to optimize or come up with a different approach to the problem, but all in vain ....

I would like someone to be interested in this problem, because I am very eager to understand what the right approach should be to tasks of this type.

Many thanks to everyone who read up to this point,I expect a certain positive reaction with an explanation, I hope it was not a waste of your time :)

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Compute for each gate the range(s) of angles such that the hamster will fly through it, and then find the value contained in the greatest number of ranges using a sweep line algorithm

»
22 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

There is a better way of solving this problem than to vary $$$\alpha$$$. The parabola is of the form $$$y = t x - k (t^2 + 1) x^2$$$ (here $$$t = \tan \alpha$$$ and $$$k = \frac{g}{2v_0^2} \ge 0$$$). Note that $$$\tan$$$ is a monotonic function on $$$[0, \frac{\pi}{2})$$$ (you might need to handle the case $$$\alpha = \frac{\pi}{2}$$$ separately).

Note that a parabola intersects with a line segment with $$$x = x_0$$$ and $$$y \in [y_1, y_2]$$$ iff $$$y_1 \le t x_0 - k (t^2 + 1) x_0^2 \le y_2$$$ has a solution. The inequality on the left has a solution (in $$$t$$$, and not $$$x_0$$$) that is either a single interval, a single point or empty, and the inequality on the right has a solution that is either two disjoint intervals, a single interval or empty. Finding the intersection of these intervals will lead us to at most two closed finite intervals (they can be degenerate intervals).

Now let's look at the problem in terms of $$$\tan \alpha$$$ rather than $$$\alpha$$$. The problem becomes: given a set of $$$N$$$ intervals, find a point common to the largest number of intervals. Now doing this is quite standard and simple (modulo floating point errors): perform coordinate compression and consider every endpoint of an interval (it can be shown that there is an optimal solution where the point chosen is an endpoint of an interval), and maintain which intervals are covered and which aren't. This can be done in $$$O(n \log n)$$$.