SNOOKER - Editorial ( NCC 2014 )

editorial
, , ,
1

PROBLEM LINK:

Contest

Practice

Author: Vaibhav Tulsyan, Aditya Sarode

Tester: Aditya Sarode

Editorialist: Aditya Sarode

DIFFICULTY:

MEDIUM

PROBLEM:

Given a snooker table with different points to its four sides find out the number of points obtained when the ball is projected from a corner at 45 degrees to its side. The ball travels distance X and whenever the ball hits a wall, the points increase by the points of the side. Find out the total points obtained in O(1)

EXPLANATION:

The ball travels X/sqrt(2) distance along the length and breadth of the table.
Let L = X/sqrt(2)
Now, we consider the collisions with the top and the bottom sides.
The ball will collide at the top and bottom sides after every M distance it travels along the vertical direction ( between top and bottom ).
Thus the total collisions with the top and the bottom combined will be floor(L/M)
Individual collisions of top and bottom can be found out by the fact that the ball will collide first with the top and then with the bottom and so on.

So either,
Number of collisions with top side = Number of collisions with bottom side
Or
Number of collisions with top side - 1 = Number of collisions with bottom side

Psudo code:


topAndBottomCollisions = X/M
leftAndRightCollisions = X/N

if topAndBottomCollisions is even:
	topCollisions = topAndBottomCollisions / 2
else:
	topCollisions = 1+topAndBottomCollisions / 2

bottom_collisions = topAndBottomCollisions / 2

if leftAndRightCollisions is even:
	rightCollisions = leftAndRightCollisions / 2
else:
	rightCollisions = 1+leftAndRightCollisions / 2

leftCollisions = leftAndRightCollisions / 2

answer = leftCollisions * L + rightCollisions * R + downCollisions * D + topCollisions* U

Complexity: O(1) for each of K tables

1 Like