- 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.
OverviewEveryone loves pizza right? This is why you are making pizza for your friends. You have a circular pizza base with radius 100 and center (0,0). You have also prepared C circular ingredients (tomatoes, onions and salami) and R rectangular ingredients (pineapple and capsicum slices). Now you want to place some or all of the ingredients such that they cover as much of the base as possible. The ingredients cannot overlap each other and they cannot lie outside the base. In particular you want to maximize c + r - abs(X*c - (1-X)*r), where c is the total area of placed circles, r is the total area of placed rectangles and X is a provided coefficient that controls the balance between the two shape types.
Here is an example solution. x and y coordinates have the usual interpretation in this image - x increases from left to right, while y increases from bottom to top. The center of the base is located at (0,0).
InputYour code will receive as input the following values, each on a separate line:
- C, the number of circles.
- R, the number of rectangles.
- X coefficient.
- C lines, where the i-th line contains the integer radius of the i-th circle.
- R lines, where the k-th line describes the integer dimensions of the k-th rectangle, formatted as "width height" (without the quotes).
OutputYour code should write to output the following:
- On the first line, N = C+R, the total number of shapes.
- C lines, where the i-th line describes the i-th circle. If this circle is placed on the base then the line should be "x y" (without the quotes), where x and y are integer coordinates of the circle's center; otherwise it should be "NA".
- R lines, where the k-th line describes the k-th rectangle. If this rectangle is placed on the base then the line should be "x y" (without the quotes), where x and y are integer coordinates of the rectangle's bottom-left corner; otherwise it should be "NA".
ScoringThe scorer will compute the area covered by all the ingredients and obtain the raw score.
If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:
- Not returning exactly N = C+R shape locations.
- If the x or y coordinate of any ingredient is outside of the [-100, 100] range.
- If any part of an ingredient lies outside the pizza base.
- Using overlapping shapes.
- Using incorrectly formatted locations.
Test Case GenerationPlease 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 number of circles C is chosen between 10 and 500, inclusive.
- The number of rectangles R is chosen between 10 and 500, inclusive.
- The radius of each circle is an integer chosen between 5 and 15, inclusive.
- The height and width of each rectangle are integers chosen between 5 and 25, inclusive.
- The coefficient X is a double chosen between 0 and 1, inclusive.
- All values are chosen uniformly at random.
- All geometric calculations use an epsilon value of 1e-9. Please check the visualiser source code for the exact details.
- The pizza base will have a fixed radius of 100.
- The ingredients are allowed to touch each other and the boundary of the pizza base.
- 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 50 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
- The match is rated.
C#, Java, C++ and Python
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.
SAMPLE SUBMISSIONSHere are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions:
- Java Source Code - TastyPizza.java
- C++ Source Code - TastyPizza.cpp
- Python3.6 Source Code - TastyPizza.py
- C# Source Code - TastyPizza.cs
ToolsAn 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.
OFFLINE TESTER / VISUALIZERIn 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\TastyPizza.exe" or "~/topcoder/TastyPizza".
In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder TastyPizza".
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.
- -noimages Uses geometric shapes instead of images. This produces a more precise drawing of the pizza.
- -shownumbers This shows the id numbers of each shape.
- -C <C> Sets a custom number of circles.
- -R <R> Sets a custom number of rectangles.
- -X <X> Sets a custom coefficient.
Marathon local testers also have other 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 other options are described here.