Marathon Match 159

This match belongs to the Marathon Match Tournament 2025.

Important Links

• Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores.
• Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution.

Overview

You are playing a game of mini golf. You are given the playing field containing W ponds, the location of the ball and the starting location of A apples. You can hit the ball by specifying an angle $\alpha$ and distance $d$. Since there is wind and other external factors the ball will move with some variance. In particular, it will travel

• At an angle $\alpha' \sim \mathcal{N}(\alpha, \delta_1*d/D)$.
• With distance $d' \sim \mathcal{N}(d, \delta_2*d)$. $d'$ is then clipped to the range $[0, D]$.
• After travelling at an angle $\alpha'$ and distance $d'$ the location of the ball is rounded to the nearest integer.

Here $\mathcal{N}(\mu, \sigma)$ is the normal distribution with mean $\mu$ and standard deviation $\sigma$, $\delta_1$ and $\delta_2$ are two provided parameters and $D$ is the maximum possible distance of the playing field, set to 14142. These equations imply that the shot will become less accurate as the planned hit distance $d$ increases.

If the ball passes through an apple then you will collect 1000 points and that apple will spawn in a new location. You can collect multiple apples in one shot. If your ball hits a pond or goes out of the field then you will lose 10% of your score. Your task is to maximize your score in 1000 turns of the game.

Here is an example solution for seed=11. The ball is shown as a green circle, the apples are red circles, while the ponds are cyan polygons.

Input and Output

Initially your code will receive as input the following values, each on a separate line:

• A, the number of apples.
• W, the number of ponds.
• $\delta_1$, the parameter controlling the shot angle.
• $\delta_2$, the parameter controlling the shot distance.
• A lines representing the location of apples. Each line will be formated as "x y", indicating that there is an apple centered at location (x, y).
• W blocks describing ponds (polygons). Each block is formatted as:
  • n, the number of points in the polygon.
  • n lines represeting the points in the polygon. Each line will be formated as "x y", indicating that there is a points at location (x, y).
• A line representing the location of the ball, formatted as "x y", indicating that the centre of the ball is located at (x, y).

For each turn the game proceeds as follows:

• You output your move. This is either "-1" to terminate the simulation or "$\alpha$ $d$" to shoot at an angle $\alpha$ and distance $d$. $\alpha$ is in degrees in the range [0, 360] and $d$ is in the range $[0, D]$.
• The tester computes your shot based on the equations provided above and provides the following, each on a separate line:
  • Outcome of your shot. This is either "BAD" if you went out of bounds or hit a pond, or "GOOD" otherwise. If your shot was "BAD" then you lose 10% of your score and the ball returns to where it was hit from.
  • If the outcome was "GOOD" then print the new location of the ball, formatted as "x y", indicating that the center of the ball is now at location (x y).
  • If the outcome was "BAD" then print the location where the ball would have landed, formatted as "x y", indicating the center of the ball.
  • The total elapsed time.
  • If the shot was "GOOD" then the tester also checks whether you collected any apples. If you have then it gives you 1000 points for every apple collected and spawns them at new locations. It then outputs the following:
    • m, the number of apples collected.
    • m lines representing the new locations of the apples. This is formatted as "i x y", indicating that the center of the i-th apple (0-based) is now located at (x, y).

Coordinate system and dimensions

All coordinates are integers. The field is a square of length 10000. The top-left corner of the field is at location (0, 0), while the bottom-right corner is at location (9999, 9999). The y-coordinate increases as you go down.

All angles are in degrees. Angle 0 points towards East, while angle 90 points towards North (decreasing y-coordinate) and so on.

The radius of the ball is 150, while the radius of apples is 200.

Scoring

The raw score is the total points obtained from your sequence of moves. If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

• Using an invalid move format.
• Exceeding the time limit.

If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is YOUR/MAX, where YOUR is your raw score and MAX is the largest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalized to 100.

Test Case Generation

Please look at the generate() method in the visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

• The number of apples A is chosen between 1 and 5, inclusive.
• The number of ponds W is chosen between 3 and 15, inclusive.
• The $\delta_1$ parameter is chosen between 0 and 60, inclusive.
• The $\delta_2$ parameter is chosen between 0.05 and 0.2, inclusive.
• Generate the playing field. Place W ponds randomly, such that they don't overlap and leave a sufficient gap with the sides of the field for the ball to go through. Place A apples randomly, such that they don't overlap each other or the ponds. Place the ball, such that it doesn't overlap the apples or the ponds.
• All values are chosen uniformly at random.

Notes

• Please see the tester code for example implementation of collision detection.
  The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
• The compilation time limit is 30 seconds.
• There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
• The match is rated.

Languages Supported

C#, Java, C++ and Python

Submission Format

Your submission must be a single ZIP file not larger than 500 MB, with your source code only.
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as MiniGolf*.<appropriate extension>*

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions:

• Java Source Code - MiniGolf.java.zip
• C++ Source Code - MiniGolf.cpp.zip
• Python3.6 Source Code - MiniGolf.py.zip
• C# Source Code - MiniGolf.cs.zip

Tools

An offline tester is available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

Downloads

• Visualizer Source - tester.zip
• Visualizer Binary - tester.jar.zip

Offline Tester / Visualizer

Your solution should interact with the tester/visualizer by reading data from standard input and writing data to standard output.

To run the tester with your solution, you should run:

java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation.
If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\MiniGolf.exe" or "~/topcoder/MiniGolf".
In case your compiled solution is to be run with the help of an interpreter, for example, if your program is in Java, the command will be something like "java -cp C:\TopCoder MiniGolf".

Additionally you can use the following options:

• -seed <seed> Sets the seed used for test case generation, default is seed 1.
• -debug. Print debug information.
• -novis. Turns off visualisation.
• -pause. Starts the visualizer in paused mode. See more information below.
• -delay <delay> Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 1000.
• -manual. Play the game manually. Use the right mouse click to aim and the left mouse click to hit the ball.
• -showAttempt. Show the location that you were aiming at.
• -A <A> Sets a custom number of apples.
• -W <W> Sets a custom number of ponds.
• -delta1 <delta1> Sets a custom parameter $\delta_1$.
• -delta2 <delta2> Sets a custom parameter $\delta_2$.

The visualizer works in two modes. In regular mode, steps are visualized one after another with a delay specified with the -delay parameter. In paused mode, the next move will be visualized only when you press any key. The space key can be used to switch between regular and paused modes. The default starting mode is regular. You can use the -pause parameter to start in paused mode.

Marathon local testers have many useful options, including running a range of seeds with a single command, running more than one seed at time (multiple threads), controlling time limit, saving input/output/error and loading solution from a file. The usage of these options are described here.