Register
Submit a solution
The challenge is finished.

Challenge Overview

Important Links

  • Instant Leaderboard (The leaderboard on the submission tab and the leaderboard linked are now the same, however, there might still be some cache issues. Thus you can always refer to the leaderboard here.
  • 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 etc.  

Problem statement

Cover a NxN grid of numbers with non-overlapping polyominoes. A polyomino is a geometric shape composed of connected squares. In this problem we will consider polyominoes between 2 (dominoes) and 7 (heptominoes) squares in size. The score of each polyomino is the product of all the numbers that it covers. You task is to maximize the total score, which is the sum of all polyomino scores. Note that cells that remain uncovered receive a penalty of -1000.

Here is a solution for example 0 (seed=1) with N=8 and tiles=(4, 2, 3, 0, 4, 2). The coloured regions represent the chosen polyominoes. The white cells are those that have not been covered by a polyomino and receive a penalty score. Note that tiles with 5 squares cannot be used in this example. This solution obtains a raw score of 678799.

Implementation

Your code should implement a single method findSolution(int N, int[] grid, int[] tiles). The method should return an int[], where element i*N+k is the polyomino ID (positive integer) of the cell in row i and column k. Cells that are not covered by any polyomino should have ID=-1.

Scoring

Your raw score for a test case is the sum of all polyomino scores minus 1000 penalty points for each uncovered cell. If your return was invalid (incorrect number of elements, illegal characters used, multiple polyominoes with the same ID, too many polyominoes used, etc.) then your raw score on this test case will be -1.

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 raw score currently obtained on this test case (considering only the last submission from each competitor). The relative scores are summed and scaled to 100.0 to give your overall score.

Constraints

  • N is the size of the grid. It will be chosen randomly between 8 and 50.
  • grid is the NxN grid of numbers represented as an int[], where element i*N+k is the number of the cell in row i and column k. Each number is chosen randomly between -9 and 9.
  • tiles is the set of available polyominoes. It is represented as an int[] with 6 elements, where the i-th element corresponds to the number of available polyominoes of size i+2. Available polyominoes will cover exactly N*N cells.
  • All generated values are chosen uniformly at random.

Notes

  • The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
  • There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
  • 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 the following content:
Please Note: Please only zip both the files together. Do not put them inside a folder before zipping, you should directly select both the files and zip them.

-solution.sh 
Structure
#!/bin/sh
<Build Command> assume your submission is in /workdir/>      
echo '<Execution Command>' > /workdir/command.txt

Example
#!/bin/sh
javac /workdir/PolyominoCovering.java      
echo 'java -cp /workdir PolyominoCovering' > /workdir/command.txt

-Source Code 
PolyominoCovering.java

Sample Submissions

Tools

Submission format and an offline tester are 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

Helpful information

Offline Tester / Visualizer

In order to use the offline tester / visualizer tool for testing your solution locally, you'll have to modify your solution by adding the main method that interacts with the tester / visualizer via reading data from standard input and writing data to standard output. As long as you do not change the implementation of method findSolution, this doesn't affect the way your solution works when submitted to our server.

Here are example solutions for different languages, modified to be executed with visualizer. They all implement the same approach: greedily form rectangular polyominoes.
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\solution.exe" or "~/topcoder/solution". 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 Solution".

Additionally, you can use the following options:
  • -novis : Turn off visualization.
  • -debug : Print debug information.
  • -size : Use custom grid size.
Finally, you can print any debug information of your solution to standard error, and it will be forwarded to the standard out of the tester.
 

ID: 30100149