We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Artificial Intelligence
  3. Digital Image Analysis
  4. Image Upsampling

Image Upsampling

To reduce the size of a -dimensional image, , containing rows and columns of pixels, the image is downsampled using a crude algorithm.

The downsampling algorithm begins sampling from the top-left pixel position, , of the original image and then proceeds to retain only those pixels which are located in those positions where both the row number and the column number are either 0, or integer multiples of some integer . The downsampled image only contains rows and columns where these values correspond to and

Let's assume for a moment that the original image is as follows (where each character indicates a pixel): 

ABCDEFG  
HIJKLMN  
OPQRSTU  
VWXYZab  
cdefghi    
jklmnop

This image has rows and columns.
Assume that the pixel is the one positioned at .
If we downsample this image using , we only retain those pixels located in positions where both the row and column numbers are even. This means the downsampled image will be: 

ACEG  
OQSU 
cegi

Observe that when , the downsampled image retains over a quarter of the pixels.

Now, if we downsample this image using , we only retain those pixels located in positions where both the row and column numbers are multiples of . This means the downsampled image will be: 

ADG  
VYb

Observe that when , the downsampled image retains only pixels.

Task

You are provided with the values for a downsampled image and the downsampling coefficient (). Given the size of the original image (and assuming that the algorithm used for downsampling is the one described above), restore the original image using the interpolation or upsampling algorithm of your choice.

Input Format

The first line contains space-separated integers, (the number of rows in the downsampled image), (the number of columns in the downsampled image) and (the downsample coefficient), respectively.

The second line contains space-separated integers, and , representing the respective numbers of rows and columns in the original image.

The subsequent lines describe the grid representing the pixel-wise values from the images (which were originally in JPG or PNG formats).
Each line contains pixels, and each pixel is represented by three comma-separated values in the range from to denoting the respective Blue, Green, and Red components. There is a space between successive pixels in the same row.

No input test case will exceed 3MB in size. This is the size of the RGB test matrix, NOT the original image from which it was generated.

Scoring

We define the between an expected pixel value and an estimated pixel value to be:

For each test image, we compute (the mean distance between the actual pixel value and the estimated value) for each pixel position in the image.

The score awarded for an image is . This means that you will receive no score for a test if your mean from the actual image exceeds . Your final score is the average of the awarded scores for each test image.

You may make no more than 15 submissions for this problem, during the contest.

Output Format

Print a grid of pixel values describing the upsampled image. Your output should follow the same format as the grid received as input.

Note: You should only print the grid; there is no need to specify the number of rows and columns here.

Sample Input

3 3 2
6 6
0,0,200 0,0,10 10,0,0
90,90,50 90,90,10 255,255,255
100,100,88 80,80,80 15,75,255

The downsampled image is pixels, with a sampling coefficient of . You must upsample this image and generate an interpolated image of pixels.

The image described above is represented by pixels. The Blue, Green, and Red values provided for each pixel are comma-separated, and the pixel descriptions are space-separated.

The top-left pixel is defined as .
The top-right pixel is defined as .
The bottom-right pixel is defined as .
The bottom-left pixel is defined as .

Sample Output

0,0,200 100,100,100 0,0,10 5,5,5 10,0,0 50,50,50
90,90,50 90,90,50 90,90,10 90,90,10 255,255,255 0,0,10
100,100,88 100,100,88 80,80,80 80,80,80 15,75,255 15,75,255 
100,100,88 100,100,88 80,80,80 80,80,80 15,75,255 15,75,255 
100,100,88 100,100,88 80,80,80 80,80,80 15,75,255 15,75,255
90,90,50 90,90,50 90,90,10 90,90,10 255,255,255 0,0,10

This is for the purpose of explanation only. We have generated an image of size from the input image.