Problem B
Image Compression
Saskia wants to reduce the bandwidth usage of her website, and has investigated how she can compress her PNG images. She got a bit curious on how PNG image optimizers work, and before she knew it, she started working on her own!
In PNG, an image is considered a grid of $Y$ rows and $X$ columns of bytes. Before the image is compressed, each row is transformed by one of five “filter transform” methods.
![\includegraphics[width=0.1\textwidth ]{cbax}](/problems/imagecompression/file/statement/en/img-0001.png)
In this problem, we’ll only consider the first four for convenience. Those filter methods use previously decoded bytes, either from the byte above (b) or the value left of this byte (a), as shown in the image above.
The four filter methods we are concerned with are defined as follows:
|
Name |
Function |
|
None |
Filt(x) = Orig(x) |
|
Sub |
Filt(x) = Orig(x) - Orig(a) |
|
Up |
Filt(x) = Orig(x) - Orig(b) |
|
Average |
Filt(x) = Orig(x) - floor((Orig(a)+Orig(b))/2) |
As we’re dealing with bytes, be sure to do unsigned modulo $256$ immediately after addition and subtraction to get the right result. In addition, if a or b doesn’t exist, they are considered to be $0$.
A common heuristic when choosing which filter to use is to pick the methods that give as many zero bytes as possible after the transformation. However, Saskia believes it is much better to use the filter methods that gives the most of ANY particular byte instead. Can you help her make a program that finds the optimal filter transforms?
Input
On the first line, you are given two positive integers, $Y$ and $X$, denoting the number of rows and columns of the image, respectively.
Then follow $Y$ lines, each with $X$ space-separated integers $b_{y,x}$, representing the picture.
Output
Print the byte that will have the highest frequency if the optimal filter methods are used, along with its frequency. If there are multiple bytes with the highest frequency, print the highest one.
Limits
-
$0 < Y, X \leq 350$
-
$0 \leq b_{y,x} < 256$
Sample Explanation
In Sample $1$, we can use the filters Up, Sub, Up and Average to get $4$ occurrences of $73$. We can also use Sub, Up, None and Average to get $4$ occurrences of $87$. As $87$ is the biggest, we print that one.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 7 251 111 206 182 13 242 73 215 93 166 13 185 159 211 43 166 218 255 48 157 87 94 92 118 142 196 206 1 |
87 4 |
