{"problem":{"name":"J. The Kamphaeng Phet's Chedis","description":{"content":"A chedi (also known as stupa, dagoba, or pagoda) is a relic usually shaped as a conic tower built over the remains of someone Buddhists consider important. Some historical Thai sites have dozens such ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10104J"},"statements":[{"statement_type":"Markdown","content":"A chedi (also known as stupa, dagoba, or pagoda) is a relic usually shaped as a conic tower built over the remains of someone Buddhists consider important. Some historical Thai sites have dozens such structures, dedicated to monks or nuns or other religious leaders (known as bhikkhu - ภกษณ, in Thailand). For instance, in Kamphaeng Phet some chedi inscriptions refer to Garuda (ครฑ), and similarly in Si Satchanalai and Sukhothai.\n\nThe differences between some Thai symbols are very subtle, making it hard for experts to analyze words. For instance, when any symbol of the word Ramakien (รามเกยรต) is changed, its meaning is altered completely. Since many of the sites are over 700 years old, the inscriptions are very worn.\n\nAn example is the pair of inscriptions below, found in distinct chedis: \n\n จดตงขโกดยพระบรมษพทธานญาต \n\nThe method works as follows. Let a = a1 a2... aN and b = b1 b2... bM be two inscriptions with N and M characters, respectively. The parameter called difference is initially set to zero. At each step, we analyze a pair (ai, bj) of characters with 1 ≤ i ≤ N + 1 and 1 ≤ j ≤ M + 1, starting with (a1, b1). Assume aN + 1 and bM + 1 are null characters.\n\nDuring each step, there are four possible actions you can take: \n\nThe experts consider that, the smaller the computed difference, the higher correspondence between the inscriptions. They want you to write a program to compute the minimum expected difference between two inscriptions.\n\nThe first line has a single integer T, the number of test cases.\n\nEach test case starts with 3 integers N, M, and K, where N is the length of the first inscription and M is the length of the second inscription. The next two lines contain, respectively, the first and second inscription. An inscription is a string of characters from _a_ to _z_.\n\n*Limits* \n\nFor each test case, print a real number, the minimum expected difference between two inscriptions. The error should not exceed 10 - 4.\n\n## Input\n\nThe first line has a single integer T, the number of test cases.Each test case starts with 3 integers N, M, and K, where N is the length of the first inscription and M is the length of the second inscription. The next two lines contain, respectively, the first and second inscription. An inscription is a string of characters from _a_ to _z_.*Limits*   1 ≤ T ≤ 500  1 ≤ N, M ≤ 3·103  The sum of N and M over all test cases will not exceed 1.2·104.  0 ≤ K ≤ 105 \n\n## Output\n\nFor each test case, print a real number, the minimum expected difference between two inscriptions. The error should not exceed 10 - 4.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k, M_k \\in \\mathbb{Z}^+ $ denote the lengths of two strings.  \n- Let $ A_k = a_1 a_2 \\dots a_{N_k} $ and $ B_k = b_1 b_2 \\dots b_{M_k} $ be strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \n- Define $ a_{N_k+1} = \\varepsilon $, $ b_{M_k+1} = \\varepsilon $ as null characters.\n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unspecified} $  \n2. $ 1 \\le N_k, M_k \\le \\text{unspecified} $  \n3. All characters in $ A_k, B_k $ are lowercase English letters.\n\n**Objective**  \nCompute the minimum edit distance (Levenshtein distance) between $ A_k $ and $ B_k $, where the allowed operations are:  \n- Insertion: cost 1  \n- Deletion: cost 1  \n- Substitution: cost 1  \n\nThat is, find the minimum number of single-character edits to transform $ A_k $ into $ B_k $.\n\n$$\nD(k) = \\min_{\\text{edit sequences}} \\sum \\text{cost of operations}\n$$\n\nEquivalently, define $ \\text{dp}[i][j] $ as the minimum edit distance between $ a_1\\dots a_i $ and $ b_1\\dots b_j $, with recurrence:  \n$$\n\\text{dp}[i][j] = \n\\begin{cases}\ni & \\text{if } j = 0 \\\\\nj & \\text{if } i = 0 \\\\\n\\min \\begin{cases}\n\\text{dp}[i-1][j] + 1 & \\text{(delete)} \\\\\n\\text{dp}[i][j-1] + 1 & \\text{(insert)} \\\\\n\\text{dp}[i-1][j-1] + \\mathbb{I}(a_i \\ne b_j) & \\text{(substitute)}\n\\end{cases} & \\text{otherwise}\n\\end{cases}\n$$\n\nOutput $ D(k) = \\text{dp}[N_k][M_k] $ for each test case.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10104J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}