JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: SFFCompression
Problem: SFFCompression

Problem Statement

    In this problem you will need to implement a compression/decompression routine for Standard Flowgram Files (SFF) that has both high compression speed and good compression ratio. The format of an SFF file is explained in details here. We provide 40 examples of SFF files, you can download them here.



You will need to implement two methods: compress and decompress. The int[] data in compress method provides the contents of an SFF file as follows. The file is considered to be a binary file, i.e. a sequence of bytes. It is divided into quadruples of consecutive bytes: the first quadruple contains first 4 bytes of the file, the next quadruple contains next 4 bytes and so on. For each quadruple (A, B, C, D), the integer res = (A<<24) + (B<<16) + (C<<8) + D is calculated. (Here, each of A, B, C, D is assumed to be a 32-bit signed integer containing a value in 0..255. res is also assumed to be a 32-bit signed integer. For example, A = 128, B = 0, C = 0, D = 128 produces res = -2,147,483,520 because 128<<24 = -2^31.) These integers are put into data in the same order as quadruples follow within the input file. Your implementation of compress should return the compressed variant of data as int[].



The return value of compress method will then be provided as data to your decompress method. It should decompress the data back and return the result as int[]. This int[] must be absolutely the same as the int[] provided to compress method, i.e., your compression/decompression routine must be lossless.



The score for a test case is calculated as follows. If the result of decompression is not the same as input data, the score is 0. Otherwise, the score is max{0, (uncompressed_size - compressed_size) / 163.84 - time * 0.6}, where time is the total execution time of both compress and decompress methods (in milliseconds), uncompressed_size is the amount of elements in data provided to compress method and compressed_size is the amount of elements in the return value of compress method. Your overall score is just the sum of your scores over all test cases.



It is known that there are 5 different kinds of SFF files in the test data. Files of the same kind are expected to be similar to each other, files of different kinds can be less similar. The size of each file (disregarding of the kind) will always be between 84 and 100 megabytes. Below you can find additional information on presence of each kind of files in the test data:
| Kind of files | Example tests | Submission tests | System tests | File numbers (among 40 examples that we provide |
|             1 |             1 |                1 |            2 |                                             1-2 |
|             2 |             1 |                2 |            4 |                                             6-9 |
|             3 |             1 |                4 |            8 |                                           16-23 |
|             4 |             1 |                6 |           12 |                                           36-47 |
|             5 |             1 |                7 |           14 |                                           66-79 |


As follows from the table above, there are 5 example test cases, 20 submission test cases and 40 system test cases. Example test cases will reuse files from 40 provided examples.



Special conditions



In order to receive the prize money, you will need to provide a description of how your solution works. Note that this description should not be submitted anywhere during the coding phase. Instead, if you win a prize, a TopCoder representative will contact you directly in order to collect this data.



Due to the way the TopCoder Marathon Framework is currently organized, both compress and decompress will be called on the same instance of SFFCompression class. However, since in practice compression and decompression happens independently, your implementations of compress and decompress must be independent. In other words, the result and the runtime of calling compress and then decompress on the same instance needs to be the same as the result and the runtime of calling compress on one instance and then decompress on another instance (without any data shared between instances except the compressed version of the file). This condition must be fulfilled for all your submissions (not only for the last one). We will monitor submissions regularly and reserve the right to disqualify the violating competitors from the match (and in some cases even to ban the TopCoder accounts of such competitors).
 

Definition

    
Class:SFFCompression
Method:compress
Parameters:int[]
Returns:int[]
Method signature:int[] compress(int[] data)
 
Method:decompress
Parameters:int[]
Returns:int[]
Method signature:int[] decompress(int[] data)
(be sure your methods are public)
    
 

Notes

-The allowed programming languages in this competition are C++, Java, C# and VB. Python submissions are not allowed.
-The time limit is 150 seconds per test cases. The memory limit is 2 gigabytes.
-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.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-The processing server specifications can be found here.
 

Examples

0)
    
1.sff
1)
    
6.sff
2)
    
16.sff
3)
    
36.sff
4)
    
66.sff

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.