E. Short Code

Codeforces

IDCF965E

Time1000ms

Memory256MB

Difficulty—

data structuresdpgreedystringstrees

English · Original

Chinese · Translation

Formal · Original

Arkady's code contains $n$ variables. Each variable has a unique name consisting of lowercase English letters only. One day Arkady decided to shorten his code. He wants to replace each variable name with its non-empty prefix so that these new names are still unique (however, a new name of some variable can coincide with some old name of another or same variable). Among such possibilities he wants to find the way with the smallest possible total length of the new names. A string $a$ is a prefix of a string $b$ if you can delete some (possibly none) characters from the end of $b$ and obtain $a$. Please find this minimum possible total length of new names. ## Input The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of variables. The next $n$ lines contain variable names, one per line. Each name is non-empty and contains only lowercase English letters. The total length of these strings is not greater than $10^5$. The variable names are distinct. ## Output Print a single integer — the minimum possible total length of new variable names. [samples] ## Note In the first example one of the best options is to shorten the names in the given order as "_cod_", "_co_", "_c_". In the second example we can shorten the last name to "_aac_" and the first name to "_a_" without changing the other names.

Arkady 的代码包含 $n$ 个变量。每个变量都有一个仅由小写英文字母组成的唯一名称。一天，Arkady 决定缩短他的代码。他希望将每个变量名替换为其一个非空前缀，使得这些新名称仍然互不相同（但某个变量的新名称可以与另一个或相同变量的旧名称相同）。在所有这样的可能性中，他希望找到一种使新名称总长度最小的方案。字符串 $a$ 是字符串 $b$ 的前缀，当且仅当你可以从 $b$ 的末尾删除一些（可能为零个）字符得到 $a$。请找出新名称可能的最小总长度。第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 变量的数量。接下来的 $n$ 行每行包含一个变量名。每个名称非空且仅包含小写英文字母。这些字符串的总长度不超过 $10^5$。变量名互不相同。请输出一个整数 —— 新变量名可能的最小总长度。在第一个示例中，一种最优方案是按给定顺序将名称缩短为 "_cod_"、"_co_"、"_c_"。在第二个示例中，我们可以将最后一个名称缩短为 "_aac_"，将第一个名称缩短为 "_a_"，而不改变其他名称。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 变量的数量。接下来的 $n$ 行每行包含一个变量名。每个名称非空且仅包含小写英文字母。这些字符串的总长度不超过 $10^5$。变量名互不相同。 ## Output 请输出一个整数 —— 新变量名可能的最小总长度。 [samples] ## Note 在第一个示例中，一种最优方案是按给定顺序将名称缩短为 "_cod_"、"_co_"、"_c_"。在第二个示例中，我们可以将最后一个名称缩短为 "_aac_"，将第一个名称缩短为 "_a_"，而不改变其他名称。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of variables. Let $ V = \{v_1, v_2, \dots, v_n\} $ be a set of distinct non-empty strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $. For each $ v_i \in V $, let $ P(v_i) = \{ v_i[1:j] \mid 1 \leq j \leq |v_i| \} $ denote the set of all non-empty prefixes of $ v_i $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ \sum_{i=1}^n |v_i| \leq 10^5 $ 3. All $ v_i $ are distinct. **Objective** Find a selection $ p_i \in P(v_i) $ for each $ i \in \{1, \dots, n\} $, such that: - All $ p_i $ are pairwise distinct, - The total length $ \sum_{i=1}^n |p_i| $ is minimized. Output the minimal possible value of $ \sum_{i=1}^n |p_i| $.

Samples

Input #1

3
codeforces
codehorses
code

Output #1

Input #2

5
abba
abb
ab
aa
aacada

Output #2

Input #3

3
telegram
digital
resistance

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Short Code",
    "description": {
      "content": "Arkady's code contains $n$ variables. Each variable has a unique name consisting of lowercase English letters only. One day Arkady decided to shorten his code. He wants to replace each variable name ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF965E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arkady's code contains $n$ variables. Each variable has a unique name consisting of lowercase English letters only. One day Arkady decided to shorten his code.\n\nHe wants to replace each variable name ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arkady 的代码包含 $n$ 个变量。每个变量都有一个仅由小写英文字母组成的唯一名称。一天，Arkady 决定缩短他的代码。\n\n他希望将每个变量名替换为其一个非空前缀，使得这些新名称仍然互不相同（但某个变量的新名称可以与另一个或相同变量的旧名称相同）。在所有这样的可能性中，他希望找到一种使新名称总长度最小的方案。\n\n字符串 $a$ 是字符串 $b$ 的前缀，当且仅当你可以从 $b$ 的末尾删除...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of variables.  \nLet $ V = \\{v_1, v_2, \\dots, v_n\\} $ be a set of distinct non-empty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments