JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 20
Problem: ImageReconstruction

Problem Statement

    

Your job is to unscramble a photograph in the fewest number of iterations possible.

The image is divided up into uniformly-sized square pieces and the pieces are shuffled. Your method will be provided with the size of each piece in pixels (the width and height are the same), the number of columns and rows of pieces in the image, and an array of pixel values. Each pixel value is encoded as an integer with eight bits per color component in RGB order, from most significant to least significant. You can decode each pixel with int red = (pixel >> 16), green = (pixel >> 8) & 0xff, blue = pixel & 0xff;.

Pieces are numbered from zero to rows*columns-1. Given a piece n, the image data for that piece can be found in row-major order in the pixels array starting at n*pieceSize*pieceSize. You can extract the pixel value at line y and column x of piece n with the expression pixels[n*pieceSize*pieceSize+y*pieceSize+x].

You are provided with a verify method which tells you which pieces are in the correct places in a guess. You pass it an array containing rows*columns integers, each of which represents a slot in the image in row major order so that the guess for the slot at row r and column c is at r*columns+c. Each slot should contain a piece number as described above. The method returns a corresponding array of integers. If the guess for a particular slot is correct, the corresponding return slot will be 1; otherwise, it will be 0. This means that it is possible to create the correct image without looking at the pixel data.

Your solution must return a guess in the same format as would be passed to the verify method. Your raw score for each case will be 1 plus the number of calls made to verify, or zero if your solution does not return the pieces in the correct order. Your aggregated score will be the sum of the lowest raw score received by any competitor on a case divided by your score on the case, excluding any cases in which you received a raw zero.

Visualizer

As in past contests, we have provided a Java visualization tool .
 

Definition

    
Class:ImageReconstruction
Method:reconstruct
Parameters:int, int, int, int[]
Returns:int[]
Method signature:int[] reconstruct(int pieceSize, int columns, int rows, int[] pixels)
(be sure your method is public)
 

Available Libraries

    
Class:Toolkit
Method:verify
Parameters:int[]
Returns:int[]
Sample Call:val = Toolkit.verify(pieceLocations);
    
 

Notes

-You have 60 seconds per case.
-You can use a maximum of 512M of memory.
-Test cases are chosen using http://commons.wikimedia.org/wiki/Special:Random/Image . Images which are not primarily photographic or photo-realistic, such as line drawings, are discarded.
-Images are centered and cropped after any scaling to make each image dimension a multiple of the piece size.
-As is customary, row (or line) 0 is the top.
-verify does not require each slot to be filled with a unique piece number. You can pass all zeros, for example.
 

Constraints

-pieceSize will be 10, 20, or 30, chosen uniformly at random
-neither image dimension will be more than 500 pixels - larger images will be scaled so that the larger dimension becomes 500
 

Examples

0)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Chemical_Brothers_Live.jpg
  Piece Size: 20x20
     Columns: 25
        Rows: 18
        Seed: 23784

1)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Flickr_hellochris_202508906--In-N-Out_triple_cheeseburger_fries.jpg
  Piece Size: 30x30
     Columns: 16
        Rows: 12
        Seed: 27360

2)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Tienen_Stadhuis.jpg
  Piece Size: 30x30
     Columns: 16
        Rows: 11
        Seed: 9981

3)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Todaiji05s3200.jpg
  Piece Size: 30x30
     Columns: 11
        Rows: 16
        Seed: 6231

4)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:800px-Kalithea_Achaias.jpg
  Piece Size: 20x20
     Columns: 24
        Rows: 15
        Seed: 20710

5)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Passower_Kirche.JPG
  Piece Size: 30x30
     Columns: 16
        Rows: 12
        Seed: 32464

6)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Wawer.jpg
  Piece Size: 30x30
     Columns: 12
        Rows: 16
        Seed: 10059

7)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Eisenbahnmarkthalle5_Detail_Berlin.JPG
  Piece Size: 10x10
     Columns: 32
        Rows: 50
        Seed: 21813

8)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Teplice%2C_Prosetice%2C_14Tr_III.JPG
  Piece Size: 20x20
     Columns: 25
        Rows: 16
        Seed: 23572

9)
    
   Image URL: http://commons.wikimedia.org/wiki/Image:Woody_London.jpg
  Piece Size: 20x20
     Columns: 24
        Rows: 15
        Seed: 26240


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.