B. Balala Power!

Codeforces

IDCF10225B

Time2000ms

Memory128MB

Difficulty—

English · Original

Formal · Original

Talented Mr. Tang has $n$ strings consisting of only lowercase letters. He wants to charge them with Balala Power (he could change each letter ranged from '_a_' to '_z_' into any number ranged from $0$ to $25$, but every two different letters must not be changed into the same number) so that he could casually calculate the sum of these strings as integers in the base of $26$. Mr. Tang wants you to maximize the sum. Note that no string in this problem can have any leading zeros when regarded as integers, except for the string "_0_". Therefore, he guarantees that at least one type of letter would not appear at the beginning of any given string. The sum may be quite large, so you should output it modulo $(10^9 + 7)$ instead. The input contains multiple (about $20$) test cases. For each test case, the first line contains an integer $n$ ($1 <= n <= 10^5$), indicating the number of strings. The $i$-th of the next $n$ lines contains a string $s_i$ ($1 <= | s_i | <= 10^5$) consisting of only lowercase letters. It is guaranteed that $sum_{i = 1}^n | s_i | <= 10^6$ for each test case. For each test case, output "_Case #x: y_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case. ## Input The input contains multiple (about $20$) test cases.For each test case, the first line contains an integer $n$ ($1 <= n <= 10^5$), indicating the number of strings.The $i$-th of the next $n$ lines contains a string $s_i$ ($1 <= | s_i | <= 10^5$) consisting of only lowercase letters. It is guaranteed that $sum_{i = 1}^n | s_i | <= 10^6$ for each test case. ## Output For each test case, output "_Case #x: y_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case. [samples]

**Definitions** Let $ a, b \in \Sigma^* $ be two strings over the lowercase English alphabet, representing reserved areas on each riverside, with $ |a|, |b| \leq 10^3 $. Each character $ a_i \in a $ and $ b_j \in b $ denotes the squad assigned to the $ i $-th and $ j $-th area on the left and right riverside, respectively. **Constraints** Bridges may only connect areas assigned to the same squad. No two bridges may cross: if bridge $ (i, j) $ connects $ a_i $ to $ b_j $ and bridge $ (i', j') $ connects $ a_{i'} $ to $ b_{j'} $, then $ i < i' \iff j < j' $. **Objective** Find the maximum number of non-crossing bridges such that each bridge connects $ a_i $ to $ b_j $ with $ a_i = b_j $. This is equivalent to computing the **Longest Common Subsequence (LCS)** of strings $ a $ and $ b $.

API Response (JSON)

{
  "problem": {
    "name": "B. Balala Power!",
    "description": {
      "content": "Talented Mr. Tang has $n$ strings consisting of only lowercase letters. He wants to charge them with Balala Power (he could change each letter ranged from '_a_' to '_z_' into any number ranged from $0",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10225B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Talented Mr. Tang has $n$ strings consisting of only lowercase letters. He wants to charge them with Balala Power (he could change each letter ranged from '_a_' to '_z_' into any number ranged from $0...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\Sigma^* $ be two strings over the lowercase English alphabet, representing reserved areas on each riverside, with $ |a|, |b| \\leq 10^3 $.  \nEach character $ a_i \\in a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments