Connection Status:
Competition Arena > ImageCompression

ImageCompression

SRM 715 · 2017-02-20 · by lg5293

SRM 715 · 2017-02-20 · by lg5293 · String Manipulation
Class Name: ImageCompression
Return Type: String
Method Name: isPossible
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

You have a rectangular bitmap that consists of n rows by m columns of pixels. You are given the bitmap encoded as a String[] image. Each pixel of the bitmap is either black or white. Black pixels are represented by the character '0', white ones by '1'.

You are also given an int k that divides both n and m. You want to check whether you can compress the bitmap by shrinking it k times in each dimension. More precisely, the compression works as follows:

  • Divide the bitmap into blocks of size k times k pixels.
  • Check whether each block consists of pixels of a single color only. If some block contains both black and white pixels, the bitmap cannot be compressed.
  • Compress the bitmap by shrinking each block into a single pixel of the respective color.

Determine whether we can compress the given bitmap for the given k. If we can, return "Possible", otherwise, return "Impossible". Note that the return value is case-sensitive.

Constraints

  • n,m will be between 2 and 50, inclusive.
  • image will contain exactly n elements.
  • Each element of image will contain exactly m characters.
  • Each character of each element of image will be '0' or '1'.
  • k will be between 2 and 50.
  • k will divide n and m.
Examples
0)
{
"0011",
"0011",
"1100",
"1100",
"0000",
"0000"
}
2
Returns: "Possible"
1)
{
"0011",
"0011",
"1100",
"1100",
"0010",
"0000"
}
2
Returns: "Impossible"

The block in the bottom right corner contains three black pixels and one white pixel.

2)
{
"111000111",
"111000111",
"111000111"
}
3
Returns: "Possible"
3)
{
"001100",
"001100",
"110011",
"110011",
"001100",
"001100"
}
6
Returns: "Impossible"

This is not compressible when k=6.

4)
{
"001100",
"001100",
"110011",
"110011",
"001100",
"001100"
}
2
Returns: "Possible"

It is compressible when k=2 however.

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ImageCompression with a public method string isPossible(vector<string> image, int k) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous