Key Information

Register
Submit
The challenge is finished.
Show Deadlines

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
  • Sample Submissions/ Tester / Source Files are now also available in the Download Section on the top right. This section will only be visible once you have registered for the match.

Problem Statement

Compression systems deal with the art of storing data using less memory. In many cases, it is necessary to perfectly represent and extract the original data. In other cases, an imperfect representation may be acceptable. These are known as “lossless” and “lossy” methods.

In our problem, we are tasked with compressing a representation of several 2D rectangular grids of (‘A’-‘Z’) letters. The required output is a single, larger 2D grid of letters, and a list of row/column locations at which a (possibly imperfect) representation of each of the original grids can be extracted.

Scoring

The two components of score for a test case will be the output grid size (compression score), and overall lossiness of the compression. Compression score will be computed as (H * W / T), where H and W are the height and width of the output grid. T is the total sum of the 2D input grid areas. So a 5x8 output grid, with 3x8 and 5x6 input 2D grids, would score (5 * 8 / (3*8 + 5*6)) = 0.740740 for compression score.

Each sub-grid that is compressed will then be scored for lossiness based on how much each cell differs from the target value. The total lossiness score over all grids will be computed as Sum(d_i) / (12.5*T), where d_i is the absolute difference between the target value and the actual value of cell i.

For example, if the actual grid and the compressed grid were:

ABAC
CDBF

The d values would be 0 (‘A’ - ‘A’), 1 (‘B’ - ‘C’), 1 (‘C’ - ‘B’), and 2 (‘D’ - ‘F’), so the lossiness score would be (0 + 1 + 1 + 2) / (12.5*4) = 0.08.

The weighted sum of the compression score and the lossiness score is the raw score for this test case. The weight P is applied such that:

Raw score = compressionScore * P + lossinessScore * (1-P)

If your return was invalid then your raw score on this test case will be -1. Possible reasons include: invalid return data, time limit exceeded, out of memory, or any kind of runtime error.

If your raw score for a test case is negative then your normalized score for that test case is 0. Your normalized score for each test case is MIN/YOUR, where YOUR is your raw score and MIN is the lowest 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 normalised to 100.

Here is an example solution from the sample submissions for seed=1

Implementation

Your solution should read from stdin the following:

  • On the first line, the value P, the compression score weight.
  • On the second line, the value N, the number of grids to follow.
  • For each grid, you will then read in h, the number of rows in the grid, followed by h lines, each representing a row of the grid.

 

Your solution should output to stdout:

  • On the first line, H, the number of rows in your compressed grid.
  • H lines, each containing a row of the grid.
  • N lines, each containing the values <row> <col>, separated by a space, indicating the top left location (0-based) of where the originally provided grid has been compressed into the larger grid. Example "2 3" (without the quotes) for row 2, column 3.

 

Test Case Generation

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

  • N, the number of 2D grids, will be chosen, between 5 and 100, inclusive.
  • P, the compression score weight, between 0.05 and 0.95, inclusive.
  • For each grid, its width W and height H will be chosen between 2 and 10, inclusive.
  • For each cell of each grid, a letter (‘A’-‘Z’) will be chosen.
  • All selections are made 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.
  • 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 Lossy2dCompression.<appropriate extension>

Sample Submissions

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

 

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.

Here are example solutions for different languages, modified to be executed with the visualizer. (You will have access to the files, once you register for the match)

 

You may modify and submit these example solutions. You will have access to the files, once you register for the match.

 

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. To turn off visualization.
  • -seed <seed>. Sets the seed used for test case generation, default is seed 1.
  • -debug. Print debug information.
  • -size. Size in pixels of a cell when drawn.
  • -fullscreen. The window goes fullscreen.
  • -N XXX. Override N with the int value XXX.
  • -P YYY. Override P with the double value YYY.
Clicking on the window will step through each of the sub-grids placed and show you the lossiness error on the selected sub-grid. 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.

 

Payments

Topcoder will compensate members in accordance with our standard payment policies, unless otherwise specified in this challenge. For information on payment policies, setting up your profile to receive payments, and general payment questions, please refer to ‌Payment Policies and Instructions.