TopCoder problem "AutoAdjust" used in TCCC05 Round 3 (Division I Level One)



Problem Statement

    Most image editing programs have the ability to adjust an image's brightness and contrast. When adjusting the brightness of an image, an integer value is either added or subtracted from the color value of each pixel. When adjusting the contrast of an image, the color value of grey is first subtracted from the color value of each pixel, then the color value is multiplied by an integer and divided by 100, and finally the value of grey is added back to the color value. When adjusting both brightness and contrast, the brightness is adjusted first, and then the contrast is adjusted. If, after applying either adjustment, the color value of a pixel is below the minimum color value or above the maximum color value, then the color value for that pixel is set at the minimum or maximum, respectively (32 and 95 in this problem).



In this problem, we will consider a greyscale image, where each pixel is represented by an ASCII character between 32 and 95, inclusive. Grey is indicated by 63.5 (hence no pixel is exactly grey). Your task is to adjust the brightness and contrast of an image so that the darkest pixels in the image are black (32), and the brightest pixels in the image are white (95). To do this, you may adjust the brightness by any integer value between -100 and 100, inclusive, and you may adjust the contrast by any integer value between 100 and 20,000, inclusive. When a pixel's value is not an integer after the adjustment, round its value to the nearest integer (0.5 rounds up). To prevent loss of detail, you should adjust the brightness and contrast in such a way that the contrast is adjusted as little as possible. If there are multiple ways to do this with the minimum contrast adjustment, you should pick the one with the smallest absolute brightness adjustment. You should return a String[] representing the adjusted image.
 

Definition

    
Class:AutoAdjust
Method:adjust
Parameters:String[]
Returns:String[]
Method signature:String[] adjust(String[] image)
(be sure your method is public)
    
 

Notes

-There will always be a way to perform the adjustment.
 

Constraints

-image will contain between 1 and 50 elements, inclusive.
-Each element of image will contain between 1 and 50 characters, inclusive.
-Each element of image will contain the same number of characters.
-There will be at least two different color values in image.
-Each character in image will have ASCII value between 32 and 95, inclusive.
 

Examples

0)
    
{"------------",
 "--TTT--CCC--",
 "---T---C----",
 "---T---CCC--",
 "------------"}
Returns: 
{ "            ",
 "  ___  CCC  ",
 "   _   C    ",
 "   _   CCC  ",
 "            " }
'-', 'C', and 'T' have ASCII values of 45, 67, and 84, respectively. By decreasing the brightness by 1, and then adjusting the contrast by 159, these three values are transformed as follows:
(45 - 1 - 63.5) * 159 / 100 + 63.5 = 32.495
(67 - 1 - 63.5) * 159 / 100 + 63.5 = 67.475
(84 - 1 - 63.5) * 159 / 100 + 63.5 = 94.505
Rounding these values, we get 32, 67 and 95.
1)
    
{"            ",
 "  ___  CCC  ",
 "   _   C    ",
 "   _   CCC  ",
 "            "}
Returns: 
{ "            ",
 "  ___  CCC  ",
 "   _   C    ",
 "   _   CCC  ",
 "            " }
The minimum and maximum values are already 32 and 95, so nothing needs to be done (brightness = 0, contrast = 100).
2)
    
{"AB"}
Returns: { " _" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3483

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6530&pm=3483

Writer:

lars2520

Testers:

PabloGilberto , lbackstrom , Yarin , vorthys

Problem categories:

Brute Force, Simple Math