Problem Statement |
| | In this problem you will control the bouncing of a ball by placing obstacles. The objective is to hit a number of targets in the shortest possible time while using as few obstacles as possible.
Simulation Details
The ball moves in a two-dimensional vertical plane under the influence of a constant gravitational force, which yields y-acceleration of -10 units/second2.
The plane is bounded with 4 obstacles: (0,0)-(500,0) for the "floor", (0,0)-(0,500) and (500,0)-(500,500) for the "walls" and (0,500)-(500,500) for the "ceiling".
The initial velocity of the ball is (0,0). The movement of the ball is simulated by repeatedly finding the next obstacle that will be intersected by its trajectory. The point of intersection and velocity at the moment of intersection vi are calculated. Then the velocity after bounce is calculated as vb = vt -0.99 * vn,
where vt and vn are
tangential and normal components
of vi to the surface of the obstacle. Thus, the tangential component remains unchanged while the normal component is reversed and dampened.
The simulation stops after 500 seconds or immediately after all the targets are hit.
Implementation Details
Your code should implement one method placeObstacles(int[] objectX, int[] objectY, int R). Elements 0 of objectX and objectY give you the initial x- and y-coordinates of the ball, while the rest of the elements give you x- and y-coordinates of the targets. R is the radius of the targets.
You must return a list of the obstacles to be placed on the plane. Each element of your return should be formatted as "X1 Y1 X2 Y2", and the corresponding obstacle is a linear segment with endpoints in (X1, Y1) and (X2, Y2). You may place at most 100 obstacles. All coordinates must be integral. x- and y-coordinates of the endpoints must be between 1 and 499, inclusive. Endpoints of one obstacle must be distinct. Obstacles may not intersect (or overlap).
Scoring
Your score for a test case will be HIT_BONUS * 0.995TIME * 0.9SEGMENTS, where
-
if the ball has hit all the targets, HIT_BONUS is equal to 2; otherwise it is the number of targets the ball has hit divided by the total number of targets,
-
TIME is the time of simulation. If the ball has hit all the targets, this is the moment of the last target hit, otherwise this is 500.
-
SEGMENTS is the total number of placed obstacles.
An invalid return of any kind will result in zero absolute score for that test case.
Your overall score will be the sum of YOUR/MAX over all test cases, where YOUR is your score and MAX is the maximal score achieved by anyone on that test case.
Test Case Generation
The number of targets is chosen between 10 and 60, and target radius R is chosen between 5 and 10. For each target, its x-coordinate is chosen between R and 500-R, and its y-coordinate is chosen between R and 490-R. Finally, initial x-coordinate of the ball is chosen between R and 500-R, and initial y-coordinate of the ball is 490.
Visualizer
A visualizer is available for offline testing.
Physics Details
When unhindered, the ball follows a trajectory defined by its current location and its current velocity. If it is at (x,y) with velocity (x',y') then t seconds later it will be at (x+t x',y+t y' - 5 t2) and have velocity (x',y'-10 t). An obstacle is a line which may be defined by an equation A x + B y = C (coefficients A, B and C can be calculated from the coordinates of the obstacle's endpoints). Using these equations in concert, we can solve for t, the time at which the ball intersects the line. It is possible to have two solutions, in which case we use the smallest positive one
which keeps the intersection point within the segment. Of all the obstacles the ball would hit on its path, we are interested only in the one it hits earliest. Once we have solved for t, we can find the exact location and velocity of the ball at the moment of the bounce. Finally, we compute the tangential and normal components of velocity, and reflect the normal one multiplying it by the dampening factor of 0.99.
A target of radius R centered at (x0,y0) is represented by an equation (x-x0)2+(y-y0)2 = R2. We cannot easily solve for t in closed form this time. Thus,
we use Newton's method
to find the time at which the ball will first pass at distance R to the point (x0,y0).
|
| |
Definition |
| | | Class: | BounceOff | | Method: | placeObstacles | | Parameters: | int[], int[], int | | Returns: | String[] | | Method signature: | String[] placeObstacles(int[] objectX, int[] objectY, int R) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Targets are not material and thus don't interact with the ball. |
| - | The ball is a point, with no extent, and the obstacles are lines with no width. If the ball hits the end of the segment, it will typically be considered to have bounced off the segment (see next note though). |
| - | Floating point numbers are used to perform the simulation. |
| - | If the ball's speed drops below 1E-6 after hitting the same obstacle twice in a row, or the ball bounces 100,000 times, the simulation will be considered stalled and will stop. |
| - | Using parts of the visualizer source code in your solution is allowed. |
| - | For more implementation details see the visualizer source. |
| - | The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code). |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
Number of targets = 11
R = 8
" | |
|
| 1) | |
| | | Returns: "seed = 2
Number of targets = 34
R = 5
" | |
|
| 2) | |
| | | Returns: "seed = 3
Number of targets = 47
R = 5
" | |
|
| 3) | |
| | | Returns: "seed = 4
Number of targets = 34
R = 5
" | |
|
| 4) | |
| | | Returns: "seed = 5
Number of targets = 45
R = 8
" | |
|
| 5) | |
| | | Returns: "seed = 6
Number of targets = 52
R = 8
" | |
|
| 6) | |
| | | Returns: "seed = 7
Number of targets = 52
R = 7
" | |
|
| 7) | |
| | | Returns: "seed = 8
Number of targets = 47
R = 5
" | |
|
| 8) | |
| | | Returns: "seed = 9
Number of targets = 41
R = 8
" | |
|
| 9) | |
| | | Returns: "seed = 10
Number of targets = 29
R = 9
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.