A. Codehorses T-shirts

Codeforces
IDCF1000A
Time2000ms
Memory256MB
Difficulty
greedyimplementation
English · Original
Chinese · Translation
Formal · Original
Codehorses has just hosted the second Codehorses Cup. This year, the same as the previous one, organizers are giving T-shirts for the winners. The valid sizes of T-shirts are either _"M"_ or from $0$ to $3$ _"X"_ followed by _"S"_ or _"L"_. For example, sizes _"M"_, _"XXS"_, _"L"_, _"XXXL"_ are valid and _"XM"_, _"Z"_, _"XXXXL"_ are not. There are $n$ winners to the cup for both the previous year and the current year. Ksenia has a list with the T-shirt sizes printed for the last year cup and is yet to send the new list to the printing office. Organizers want to distribute the prizes as soon as possible, so now Ksenia is required not to write the whole list from the scratch but just make some changes to the list of the previous year. In one second she can choose arbitrary position in any word and replace its character with some uppercase Latin letter. Ksenia can't remove or add letters in any of the words. What is the minimal number of seconds Ksenia is required to spend to change the last year list to the current one? _The lists are unordered_. That means, two lists are considered equal if and only if the number of occurrences of any string is the same in both lists. ## Input The first line contains one integer $n$ ($1 \le n \le 100$) — the number of T-shirts. The $i$\-th of the next $n$ lines contains $a_i$ — the size of the $i$\-th T-shirt of the list for the previous year. The $i$\-th of the next $n$ lines contains $b_i$ — the size of the $i$\-th T-shirt of the list for the current year. It is guaranteed that all the sizes in the input are valid. It is also guaranteed that Ksenia can produce list $b$ from the list $a$. ## Output Print the minimal number of seconds Ksenia is required to spend to change the last year list to the current one. If the lists are already equal, print _0_. [samples] ## Note In the first example Ksenia can replace _"M"_ with _"S"_ and _"S"_ in one of the occurrences of _"XS"_ with _"L"_. In the second example Ksenia should replace _"L"_ in _"XXXL"_ with _"S"_. In the third example lists are equal.
Codehorses 刚刚举办了第二届 Codehorses 杯。今年和去年一样,主办方将为获胜者发放 T 恤。 有效的 T 恤尺码为 _"M"_,或由 $0$ 到 $3$ 个 _"X"_ 后跟 _"S"_ 或 _"L"_ 组成。例如,尺码 _"M"_、_"XXS"_、_"L"_、_"XXXL"_ 是有效的,而 _"XM"_、_"Z"_、_"XXXXL"_ 是无效的。 去年和今年各有 $n$ 名获奖者。Ksenia 拥有去年杯赛 T 恤尺码的列表,但尚未将今年的列表发送给印刷厂。 主办方希望尽快分发奖品,因此 Ksenia 不需要从头重写整个列表,而只需对去年的列表进行一些修改。每秒她可以选择任意单词中的任意位置,并将其字符替换为某个大写拉丁字母。Ksenia 不能在任何单词中删除或添加字母。 Ksenia 最少需要花费多少秒才能将去年的列表修改为今年的列表? _列表是无序的_。这意味着,当且仅当两个列表中每个字符串的出现次数相同时,这两个列表被认为是相等的。 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— T 恤的数量。 接下来的 $n$ 行中,第 $i$ 行包含 $a_i$ —— 去年列表中第 $i$ 件 T 恤的尺码。 接下来的 $n$ 行中,第 $i$ 行包含 $b_i$ —— 今年列表中第 $i$ 件 T 恤的尺码。 保证输入中的所有尺码均有效。同时保证 Ksenia 可以从列表 $a$ 生成列表 $b$。 请输出 Ksenia 为将去年列表修改为今年列表所需花费的最少秒数。如果两个列表已经相等,请输出 _0_。 在第一个例子中,Ksenia 可以将 _"M"_ 替换为 _"S"_,并将其中一个 _"XS"_ 中的 _"S"_ 替换为 _"L"_。 在第二个例子中,Ksenia 应将 _"XXXL"_ 中的 _"L"_ 替换为 _"S"_。 在第三个例子中,两个列表相等。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— T 恤的数量。接下来的 $n$ 行中,第 $i$ 行包含 $a_i$ —— 去年列表中第 $i$ 件 T 恤的尺码。接下来的 $n$ 行中,第 $i$ 行包含 $b_i$ —— 今年列表中第 $i$ 件 T 恤的尺码。保证输入中的所有尺码均有效。同时保证 Ksenia 可以从列表 $a$ 生成列表 $b$。 ## Output 请输出 Ksenia 为将去年列表修改为今年列表所需花费的最少秒数。如果两个列表已经相等,请输出 _0_。 [samples] ## Note 在第一个例子中,Ksenia 可以将 _"M"_ 替换为 _"S"_,并将其中一个 _"XS"_ 中的 _"S"_ 替换为 _"L"_。在第二个例子中,Ksenia 应将 _"XXXL"_ 中的 _"L"_ 替换为 _"S"_。在第三个例子中,两个列表相等。
**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 100 $, be the number of T-shirts. Let $ A = (a_1, a_2, \dots, a_n) $ and $ B = (b_1, b_2, \dots, b_n) $ be multisets (unordered lists) of T-shirt sizes, where each size is a string from the valid set: $$ \mathcal{S} = \{ \text{"S"}, \text{"M"}, \text{"L"}, \text{"XS"}, \text{"XL"}, \text{"XXS"}, \text{"XXL"}, \text{"XXXS"}, \text{"XXXL"} \} $$ **Constraints** 1. All elements of $ A $ and $ B $ belong to $ \mathcal{S} $. 2. The multisets $ A $ and $ B $ have the same cardinality $ n $. 3. Ksenia may perform character replacements only (no insertions or deletions). 4. The goal is to transform multiset $ A $ into multiset $ B $ with minimal total character replacements. **Objective** Compute the minimal number of character replacements required to transform multiset $ A $ into multiset $ B $, where in one second one character in one string may be replaced by another uppercase Latin letter. Let $ f: \mathcal{S} \to \mathbb{Z}_{\geq 0} $ denote the frequency function of a multiset. Define the multiset difference as: $$ D(s) = f_B(s) - f_A(s), \quad \forall s \in \mathcal{S} $$ Let $ \mathcal{P} = \{ s \in \mathcal{S} \mid D(s) > 0 \} $ (deficit in $ A $), and $ \mathcal{N} = \{ s \in \mathcal{S} \mid D(s) < 0 \} $ (surplus in $ A $). For each pair $ (s, t) \in \mathcal{N} \times \mathcal{P} $, define $ c(s, t) $ as the minimum number of character replacements required to transform string $ s $ into string $ t $. The problem reduces to finding a minimum-cost bipartite matching between surplus and deficit sizes, where the cost of matching a surplus string $ s \in \mathcal{N} $ to a deficit string $ t \in \mathcal{P} $ is $ c(s, t) $, and the total flow is $ \sum_{s \in \mathcal{N}} |D(s)| = \sum_{t \in \mathcal{P}} D(t) $. Let $ \mathcal{F} $ be the set of all feasible flow assignments $ x_{s,t} \in \mathbb{Z}_{\geq 0} $, where: - $ \sum_{t \in \mathcal{P}} x_{s,t} = -D(s) $ for all $ s \in \mathcal{N} $, - $ \sum_{s \in \mathcal{N}} x_{s,t} = D(t) $ for all $ t \in \mathcal{P} $. Then the minimal number of seconds is: $$ \min_{\mathcal{F}} \sum_{s \in \mathcal{N}} \sum_{t \in \mathcal{P}} x_{s,t} \cdot c(s, t) $$
Samples
Input #1
3
XS
XS
M
XL
S
XS
Output #1
2
Input #2
2
XXXL
XXL
XXL
XXXS
Output #2
1
Input #3
2
M
XS
XS
M
Output #3
0
API Response (JSON)
{
  "problem": {
    "name": "A. Codehorses T-shirts",
    "description": {
      "content": "Codehorses has just hosted the second Codehorses Cup. This year, the same as the previous one, organizers are giving T-shirts for the winners. The valid sizes of T-shirts are either _\"M\"_ or from $0$",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1000A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Codehorses has just hosted the second Codehorses Cup. This year, the same as the previous one, organizers are giving T-shirts for the winners.\n\nThe valid sizes of T-shirts are either _\"M\"_ or from $0$...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Codehorses 刚刚举办了第二届 Codehorses 杯。今年和去年一样,主办方将为获胜者发放 T 恤。\n\n有效的 T 恤尺码为 _\"M\"_,或由 $0$ 到 $3$ 个 _\"X\"_ 后跟 _\"S\"_ 或 _\"L\"_ 组成。例如,尺码 _\"M\"_、_\"XXS\"_、_\"L\"_、_\"XXXL\"_ 是有效的,而 _\"XM\"_、_\"Z\"_、_\"XXXXL\"_ 是无效的。\n\n去年和今年各有 $n$ ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 100 $, be the number of T-shirts.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ and $ B = (b_1, b_2, \\dots, b_n) $ be multisets (unordered lists) of ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments