BILLRD Help

help
1

code: CodeChef: Practical coding for everyone

can someone please give a brief idea about the concept used in this problem of the January long challenge?
I tried so many times but got no luck!

2

Some points to note:

  1. The ball is initially shot at 45 deg along the horizontal axis.
  2. Angle of incidence is equal to the angle of reflection.
  3. The table is square.

So, every time the ball hits a corner it gets reflected at 45 deg angle with respect to that axis.

Think of the table like a grid or a matrix.
Now, Let’s understand how we can find the first point of collision:

Eg:
Let’s say we have a 5*5 matrix.
The ball is initially at position (3,1).
Think about what will be the next coordinate our ball will be in the matrix after (3,1). Since it moves at an angle of 45 deg, the next coordinate will be (4,2).

Because If the angle is 0 deg, it moves in the same axis which will lead us to (4,1), or if the angle is 90 deg, it moves in the opposite axis which will lead us to (3,2) so 45 deg angle will lead us to (4,2).
Simply put , line which passes through the point a a angle of 45 deg has slope 1 which is calculated by tan(45 deg).
So,now we know our slope is 1, which means if x increases by 1 y also increases by 1. The point of first collision will be the point when x or y reaches n (5 in our case) . The path will be,
(3,1) → (4,2) → (5,3).

To find out the point of second collision,
we need to know on which side of the matrix ,the first collision occurred.
It either has to be top(if y reaches 5 ) or right(x reaches 5).
In our case the first collision is on the right because(x reaches 5).

if the first collision is on the right then the second collision will be in the top, or if the first collision is in the top ,the second collision will be in the right.

In general, if first collision is on right side ,the ball travels in anti clock wise direction (right-top-left-bottom) or if it collides on top ,it travels in clock wise direction(top-right-bottom-left).

It can also be easily seen that the ball travels in the same path. so it can only hit four different points in the corners.

So there are three main cases,
if (x,y) is the initial point and n is the size of the board:

  1. x=y:
    It will lead to the corner (n,n) since the slope is 1.It doesn’t move further so ans will be (n,n).

  2. x<y :
    first collision will happen at the top.(It can be understood in comparison with the first condition)

  3. x>y:
    first collision will happen at the right.(It also can be understood in comparison with the first condition)

We will have two different lines with slope 1 wrt to the x-axis.
left and the top points will make a line.
bottom and the right points will make a line.
Depending upon the point of the first collision, we can identify the order of the points.

we know the initial point and the slope, if we apply it in the equation of a line (y-y1=m(x-x1))we can get two points. To find out the other two points, we take the first two points and slope as -1(since we will be calculating wrt to the y-axis) and apply it in the equation of the line.

depending upon case 2 or 3 we need to choose the x and y values differently to denote one end of the matrix.

Finally, we can take mod 4 of the no of collisions to find out the point within the 4 calculated points.

My Solution: CodeChef: Practical coding for everyone

1 Like
3

Perhaps seeing the video editorial might help.

1 Like
4

Thanks for the explanation.

5

Thanks, got it now.