{"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 weren't palindromes and decided to create a new category called _K-Palindrome_, defined as follows: \n\nFor 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.\n\nWith this new definition, Guga was able to find many more words that satisfied it.\n\nWhile researching on palindromes, Guga discovered the following problem: given a string S, how many continuous substrings of S are palindromes?\n\nIntrigued, he decided to create an equivalent problem: given a string S and an integer K, how many continuous substrings of S are K-palindromes?\n\nGuga 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 (:\n\nEach test case consists of two lines.\n\nThe 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.\n\nThe second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S.\n\nThe output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes.\n\nBy definition: \n\n## Input\n\nEach 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.\n\n## Output\n\nThe output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes.\n\n[samples]\n\n## Note\n\nBy definition:   Every _K-Palindrome_ is also a _K'-Palindrome_, where K' > K.  Every palindrome is a 0-palindrome.","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 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 $.  \n\n**Constraints**  \n1. $ 1 \\leq |S| \\leq 3000 $  \n2. $ 0 \\leq K \\leq \\lfloor |S|/2 \\rfloor $  \n\n**Objective**  \nCount 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 $.  \n\nEquivalently, for each substring $ T = S[i:j] $, let $ d(T) $ be the minimum number of substitutions needed to make $ T $ a palindrome. Then:  \n$$\nX = \\left| \\left\\{ (i,j) \\mid 1 \\leq i \\leq j \\leq n,\\ d(S[i:j]) \\leq K \\right\\} \\right|\n$$  \nwhere  \n$$\nd(T) = \\sum_{k=1}^{\\lfloor |T|/2 \\rfloor} \\mathbb{1}_{T[k] \\neq T[|T|+1-k]}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10162E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}