A. Binary Blocks

Codeforces

IDCF838A

Time2000ms

Memory256MB

Difficulty—

brute force

English · Original

Chinese · Translation

Formal · Original

You are given an image, that can be represented with a 2\-d _n_ by _m_ grid of pixels. Each pixel of the image is either on or off, denoted by the characters "_0_" or "_1_", respectively. You would like to compress this image. You want to choose an integer _k_ > 1 and split the image into _k_ by _k_ blocks. If _n_ and _m_ are not divisible by _k_, the image is padded with only zeros on the right and bottom so that they are divisible by _k_. Each pixel in each individual block must have the same value. The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle (after padding) in order for the image to be compressible for some _k_. More specifically, the steps are to first choose _k_, then the image is padded with zeros, then, we can toggle the pixels so it is compressible for this _k_. The image must be compressible in that state. ## Input The first line of input will contain two integers _n_, _m_ (2 ≤ _n_, _m_ ≤ 2 500), the dimensions of the image. The next _n_ lines of input will contain a binary string with exactly _m_ characters, representing the image. ## Output Print a single integer, the minimum number of pixels needed to toggle to make the image compressible. [samples] ## Note We first choose _k_ = 2. The image is padded as follows: 001000 101100 110010 000000 We can toggle the image to look as follows: 001100 001100 000000 000000 We can see that this image is compressible for _k_ = 2.

[{"iden":"statement","content":"给你一张图像，可以用一个大小为 #cf_span[n] × #cf_span[m] 的二维像素网格表示。每个像素要么开启（用字符 \"_0_\" 表示），要么关闭（用字符 \"_1_\" 表示）。你希望压缩这张图像。你需要选择一个整数 #cf_span[k > 1]，并将图像分割为 #cf_span[k] × #cf_span[k] 的块。如果 #cf_span[n] 和 #cf_span[m] 不能被 #cf_span[k] 整除，则在图像的右侧和底部填充仅由零组成的像素，使得其尺寸能被 #cf_span[k] 整除。每个块内的所有像素必须具有相同的值。当前图像可能无法直接压缩。请找出在填充后，最少需要翻转多少个像素，才能使图像对于某个 #cf_span[k] 可压缩。更具体地说，步骤为：首先选择 #cf_span[k]，然后对图像进行填充，接着翻转一些像素，使得图像对该 #cf_span[k] 可压缩。最终图像必须满足可压缩条件。\n\n输入的第一行包含两个整数 #cf_span[n, m] (#cf_span[2 ≤ n, m ≤ 2 500])，表示图像的尺寸。\n\n接下来的 #cf_span[n] 行，每行包含一个恰好有 #cf_span[m] 个字符的二进制字符串，表示图像。\n\n请输出一个整数，表示使图像可压缩所需的最少翻转像素数。"}},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n, m] (#cf_span[2 ≤ n, m ≤ 2 500])，表示图像的尺寸。接下来的 #cf_span[n] 行，每行包含一个恰好有 #cf_span[m] 个字符的二进制字符串，表示图像。"},{"iden":"output","content":"请输出一个整数，表示使图像可压缩所需的最少翻转像素数。"},{"iden":"note","content":"我们首先选择 #cf_span[k = 2]。图像填充后如下：001000101100110010000000我们可以翻转图像使其变为如下形式：001100001100000000000000可以看出，该图像对于 #cf_span[k = 2] 是可压缩的。"}]

**Definitions** Let $ n, m \in \mathbb{Z} $ be the dimensions of the image grid, with $ 2 \leq n, m \leq 2500 $. Let $ G \in \{0,1\}^{n \times m} $ be the input binary grid, where $ G[i][j] \in \{0,1\} $ denotes the pixel at row $ i $, column $ j $. For a chosen integer $ k > 1 $, define the padded dimensions: $$ n' = \left\lceil \frac{n}{k} \right\rceil \cdot k, \quad m' = \left\lceil \frac{m}{k} \right\rceil \cdot k $$ The padded grid $ G' \in \{0,1\}^{n' \times m'} $ is formed by appending $ n' - n $ rows and $ m' - m $ columns of zeros to $ G $. The grid $ G' $ is **compressible** for $ k $ if it can be partitioned into $ \frac{n'}{k} \times \frac{m'}{k} $ disjoint $ k \times k $ blocks, such that **all pixels in each block are equal** (i.e., each block is monochromatic). **Constraints** 1. $ k \in \mathbb{Z} $, $ k > 1 $ 2. $ n' \geq n $, $ m' \geq m $, and $ k \mid n' $, $ k \mid m' $ 3. The number of toggles is the Hamming distance between $ G' $ and a compressible grid $ H \in \{0,1\}^{n' \times m'} $, where $ H $ is constant on each $ k \times k $ block. **Objective** Find the minimum number of pixel toggles over all valid $ k > 1 $: $$ \min_{\substack{k > 1 \\ k \in \mathbb{Z}}} \left( \min_{\substack{H \in \{0,1\}^{n' \times m'} \\ H \text{ is } k\text{-compressible}}} \sum_{i=1}^{n'} \sum_{j=1}^{m'} \left| G'[i][j] - H[i][j] \right| \right) $$ where $ G' $ is the zero-padded version of $ G $ for the chosen $ k $.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "A. Binary Blocks",
    "description": {
      "content": "You are given an image, that can be represented with a 2\\-d _n_ by _m_ grid of pixels. Each pixel of the image is either on or off, denoted by the characters \"_0_\" or \"_1_\", respectively. You would li",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF838A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an image, that can be represented with a 2\\-d _n_ by _m_ grid of pixels. Each pixel of the image is either on or off, denoted by the characters \"_0_\" or \"_1_\", respectively. You would li...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"给你一张图像，可以用一个大小为 #cf_span[n] × #cf_span[m] 的二维像素网格表示。每个像素要么开启（用字符 \\\"_0_\\\" 表示），要么关闭（用字符 \\\"_1_\\\" 表示）。你希望压缩这张图像。你需要选择一个整数 #cf_span[k > 1]，并将图像分割为 #cf_span[k] × #cf_span[k] ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the dimensions of the image grid, with $ 2 \\leq n, m \\leq 2500 $.  \nLet $ G \\in \\{0,1\\}^{n \\times m} $ be the input binary grid, where $ G[i][j] \\in \\{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments