SPOJ: The Ball

source: http://www.spoj.com/problems/BALL/
please help me to solve this problem.

The problem is quite easy… The Algorithm is as follows

  • the direction of first belt can be determined from the difference bet. the max value of x-coordinates below it
  • the belt just above the ground can be in any direction
  • now, for each ball check (its x-coordinate) whether lying in within the belt’s limit from top to bottom.
  • if it lies within a belt’s limit then change the ball’s x-coordinate to the belt’s limit according to the direction of the belt.
  • again repeat step 3 and 4 until the loop exceeds the N value.
  • Using a counter variable count the no. of belts it has touched(i.e no. of times the ball x-coordinate has been changed)
  • value of the counter variable is the required answer…

Hope this algorithm works… I’m not sure whether there exist any efficient algorithm for this problem…
Happy Coding… :slight_smile:

If you look carefully, each belt when going left or right is connected to exactly one belt(i.e. the ball can land on exactly one belt). So this is a binary tree (or forest), and you need to find the maximum height of it. So you need to figure out which belt the ball falls on, then your answer max(leftTreeHeight,rightTreeHeight). The tough part in this question is figuring out what is the next belt the ball hits going left or right, although I’m sure you can manage it.( hint : sort by y, then search for the next belt who’s x1 <= x1’ <=x2 (x1’ being the current belt’s x1 or x2).

looking at the constraints…i think that this algo will give a TLE verdict!!!