JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 104
Problem: TypesetterArt

Problem Statement

    

Introduction

NOTE:This match will be unrated and won't be a part TCO19 Marathon Competion.Learn More

You are given a typesetter and a set of 4 colored tapes for it – cyan, magenta, yellow and black. The typesetter has a feature of altering the font and its size, by replacing the letters. The replacement procedure takes time and you can apply it limited number of times

The task you are asked to implement is to paint an image by using the typesetter and paper.

You are given a reference image that you are going to reproduce. The idea is to type a number of layers, one on top of another, so that the resulting image is as close as possible to the reference image.

Technical Details

First, your solution is initialized. This is done by calling init method. The signature is as follows:

int init(int nRenders, int nFonts, int precision, int width, int height, int[] image)

  • nRenders is the number of times you can setup the typesetter font.
  • nFonts is the total available amount of fonts available.
  • precision is the size of window that will be used for scoring the output.
  • width is the width of input image; it equals the size of the paper you have.
  • height is the height of input image; it equals to the size of paper you have.
  • image is a flattened 3-dimensional array that encodes the 4 layers of the 2D image. See implementation for details, or use the demo solutions to decode it.
  • The return can be any integer, for instance 0.

Next, a method nextGlyph is called until it returns an empty array. The purpose of it is to retrieve the available font letter images. Each next call to the method receives the information about the letter requested during the previous call. The first call gets dummy parameters. The signature is:

int[] nextGlyph(int width, int height, int[] bitmask, int remainingMillis)

  • width is the width of the letter requested on the previous call to this method.
  • height is the height.
  • bitmask encodes the letter image. To save the bandwidth and minimize latency, it is a bitmask with 1-s representing ON pixels (you chose the color later) and 0-s representing OFF pixels (not painted). The bitmask is aligned to 32 bits. You can use the following code to extract the letter image:
    int rowLength = (width + 31) / 32;
    for (int k = 0; k < bitmask.length; k++) {
    	int x = bitmask[k];
    	int left = (k % rowLength) * 32;
    	int row = k / rowLength;
    	for (int m = 0; m < 32 && left + m < width; m++) {
    		if ((x & (1 << m)) != 0) {
    			// The pixel[row][left + m] is SET if this condition is true, otherwise UNSET.
    		}
    	}
    }
  • remainingMillis is the remaning time (in ms) as measured by the external tester and that is used for timeout condition. Note that this value may not match with your solution's time measurements.

The return from this method should be formatted as follows:

  • In case you don't need any more letters, return an empty (0-size) array.
  • Otherwise, it must have 3 elements:
    • letterId, the ASCII code of letter you want to receive next time; accepted codes are [32..126].
    • fontId, the ID of font; accepted values are [0..nFonts-1].
    • sizeId, the size of font letters; accepted values are [8..72].

It is suggested that you implement a state machine to match requested and received letters.

Finally, a method render is called for nRenders times. You received the value of nRenders from init(). This method should contain the core of your logic that attempts to replicate the image. The signature is:

int[] render(int iteration, int remainingMillis)

  • iteration is the ID of render iteration, starting with 0.
  • reminaingMillis is the same as in nextGlyph.
  • The return value, called ret must be formatted as follows:
    • ret[0] is the fontId you decided to use for this layer.
    • ret[1] is the letter size.
    • ret[2] is one of the 4 ink colors (cyan=0, magenta=1, yellow=2, black=3).
    • ret[3] is saturation value of the ink.
    • the next items of the array should represent ASCII codes of the letters you decided to print on this layer. Available codes are [32..126] and 10 for carriage return (effectively advances to the next line and returns to 0-th position horizontally.

Scoring

Your solution will be scored as follows. First, all the layers are summed together (in CMYK space). Then the result image is compare to the one provided in init(). The comparison is done by splitting both images into precision x precision squares, then counting the total intensity of each of the 4 colors in source and result boxes. The score is increased for each of the boxes by the following amount: pow(1 - abs(actualSum - originalSum), 2),

actualSum is the total saturation sum of a color K on a frame precision x precision, and

originalSum is the same for the original image.

Both values are scaled so that they are in range [0..1], by dividing them by area of the current box.

Finally, score is divided by canvas area, and multiplied by 1,000,000.

In case of illegal return of any kind, the score is zero.

Overall score across test cases is calculated relatively, summing YOUR / BEST for each of the test cases, averaging and scaling to 1,000,000.

Offline Tester

Available here

 

Definition

    
Class:TypesetterArt
Method:init
Parameters:int, int, int, int, int, int[]
Returns:int
Method signature:int init(int nRenders, int nFonts, int precision, int width, int height, int[] image)
 
Method:nextGlyph
Parameters:int, int, int[], int
Returns:int[]
Method signature:int[] nextGlyph(int width, int height, int[] bitmask, int measuredMillis)
 
Method:render
Parameters:int, int
Returns:int[]
Method signature:int[] render(int iteration, int measuredMillis)
(be sure your methods are public)
    
 

Constraints

-nRenders will be in range [1..16].
-nFonts will be in range [10..25].
-precision will be in range [1..16].
-Images used in tests were downloaded from random image at Wikipedia. Images which were not primarily photographic or photo-realistic, such as line drawings or photos of paintings, were discarded. Each dimension of each image will be between 250 and 800 pixels.
 

Examples

0)
    
seed = 1
1
1)
    
seed = 2
2
2)
    
seed = 3
3
3)
    
seed = 4
4
4)
    
seed = 5
5
5)
    
seed = 6
6
6)
    
seed = 7
7
7)
    
seed = 8
8
8)
    
seed = 9
9
9)
    
seed = 10
10

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.