1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Pluses everywhere
Contest: Codeforces Round 295 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, dp, math, number theory

Vasya is sitting on an extremely boring math class. To have fun, he took a piece of paper and wrote out n numbers on a single line. After that, Vasya began to write out different ways to put pluses ("+") in the line between certain digits in the line so that the result was a correct arithmetic expression; formally, no two pluses in such a partition can stand together (between any two adjacent pluses there must be at least one digit), and no plus can stand at the beginning or the end of a line. For example, in the string 100500, ways 100500 (add no pluses), 1+00+500 or 10050+0 are correct, and ways 100++500, +1+0+0+5+0+0 or 100500+ are incorrect.

The lesson was long, and Vasya has written all the correct ways to place exactly k pluses in a string of digits. At this point, he got caught having fun by a teacher and he was given the task to calculate the sum of all the resulting arithmetic expressions by the end of the lesson (when calculating the value of an expression the leading zeros should be ignored). As the answer can be large, Vasya is allowed to get only its remainder modulo 109 + 7. Help him!

Input format:
The first line contains two integers, n and k (0 ≤ k < n ≤ 105).

The second line contains a string consisting of n digits.

Output format:
Print the answer to the problem modulo 109 + 7.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample the result equals (1 + 08) + (10 + 8) = 27.

In the second sample the result equals 1 + 0 + 8 = 9.

Example input:
3 1
108

Example output:
27

Example input:
3 2
108

Example output:
9

Editorial:
DZY Loves Physics
Contest: Codeforces Round 254 (Div. 1)
Difficulty rating: 1600
Tags: greedy, math

DZY loves Physics, and he enjoys calculating density.

Almost everything has density, even a graph. We define the density of a non-directed graph (nodes and edges of the graph have some values) as follows:

$$\begin{cases}
\dfrac{v}{e} & (e > 0) \\
0 & (e = 0)
\end{cases}$$

Once DZY got a graph G, now he wants to find a connected induced subgraph G' of the graph, such that the density of G' is as large as possible.

An induced subgraph G'(V', E') of a graph G(V, E) is a graph that satisfies:

- $$V' \subseteq V$$;
- edge $$(a,b)\in E^{T}$$ if and only if $$a \in V', b \in V'$$, and edge $$(a,b)\in E$$;
- the value of an edge in G' is the same as the value of the corresponding edge in G, so as the value of a node.

Help DZY to find the induced subgraph with maximum density. Note that the induced subgraph you choose must be connected.

Input format:
The first line contains two space-separated integers n (1 ≤ n ≤ 500), $$m \left( 0 \leq m \leq \frac{n(n-1)}{2} \right)$$. Integer n represents the number of nodes of the graph G, m represents the number of edges.

The second line contains n space-separated integers xi (1 ≤ xi ≤ 106), where xi represents the value of the i-th node. Consider the graph nodes are numbered from 1 to n.

Each of the next m lines contains three space-separated integers ai, bi, ci (1 ≤ ai < bi ≤ n; 1 ≤ ci ≤ 103), denoting an edge between node ai and bi with value ci. The graph won't contain multiple edges.

Output format:
Output a real number denoting the answer, with an absolute or relative error of at most 10 - 9.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, you can only choose an empty subgraph, or the subgraph containing only node 1.

In the second sample, choosing the whole graph is optimal.

Example input:
1 0
1

Example output:
0.000000000000000

Example input:
2 1
1 2
1 2 1

Example output:
3.000000000000000

Editorial:
DZY Loves FFT
Contest: Codeforces Round 254 (Div. 1)
Difficulty rating: 2300
Tags: probabilities

DZY loves Fast Fourier Transformation, and he enjoys using it.

Fast Fourier Transformation is an algorithm used to calculate convolution. Specifically, if a, b and c are sequences with length n, which are indexed from 0 to n - 1, and

$$c_i = \sum_{j=0}^{i} a_j b_{i-j-1}$$

We can calculate c fast using Fast Fourier Transformation.

DZY made a little change on this formula. Now

$$c_i = \max_{j=0}^{i} a_j b_{i-j}$$

To make things easier, a is a permutation of integers from 1 to n, and b is a sequence only containing 0 and 1. Given a and b, DZY needs your help to calculate c.

Because he is naughty, DZY provides a special way to get a and b. What you need is only three integers n, d, x. After getting them, use the code below to generate a and b.

Operation x % y denotes remainder after division x by y. Function swap(x, y) swaps two values x and y.

Input format:
The only line of input contains three space-separated integers n, d, x (1 ≤ d ≤ n ≤ 100000; 0 ≤ x ≤ 1000000006). Because DZY is naughty, x can't be equal to 27777500.

Output format:
Output n lines, the i-th line should contain an integer ci - 1.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, a is [1 3 2], b is [1 0 0], so c0 = max(1·1) = 1, c1 = max(1·0, 3·1) = 3, c2 = max(1·0, 3·0, 2·1) = 2.

In the second sample, a is [2 1 4 5 3], b is [1 1 1 0 1].

In the third sample, a is [5 2 1 4 3], b is [1 1 1 1 0].

Example input:
3 1 1

Example output:
1
3
2

Example input:
5 4 2

Example output:
2
2
4
5
5

Editorial:
DZY Loves Colors
Contest: Codeforces Round 254 (Div. 1)
Difficulty rating: 2400
Tags: data structures

DZY loves colors, and he enjoys painting.

On a colorful day, DZY gets a colorful ribbon, which consists of n units (they are numbered from 1 to n from left to right). The color of the i-th unit of the ribbon is i at first. It is colorful enough, but we still consider that the colorfulness of each unit is 0 at first.

DZY loves painting, we know. He takes up a paintbrush with color x and uses it to draw a line on the ribbon. In such a case some contiguous units are painted. Imagine that the color of unit i currently is y. When it is painted by this paintbrush, the color of the unit becomes x, and the colorfulness of the unit increases by |x - y|.

DZY wants to perform m operations, each operation can be one of the following:

1. Paint all the units with numbers between l and r (both inclusive) with color x.
2. Ask the sum of colorfulness of the units between l and r (both inclusive).

Can you help DZY?

Input format:
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105).

Each of the next m lines begins with a integer type (1 ≤ type ≤ 2), which represents the type of this operation.

If type = 1, there will be 3 more integers l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108) in this line, describing an operation 1.

If type = 2, there will be 2 more integers l, r (1 ≤ l ≤ r ≤ n) in this line, describing an operation 2.

Output format:
For each operation 2, print a line containing the answer — sum of colorfulness.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the color of each unit is initially [1, 2, 3], and the colorfulness is [0, 0, 0].

After the first operation, colors become [4, 4, 3], colorfulness become [3, 2, 0].

After the second operation, colors become [4, 5, 5], colorfulness become [3, 3, 2].

So the answer to the only operation of type 2 is 8.

Example input:
3 3
1 1 2 4
1 2 3 5
2 1 3

Example output:
8

Example input:
3 4
1 1 3 4
2 1 1
2 2 2
2 3 3

Example output:
3
2
1

Editorial:
DZY Loves Strings
Contest: Codeforces Round 254 (Div. 1)
Difficulty rating: 2500
Tags: binary search, hashing, strings, two pointers

DZY loves strings, and he enjoys collecting them.

In China, many people like to use strings containing their names' initials, for example: xyz, jcvb, dzy, dyh.

Once DZY found a lucky string s. A lot of pairs of good friends came to DZY when they heard about the news. The first member of the i-th pair has name ai, the second one has name bi. Each pair wondered if there is a substring of the lucky string containing both of their names. If so, they want to find the one with minimum length, which can give them good luck and make their friendship last forever.

Please help DZY for each pair find the minimum length of the substring of s that contains both ai and bi, or point out that such substring doesn't exist.

A substring of s is a string slsl + 1... sr for some integers l, r (1 ≤ l ≤ r ≤ |s|). The length of such the substring is (r - l + 1).

A string p contains some another string q if there is a substring of p equal to q.

Input format:
The first line contains a string s (1 ≤ |s| ≤ 50000).

The second line contains a non-negative integer q (0 ≤ q ≤ 100000) — the number of pairs. Each of the next q lines describes a pair, the line contains two space-separated strings ai and bi (1 ≤ |ai|, |bi| ≤ 4).

It is guaranteed that all the strings only consist of lowercase English letters.

Output format:
For each pair, print a line containing a single integer — the minimum length of the required substring. If there is no such substring, output -1.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The shortest substrings in the first sample are: xyz, dyhduxyz.

The shortest substrings in the second sample are: ca, abc and abd.

The shortest substrings in the third sample are: baabca and abaa.

Example input:
xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz

Example output:
3
8
-1

Example input:
abcabd
3
a c
ab abc
ab d

Example output:
2
3
3

Editorial:
DZY Loves Planting
Contest: Codeforces Round 254 (Div. 1)
Difficulty rating: 2700
Tags: binary search, dsu, trees

DZY loves planting, and he enjoys solving tree problems.

DZY has a weighted tree (connected undirected graph without cycles) containing n nodes (they are numbered from 1 to n). He defines the function g(x, y) (1 ≤ x, y ≤ n) as the longest edge in the shortest path between nodes x and y. Specially g(z, z) = 0 for every z.

For every integer sequence p1, p2, ..., pn (1 ≤ pi ≤ n), DZY defines f(p) as $$\min_{i=1}^{n} g(i,p_i)$$.

DZY wants to find such a sequence p that f(p) has maximum possible value. But there is one more restriction: the element j can appear in p at most xj times.

Please, find the maximum possible f(p) under the described restrictions.

Input format:
The first line contains an integer n (1 ≤ n ≤ 3000).

Each of the next n - 1 lines contains three integers ai, bi, ci (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ 10000), denoting an edge between ai and bi with length ci. It is guaranteed that these edges form a tree.

Each of the next n lines describes an element of sequence x. The j-th line contains an integer xj (1 ≤ xj ≤ n).

Output format:
Print a single integer representing the answer.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample, one of the optimal p is [4, 3, 2, 1].

Example input:
4
1 2 1
2 3 2
3 4 3
1
1
1
1

Example output:
2

Example input:
4
1 2 1
2 3 2
3 4 3
4
4
4
4

Example output:
3

Editorial:
Shovels and Swords
Contest: Educational Codeforces Round 89 (Rated for Div. 2)
Difficulty rating: 1100
Tags: binary search, greedy, math

Polycarp plays a well-known computer game (we won't mention its name). In this game, he can craft tools of two types — shovels and swords. To craft a shovel, Polycarp spends two sticks and one diamond; to craft a sword, Polycarp spends two diamonds and one stick.

Each tool can be sold for exactly one emerald. How many emeralds can Polycarp earn, if he has $$$a$$$ sticks and $$$b$$$ diamonds?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 10^9$$$) — the number of sticks and the number of diamonds, respectively.

Output format:
For each test case print one integer — the maximum number of emeralds Polycarp can earn.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case Polycarp can earn two emeralds as follows: craft one sword and one shovel.

In the second test case Polycarp does not have any diamonds, so he cannot craft anything.

Example input:
4
4 4
1000000000 0
7 15
8 7

Example output:
2
0
7
5

Editorial:
There are three constraints on the number of emeralds:
1. the number of emeralds can't be greater than $$$a$$$;
2. the number of emeralds can't be greater than $$$b$$$;
3. the number of emeralds can't be greater than $$$\frac{a+b}{3}$$$.
So the answer is $$$\min(a, b, \frac{a+b}{3})$$$.
Shuffle
Contest: Educational Codeforces Round 89 (Rated for Div. 2)
Difficulty rating: 1300
Tags: math, two pointers

You are given an array consisting of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. Initially $$$a_x = 1$$$, all other elements are equal to $$$0$$$.

You have to perform $$$m$$$ operations. During the $$$i$$$-th operation, you choose two indices $$$c$$$ and $$$d$$$ such that $$$l_i \le c, d \le r_i$$$, and swap $$$a_c$$$ and $$$a_d$$$.

Calculate the number of indices $$$k$$$ such that it is possible to choose the operations so that $$$a_k = 1$$$ in the end.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the description of $$$t$$$ testcases follow.

The first line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m \le 100$$$; $$$1 \le x \le n$$$).

Each of next $$$m$$$ lines contains the descriptions of the operations; the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Output format:
For each test case print one integer — the number of indices $$$k$$$ such that it is possible to choose the operations so that $$$a_k = 1$$$ in the end.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it is possible to achieve $$$a_k = 1$$$ for every $$$k$$$. To do so, you may use the following operations:

1. swap $$$a_k$$$ and $$$a_4$$$;
2. swap $$$a_2$$$ and $$$a_2$$$;
3. swap $$$a_5$$$ and $$$a_5$$$.

In the second test case, only $$$k = 1$$$ and $$$k = 2$$$ are possible answers. To achieve $$$a_1 = 1$$$, you have to swap $$$a_1$$$ and $$$a_1$$$ during the second operation. To achieve $$$a_2 = 1$$$, you have to swap $$$a_1$$$ and $$$a_2$$$ during the second operation.

Example input:
3
6 4 3
1 6
2 3
5 5
4 1 2
2 4
1 2
3 3 2
2 3
1 2

Example output:
6
2
3

Editorial:
Let's consider how the set of possible indices where the $$$1$$$ can be changes. Initially, only one index is correct — $$$x$$$. After performing an operation $$$l, r$$$ such that $$$x < l$$$ or $$$x > r$$$ this set does not change. But after performing an operation $$$l, r$$$ such that $$$l \le x \le r$$$ we should insert the elements $$$\{l, l+1, l+2, \dots, r-1, r\}$$$ into this set, if they are not present.
Now consider how the set $$$\{L, L+1, L+2, \dots, R-1, R\}$$$ changes. If segments $$$[l, r]$$$ and $$$[L, R]$$$ do not share any indices, there are no changes — but if they do, the set turns into $$$\{ \min(l, L), \min(l, L)+1, \min(l, L)+2, \dots, \max(r, R)-1, \max(r, R) \}$$$.
So the set of reachable indices is always a segment of numbers, and to process an operation, we should check whether the segment from operation intersects with the segment of indices we have — and if it is true, unite them.
Two Divisors
Contest: Educational Codeforces Round 89 (Rated for Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, math, number theory

You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.

For each $$$a_i$$$ find its two divisors $$$d_1 > 1$$$ and $$$d_2 > 1$$$ such that $$$\gcd(d_1 + d_2, a_i) = 1$$$ (where $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$) or say that there is no such pair.

Input format:
The first line contains single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10^7$$$) — the array $$$a$$$.

Output format:
To speed up the output, print two lines with $$$n$$$ integers in each line.

The $$$i$$$-th integers in the first and second lines should be corresponding divisors $$$d_1 > 1$$$ and $$$d_2 > 1$$$ such that $$$\gcd(d_1 + d_2, a_i) = 1$$$ or $$$-1$$$ and $$$-1$$$ if there is no such pair. If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's look at $$$a_7 = 8$$$. It has $$$3$$$ divisors greater than $$$1$$$: $$$2$$$, $$$4$$$, $$$8$$$. As you can see, the sum of any pair of divisors is divisible by $$$2$$$ as well as $$$a_7$$$.

There are other valid pairs of $$$d_1$$$ and $$$d_2$$$ for $$$a_{10}=24$$$, like $$$(3, 4)$$$ or $$$(8, 3)$$$. You can print any of them.

Example input:
10
2 3 4 5 6 7 8 9 10 24

Example output:
-1 -1 -1 -1 3 -1 -1 -1 2 2 
-1 -1 -1 -1 2 -1 -1 -1 5 3

Editorial:
Firstly, for the fast factorization of given $$$a_i$$$, let's use Sieve of Eratosthenes: let's for each value $$$val \le 10^7$$$ calculate its minimum prime divisor $$$minDiv[val]$$$ in the same manner as the sieve do. Now we can factorize each $$$a_i$$$ in $$$O(\log{a_i})$$$ time by separating its prime divisors one by one using precalculated array $$$minDiv$$$.
Suppose, we have a factorization $$$a_i = p_1^{s_1} p_2^{s_2} \cdot \ldots \cdot p_k^{s_k}$$$. If $$$k = 1$$$ then any divisor of $$$a_i$$$ is divisible by $$$p_1$$$ so do the sum of divisors. Obviously, the answer is $$$-1$$$ $$$-1$$$.
Otherwise, we can divide all prime divisors $$$p_i$$$ into two non-empty groups $$$\{p_1, p_2, \dots, p_x\}$$$ and $$$\{p_{x + 1}, \dots, p_k\}$$$ and take $$$d_1 = p_1 \cdot p_2 \cdot \ldots \cdot p_x$$$ and $$$d_2 = p_{x + 1} \cdot \ldots \cdot p_k$$$. Any division is valid (proof is below), so, for example, we can take $$$d_1 = p_1$$$ and $$$d_2 = p_2 \cdot \ldots \cdot p_k$$$.
Let's prove that if $$$d_1 = p_1 \cdot p_2 \cdot \ldots \cdot p_x$$$ and $$$d_2 = p_{x + 1} \cdot \ldots \cdot p_k$$$ then $$$\gcd(d_1 + d_2, a_i) = 1$$$. Let's look at any $$$p_i$$$. We can assume that $$$a_i \equiv 0 \mod p_i$$$ and (without loss of generality) $$$d_1 \equiv 0 \mod p_i$$$. But it means that $$$d_2 \not\equiv 0 \mod p_i$$$, then $$$d_1 + d_2 \equiv 0 + d_2 \equiv d_2 \not\equiv 0 \mod p_i$$$. In other words, there are no prime divisor of $$$a_i$$$ which divides $$$d_1 + d_2$$$, so the $$$\gcd(d_1 + d_2, a_i) = 1$$$.
Time complexity is $$$O(A \log{\log{A}} + n \log{A})$$$ for the sieve and finding answers ($$$A \le 10^7$$$).
Two Arrays
Contest: Educational Codeforces Round 89 (Rated for Div. 2)
Difficulty rating: 2100
Tags: binary search, brute force, combinatorics, constructive algorithms, dp, two pointers

You are given two arrays $$$a_1, a_2, \dots , a_n$$$ and $$$b_1, b_2, \dots , b_m$$$. Array $$$b$$$ is sorted in ascending order ($$$b_i < b_{i + 1}$$$ for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$).

You have to divide the array $$$a$$$ into $$$m$$$ consecutive subarrays so that, for each $$$i$$$ from $$$1$$$ to $$$m$$$, the minimum on the $$$i$$$-th subarray is equal to $$$b_i$$$. Note that each element belongs to exactly one subarray, and they are formed in such a way: the first several elements of $$$a$$$ compose the first subarray, the next several elements of $$$a$$$ compose the second subarray, and so on.

For example, if $$$a = [12, 10, 20, 20, 25, 30]$$$ and $$$b = [10, 20, 30]$$$ then there are two good partitions of array $$$a$$$:

1. $$$[12, 10, 20], [20, 25], [30]$$$;
2. $$$[12, 10], [20, 20, 25], [30]$$$.

You have to calculate the number of ways to divide the array $$$a$$$. Since the number can be pretty large print it modulo 998244353.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of arrays $$$a$$$ and $$$b$$$ respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots , b_m$$$ ($$$1 \le b_i \le 10^9; b_i < b_{i+1}$$$) — the array $$$b$$$.

Output format:
In only line print one integer — the number of ways to divide the array $$$a$$$ modulo 998244353.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6 3
12 10 20 20 25 30
10 20 30

Example output:
2

Example input:
4 2
1 3 3 7
3 7

Example output:
0

Editorial:
At first, let's reverse arrays $$$a$$$ and $$$b$$$. Now array $$$b$$$ is sorted in descending order.
Now let's find minimum index $$$x$$$ such that $$$a_x = b_1$$$. If there is no such index or if $$$\min\limits_{1 \le i \le x}a_i < b_1$$$ then the answer is $$$0$$$ (because minimum on any prefix of array $$$a$$$ will never be equal to $$$b_1$$$).
Otherwise, let's find the minimum index $$$y > x$$$ such that $$$a_y = b_2$$$. If there is no such index or if $$$\min\limits_{x \le i \le y}a_i < b_2$$$ then the answer is $$$0$$$. Also let's find the minimum index $$$mid > x$$$ such that $$$a_{mid} < b_1$$$ (it can't be greater than $$$y$$$). The first subarray starts in position $$$1$$$ and ends in any position $$$x, x + 1, x + 2, \dots, mid - 1$$$ (because if it ends in position $$$mid$$$ or further, then the minimum in the first subarray is greater than $$$b_1$$$). So there are $$$mid - x$$$ ways to split subarrays $$$1$$$ and $$$2$$$.
A similar approach can be used to calculate the number of ways to split the second and third subarrays and, so on.
After all, you have to check that minimum in the last subarray is equal to $$$b_m$$$ (otherwise the answer is $$$0$$$).
Binary Blocks
Contest: IndiaHacks 2nd Elimination 2017 (unofficial, unrated mirror, ICPC rules)
Difficulty rating: 1400
Tags: brute force

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 format:
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 format:
Print a single integer, the minimum number of pixels needed to toggle to make the image compressible.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
We first choose k = 2.

The image is padded as follows:

We can toggle the image to look as follows:

We can see that this image is compressible for k = 2.

Example input:
3 5
00100
10110
11001

Example output:
5

Editorial:
Let's define function onesInRect(sx, sy, ex, ey) as number of ones in rectangle with top-left (sx, sy) and down-right (ex - 1, ey - 1) (0-based).
Let psi, j the number of ones in rectangle with top-left (0, 0) and down-right (i - 1, j - 1) (0-based).
Let Cost(k) the answer if we compress the image with k. Let's find Cost(k).
int ans = 0;
for(int i = k; i < n + k; i++)
for(int j = k; j < m + k; j++)
ans += min(onesInRect(i - k, j - k, i, j), k * k - onesInRect(i - k, j - k, i, j));
Time complexity of Cost(k) is $${\mathcal {O}}\left({\frac {n\cdot m}{k^{2}}}\right)$$. Now the answer is mink = 2max(n, m)Cost(k). Overall time complexity is $${ \mathcal { O } } ( n \cdot m )$$.