English · Original
Chinese · Translation
Formal · Original
On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.
Let {_a_1, _a_2, ..., _a__n_} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are **of the same length** and consist only of the digits 0 and 1. Let's define the compression function:
* _f_(empty sequence) = empty string
* _f_(_s_) = _s_.
* _f_(_s_1, _s_2) = the smallest in length string, which has one of the prefixes equal to _s_1 and one of the suffixes equal to _s_2. For example, _f_(001, 011) = 0011, _f_(111, 011) = 111011.
* _f_(_a_1, _a_2, ..., _a__n_) = _f_(_f_(_a_1, _a_2, _a__n_ - 1), _a__n_). For example, _f_(000, 000, 111) = _f_(_f_(000, 000), 111) = _f_(000, 111) = 000111.
Valera faces a real challenge: he should divide the given sequence {_a_1, _a_2, ..., _a__n_} into two subsequences {_b_1, _b_2, ..., _b__k_} and {_c_1, _c_2, ..., _c__m_}, _m_ + _k_ = _n_, so that the value of _S_ = |_f_(_b_1, _b_2, ..., _b__k_)| + |_f_(_c_1, _c_2, ..., _c__m_)| took the minimum possible value. Here |_p_| denotes the length of the string _p_.
Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences _b_ and _c_ don't have to be consecutive in the original sequence _a_, i. e. elements of _b_ and _c_ can alternate in _a_ (see samples 2 and 3).
Help Valera to find the minimum possible value of _S_.
## Input
The first line of input data contains an integer _n_ — the number of strings (1 ≤ _n_ ≤ 2·105). Then on _n_ lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The _i_ + 1\-th input line contains the _i_\-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.
## Output
Print a single number — the minimum possible value of _S_.
[samples]
## Note
Detailed answers to the tests:
* The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |_f_(01, 10, 01)| = |_f_(_f_(01, 10), 01)| = |_f_(010, 01)| = |0101| = 4.
* The best option is: _b_ = {000, 001}, _c_ = {111, 110}. _S_ = |_f_(000, 001)| + |_f_(111, 110)| = |0001| + |1110| = 8.
* The best option is: _b_ = {10101, 01010, 01000}, _c_ = {11111, 10010}. _S_ = |10101000| + |111110010| = 17.
在一次信息技术课上，Valera 学习了数据压缩。老师介绍了一种新方法，我们现在将向你描述它。
设 #cf_span[{a1, a2, ..., an}] 为需要压缩的给定字符串序列。此处及下文中，我们假设所有字符串 *长度相同*，且仅由数字 #cf_span[0] 和 #cf_span[1] 组成。定义压缩函数：
Valera 面临一个真正的挑战：他需要将给定序列 #cf_span[{a1, a2, ..., an}] 划分为两个子序列 #cf_span[{b1, b2, ..., bk}] 和 #cf_span[{c1, c2, ..., cm}]，其中 #cf_span[m + k = n]，使得值 #cf_span[S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)|] 达到最小可能值。这里 #cf_span[|p|] 表示字符串 #cf_span[p] 的长度。
注意，不允许改变子序列中字符串的相对顺序。允许将其中一个子序列设为空。初始序列中的每个字符串必须恰好属于一个子序列。子序列 #cf_span[b] 和 #cf_span[c] 的元素在原序列 #cf_span[a] 中不必连续，即 #cf_span[b] 和 #cf_span[c] 的元素可以在 #cf_span[a] 中交错出现（见样例 2 和 3）。
帮助 Valera 找到 #cf_span[S] 的最小可能值。
输入数据的第一行包含一个整数 #cf_span[n] —— 字符串的数量（#cf_span[1 ≤ n ≤ 2·105]）。接下来的 #cf_span[n] 行是序列的元素——每个字符串长度为 #cf_span[1] 到 #cf_span[20] 个字符，仅由数字 #cf_span[0] 和 #cf_span[1] 组成。第 #cf_span[i + 1] 行包含序列的第 #cf_span[i] 个元素。序列的元素仅由换行符分隔。保证所有字符串长度相同。
输出一个单独的数字——#cf_span[S] 的最小可能值。
## Input
The first line of input data contains an integer #cf_span[n] — the number of strings (#cf_span[1 ≤ n ≤ 2·105]). Then on #cf_span[n] lines follow elements of the sequence — strings whose lengths are from #cf_span[1] to #cf_span[20] characters, consisting only of digits #cf_span[0] and #cf_span[1]. The #cf_span[i + 1]-th input line contains the #cf_span[i]-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.
## Output
Print a single number — the minimum possible value of #cf_span[S].
[samples]
## Note
测试的详细解答：
最佳方案是将其中一个子序列设为空，另一个等于整个给定序列。#cf_span[|f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4]。
最佳方案是：#cf_span[b = {000, 001}, c = {111, 110}]。#cf_span[S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8]。
最佳方案是：#cf_span[b = {10101, 01010, 01000}, c = {11111, 10010}]。#cf_span[S = |10101000| + |111110010| = 17]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of binary strings.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of binary strings, each of fixed length $ L \geq 1 $, with $ a_i \in \{0,1\}^L $.
Let $ f(S) $ denote the compression function applied to a subsequence $ S = (s_1, s_2, \dots, s_k) $, defined as:
$$
f(S) = \text{the shortest binary string } p \text{ such that } \forall i \in \{1,\dots,k\},\ s_i \text{ is a substring of } p.
$$
Let $ |p| $ denote the length of string $ p $.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. Each $ a_i $ has length $ L $, where $ 1 \leq L \leq 20 $
3. Each $ a_i $ consists only of characters '0' and '1'
**Objective**
Partition $ A $ into two disjoint subsequences $ B = (b_1, \dots, b_k) $ and $ C = (c_1, \dots, c_m) $, with $ k + m = n $, preserving the relative order of elements in each subsequence.
Minimize:
$$
S = |f(B)| + |f(C)|
$$
API Response (JSON)
{
"problem": {
"name": "E. Two Subsequences",
"description": {
"content": "On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you. Let {_a_1, _a_2, ..., _a__n_} be the given sequence of lines needed to be com",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF83E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.\n\nLet {_a_1, _a_2, ..., _a__n_} be the given sequence of lines needed to be com...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在一次信息技术课上，Valera 学习了数据压缩。老师介绍了一种新方法，我们现在将向你描述它。\n\n设 #cf_span[{a1, a2, ..., an}] 为需要压缩的给定字符串序列。此处及下文中，我们假设所有字符串 *长度相同*，且仅由数字 #cf_span[0] 和 #cf_span[1] 组成。定义压缩函数：\n\nValera 面临一个真正的挑战：他需要将给定序列 #cf_span[{a1,...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of binary strings. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of binary strings, each of fixed length $ L \\geq 1 $, with $ a_i \\in \\{...",
"is_translate": false,
"language": "Formal"
}
]
}