E. Equivalent

Codeforces

IDCF10162E

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Guga was bored, so he decided to read the dictionary and learned a new word: _madam_, _hannah_, _x_ e _redivider_ are examples of palindromes. Analyzing some words, Guga realized the most of them weren't palindromes and decided to create a new category called _K-Palindrome_, defined as follows: For example, _xyz_ is not a palindrome, but is a 1-Palindrome, because we can substitute the x with a z and obtain _zyz_. On the other hand, _abcb_ is neither a palindrome nor a 1-Palindrome, but it is a 2-Palindrome, for we can substitute two letters and obtain a palindrome. With this new definition, Guga was able to find many more words that satisfied it. While researching on palindromes, Guga discovered the following problem: given a string S, how many continuous substrings of S are palindromes? Intrigued, he decided to create an equivalent problem: given a string S and an integer K, how many continuous substrings of S are K-palindromes? Guga thinks it's very easy to find a wrong answer to his problem with large strings, and want a computer program that solve it. Help Guga (: Each test case consists of two lines. The first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes. The second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S. The output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes. By definition: ## Input Each test case consists of two lines.The first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes.The second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S. ## Output The output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes. [samples] ## Note By definition: Every _K-Palindrome_ is also a _K'-Palindrome_, where K' > K. Every palindrome is a 0-palindrome.

**Definitions** Let $ S $ be a string of length $ n $, with $ S[i] \in \{a, b, \dots, z\} $ for $ i \in \{1, \dots, n\} $. Let $ K \in \mathbb{Z} $, $ 0 \leq K \leq \lfloor n/2 \rfloor $. A substring $ S[i:j] $ (with $ 1 \leq i \leq j \leq n $) is a **$ K $-palindrome** if the minimum number of character substitutions required to make it a palindrome is at most $ K $. **Constraints** 1. $ 1 \leq |S| \leq 3000 $ 2. $ 0 \leq K \leq \lfloor |S|/2 \rfloor $ **Objective** Count the number of contiguous substrings $ S[i:j] $ such that the edit distance (under substitution only) from $ S[i:j] $ to some palindrome is $ \leq K $. Equivalently, for each substring $ T = S[i:j] $, let $ d(T) $ be the minimum number of substitutions needed to make $ T $ a palindrome. Then: $$ X = \left| \left\{ (i,j) \mid 1 \leq i \leq j \leq n,\ d(S[i:j]) \leq K \right\} \right| $$ where $$ d(T) = \sum_{k=1}^{\lfloor |T|/2 \rfloor} \mathbb{1}_{T[k] \neq T[|T|+1-k]} $$

API Response (JSON)

{
  "problem": {
    "name": "E. Equivalent",
    "description": {
      "content": "Guga was bored, so he decided to read the dictionary and learned a new word:  _madam_, _hannah_, _x_ e _redivider_ are examples of palindromes. Analyzing some words, Guga realized the most of them w",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10162E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Guga was bored, so he decided to read the dictionary and learned a new word: \n\n_madam_, _hannah_, _x_ e _redivider_ are examples of palindromes.\n\nAnalyzing some words, Guga realized the most of them w...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S $ be a string of length $ n $, with $ S[i] \\in \\{a, b, \\dots, z\\} $ for $ i \\in \\{1, \\dots, n\\} $.  \nLet $ K \\in \\mathbb{Z} $, $ 0 \\leq K \\leq \\lfloor n/2 \\rfloor $.  \n\nA sub...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments