Register
Submit a solution
The challenge is finished.

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

A hidden 3-Dimensional surface has been created by the accumulation of E equations. Your task is to try and reconstruct this N by N surface as well as possible, while minimising the number of samples extracted from it. The surface is constructed by a set of randomly selected equations with randomly selected parameters. After all the cells have accumulated results from the equations, the surface is normalized such that the value of each cell falls within [0, 255].

You can perform a maximum of floor(N * N / 9) samples. For each sampling performed, you will receive the values of the hidden surface for a 3 by 3 subgrid centered at your sample location. If your sample location is (r, c), you will get the 9 values from cells (r-1, c-1) to (r+1, c+1) in row major order.

After you have sampled the surface for the desired number of times, you should predict the value of each cell of the surface. Your score will depend on the difference between the hidden surface and you predicted surface, as well as the number of samples performed. The normalized mean squared error between your predicted surface and the hidden surface will be multiplied by the weighting factor A and added to (1.0-A) multiplied by the fraction of available samples used.

Here is an example solution for seed=11 where one sample has been taken at the center of the surface.

Seed11 example

Input and Output

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

  • A, the weighting factor.
  • N, the size of the surface.

You then have the following options:

1.Perform a single sample.

  • Output the sampling location on a single line such as "r c" (without the quotes), where r is the row and c is the column of the center location of the sample. "0 0" is the top left coordinate. r and c should be within [1, N-2].
  • Read in 9 integers, each on their own separate line that will represent the 3 by 3 surface values surrounding the sampling location in row major order.
  • Read in a line that contains the remaining time left.
  • Perform another sample or stop sampling with the option below.

2.End sampling. You have finished taking samples and would like to predict the surface and stop execution. Output the following, each on a separate line:

  • "done", without the quotes.
  • N by N integer values in the range [0, 255] for the predicted surface, in row major order.

Scoring

The raw score is the normalized mean squared error between your predicted surface and the hidden surface will be multiplied by the weighting factor A and added to (1.0-A) multiplied by the fraction of available samples used. The raw score will then be scaled by 100000 for ease of readability.

Rawscore=100000((Amse/maxMSE)+(1.0A)(numSamples/maxSamples))Raw score = 100000 * ( (A*mse/maxMSE) + (1.0-A)*(numSamples/maxSamples) )

where maxMSE=6464maxMSE=64*64

maxSamples=floor(NN/9)maxSamples=floor(N*N/9)

mse=(x=0N1y=0N1(PredictedxyHiddenxy)2)/(NN)mse=(\sum_{x=0}^{N-1} \sum_{y=0}^{N-1} (Predicted_{xy}-Hidden_{xy})^2)/(N*N)

If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

  • Performing zero samples.
  • Performing more than the maximum number of samples floor(N * N / 9).
  • Predicting values outside the range of [0, 255].
  • Performing a sample that doesn't fit entirely on the surface.

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 MIN/YOUR, where YOUR is your raw score and MIN is the smallest 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 equations E is chosen between 2 and 30, inclusive.
  • The size of the surface N is chosen between 20 and 60, inclusive.
  • The weighting factor A is chosen between 0.2 and 0.8, inclusive.
  • For each equation E:
    • A type value is chosen between 0 and 10, inclusive.
    • The slope equation is added when the type is 0.
    • The Sin Cos equation is added when the type is 1.
    • The XOR equation is added when the type is 2.
    • Otherwise the XY^2 equation is added for values larger than 2.

Firstly, all the values of the SurfaceSurface is initialised to 0.
For each equation, random integer offsets are chosen between 0 and N, inclusive.

offx=randInt(0,N)offx = randInt(0,N)

offy=randInt(0,N)offy = randInt(0,N)

The slope equation:

Two random scaling parameters are chosen, between -10 and 10, inclusive.

s1=randDouble(10,10)s1 = randDouble(-10,10)

s2=randDouble(10,10)s2 = randDouble(-10,10)

For each cell in the grid, where x is the column and y is the row, the following equation is performed:

Surface(x,y)+=(xoffx)s1(yoffy)s2Surface(x,y) += (x-offx)*s1 - (y-offy)*s2

The SinCos equation:

Two random scaling parameters are chosen, between -0.4 and 0.4, inclusive.

s1=randDouble(0.4,0.4)s1 = randDouble(-0.4,0.4)

s2=randDouble(0.4,0.4)s2 = randDouble(-0.4,0.4)

A random amplitude parameter is chosen between 10 and 100, inclusive.

amp=randDouble(10,100)amp = randDouble(10,100)

For each cell in the grid, where x is the column and y is the row, the following equation is performed:

Surface(x,y)+=amp[Sin((xoffx)s1)+Cos((yoffy)s2)]Surface(x,y) += amp * [ Sin((x-offx)*s1) + Cos((y-offy)*s2) ]

The XY2 equation:

Two random scaling parameters are chosen, between 0.001 and 0.1, inclusive.

rx=randDouble(0.001,0.1)rx = randDouble(0.001,0.1)

ry=randDouble(0.001,0.1)ry = randDouble(0.001,0.1)

A random amplitude parameter is chosen between 10 and 100, inclusive.

amp=randDouble(10,100)amp = randDouble(10,100)

For each cell in the grid, where x is the column and y is the row, the following equation is performed:

Surface(x,y)+=ampexp((rx(xoffx)2+ry(yoffy)2))Surface(x,y) += amp * exp(-(rx*(x-offx)^2+ry*(y-offy)^2))

The XOR equation:

For each cell in the grid, where x is the column and y is the row, the following equation is performed:

Surface(x,y)+=(xoffx)XOR(yoffy)Surface(x,y) += (x-offx) XOR (y-offy)

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.
  • 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 SurfaceReconstruction*.<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:

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

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\SurfaceReconstruction.exe" or "~/topcoder/SurfaceReconstruction".
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 SurfaceReconstruction".

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 100.
  • -A <A> Sets a custom weighting factor.
  • -N <N> Sets a custom surface size.
  • -E <E> Sets a custom number of equations.

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. The replay function allows you to inspect the hidden surface, predicted surface and difference map by moving backwards or forwards after the run completed.

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.