Key Information

Register
Submit
Competition Timeline

Timezone:Etc/UTC

Registration

Starts

Jan 04, 2022

18:04

Ends

Jan 19, 2022

18:05

Submission

Starts

Jan 04, 2022

18:09

Ends

Jan 19, 2022

18:15

Winners Announced

Jan 21, 2022

18:17

Challenge Overview

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 an abstract game with B bouncing balls on a NxN grid. Each ball is fired from a gun located on the edge of the grid. The ball will travel in a straight line until it hits a diagonal panel, at which point it will bounce at a right angle and continue its journey. Some panels are provided to you, while other panels you can place yourself. If the ball hits one of the panels that you placed then it will spin it around by 90 degrees; otherwise if the ball hits one of the provided panels then the panel will stay fixed. If two or more balls hit a panel at the same time then it will not spin around. When a ball hits a panel you receive 1 point. Some cells will also contain a bonus. When a ball passes through a bonus cell you receive bonusValue points. The bonus cell will remain for the entire game and can be collected multiple times. The game continues until one of the balls exits the grid.

Initially you will be given a grid partially filled with fixed panels and bonus cells. Your task is to place the guns and additional rotating panels in order to maximize the number of points scored during the game.

Here is an example solution for seed=1. The provided fixed panels and bonus cells are shown in magenta.

seed 1 example

Input and Output

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

  • N, the grid size.
  • B, the number of balls.
  • bonusValue, the value of the bonus cell.
  • N*N lines representing the initial grid in row-major order. Each cell is either empty ('.'), a North-East panel ('/'), a North-West panel ('\') or a bonus ('*').

Your code needs to output the following, each on a separate line:

  • B lines representing the locations of guns. Each line should be formatted as "row column", without the quotes. The North edge should have row=-1, the East edge should have column=N, the South edge should have row=N and the West edge should have column=-1.
  • N*N lines representing the output grid in row-major order. Each cell is either empty ('.'), a North-East panel ('/'), a North-West panel ('\') or a bonus ('*'). Note you cannot place any additional bonuses.

Scoring

The raw score is the total number of points you received during the game. If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

  • Invalid or repeated gun locations.
  • Invalid output grid cells or overwriting the non-empty input grid cells.
  • Placing additional bonuses.
  • 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 visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

  • The grid size N is chosen between 6 and 30, inclusive.
  • The number of balls B is chosen between 1 and 5, inclusive.
  • The value of the bonus cell bonusValue is chosen between 2 and N, inclusive.
  • The number of bonus cells numBonus is chosen between 2 and N, inclusive.
  • The number of fixed panels numFixed is chosen between 2 and N, inclusive.
  • The grid is filled randomly such that it contains numFixed panels and numBonus bonus cells. The two panel types are chosen with equal likelihood.
  • All values are chosen uniformly at random.

Notes

  • If two or more balls hit a panel at the same time then it will not spin around.
  • Balls travel directly through each other without interacting.
  • You cannot place any additional bonuses.
  • 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 BouncingBalls.<appropriate extension>

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. Note that this solution does not produce a valid final answer. You may modify and submit these example solutions:

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

Offline Tester / Visualizer

In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to include in your solution the main method that interacts with the tester/visualizer via 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\BouncingBalls.exe" or "~/topcoder/BouncingBalls". In case your compiled solution is to be run with the help of an interpreter, for example, if you program is in Java, the command will be something like "java -cp C:\TopCoder BouncingBalls".

Additionally you can use the following options:

  • -seed <seed> Sets the seed used for test case generation, default is seed 1.
  • -showPaths. Shows the paths that the balls travelled.
  • -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 100.
  • -N <N> Sets a custom grid size.
  • -B <B> Sets a custom number of balls.
  • -bonusValue <bonusValue> Sets a custom value of the bonus cells.
  • -numBonus <numBonus> Sets a custom number of bonus cells.
  • -numFixed <numFixed> Sets a custom number of fixed panels.

The marathon local tester has recently been upgraded to include a replay functionality. You can read more about it here.

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.