You are given a sequence of balls A by your teacher, each labeled with a lowercase Latin…
- User
You are given a sequence of balls A by your teacher, each labeled with a lowercase Latin letter 'a'-'z'. You don't like the given sequence. You want to change it into a new sequence, B that suits you better. So, you allow yourself four operations:
- You can insert any ball with any label into the sequence at any position.
- You can delete (remove) any ball from any position.
- You can replace any ball with any other ball.
- You can exchange (swap) two adjacent balls.
Your teacher now places time constraints on each operation, meaning that an operation can only be performed in certain time. So, the first operation takes time ti, the second one takes td, the third one takes tr and the fourth one takes te. Also, it is given that 2·te ≥ ti + td.
Find the minimal time to convert the sequence A to the sequence B. Input
The first line contains four space-separated integers ti, td, tr, te (0 < ti, td, tr, te ≤ 100). The following two lines contain sequences A and B on separate lines. The length of each line is between 1 and 4000 characters inclusive.
Output
Print a single integer representing minimum time to convert A into B.
Examples
Input
1 1 1 1 youshouldnot thoushaltnot
Output
5
Input
2 4 10 3 ab ba
Output
3
Input
1 10 20 30 a za
Output
1
Note
In the second sample, you could delete the ball labeled 'a' from the first position and then insert another 'a' at the new second position with total time 6. However exchanging the balls give total time 3.
Assistant
We need to find minimum cost to transform string A into string B using insert, delete, replace, and swap of adjacent characters. Costs: ti (insert), td (delete), tr (replace), te (swap). Also given 2*te >= ti+td, meaning swapping two adjacent elements is at least as costly as deleting one and inserting one (or replace? Actually delete+insert). That ensures certain optimality properties: swapping is not too cheap.
We have to consider classic edit distance with insert/delete/replace (Levenshtein) plus adjacent swap. The swap operation can exchange two adjacent characters. It essentially allows us to fix transpositions. However, note that swap only exchanges adjacent positions; it can be used to simulate a move of a character at a cost that might be less than delete+insert? But given the constraint 2te >= ti+td, it's not cheaper than deleting one and inserting the other, but could be cheaper than two separate operations if we need to swap them? Actually, if you have two adjacent characters that are reversed, you could either replace them (two replacements) or delete+insert? But swap is a specific operation that exchanges them. The inequality suggests that swapping is at least as expensive as a delete followed by an insert (which would also achieve swapping but with extra steps? Let's think: To swap two adjacent characters, you could delete one, then insert it on the other side. That would involve one delete and one insert, costing td+ti. But that would change the order? Actually, if you delete char at position i, then all characters after shift left; then you insert the deleted char at position i+1? That would achieve swap but with cost td+ti. So swapping should cost at most td+ti (since you could do that). The inequality 2te >= ti+td ensures that te is not less than (ti+td)/2, so te could be less than td+ti? Actually if ti=2, td=4, then ti+td=6, so te >=3, so te could be 3, which is less than 6. So swap can be cheaper than delete+insert. However the inequality gives lower bound, not upper bound. Actually "2·te ≥ ti + td" means te >= (ti+td)/2. So swap cost is at least half the sum of insert and delete. It could be less than ti+td if ti+td is large, e.g., ti=100, td=100, then (ti+td)/2=100, so te >= 100. So te could be 100, equal to half, not less. But the sum is 200, so te=100 is less than 200. So swap could be cheaper than delete+insert (since 200 > 100). So swap can be advantageous.
We also need to consider that swap might be used to effectively move a character further away by a series of swaps, but that would cost te per adjacent swap. However, moving a character a distance d by swaps costs dte. Comparing with delete+insert: delete the character and insert at new position costs td+ti. So if dte < td+ti, then swapping could be cheaper. But also we can consider using swap in combination with other operations.
We need to compute minimum cost edit distance with these operations. Both strings lengths up to 4000, so O(n^2) is possible (16 million). But need careful DP.
We have insert, delete, replace costs, and swap of adjacent characters. However, note that swap operation only exchanges two adjacent characters. In classic edit distance DP, we consider operations that modify one character at a time. Swap of adjacent characters involves two positions. It is like a transposition. This is similar to Damerau–Levenshtein distance with adjacent transposition cost. However, in standard Damerau-Levenshtein, you can swap adjacent characters and then continue DP with condition that the two characters are equal to the two in the other string, etc. But there the cost is 1 per transposition, but here we have arbitrary costs and also we can combine with other ops.
We need to design a DP that incorporates adjacent swap. Since strings length up to 4000, we can do DP with O(nm). But standard Damerau-Levenshtein with transpositions can be done with O(nm) time and O(n*m) memory if we keep additional data. However, typical implementation for Damerau–Levenshtein with adjacent transpositions uses a DP table and also tracks last occurrence of each character to allow transposition with a formula: if a[i] == b[j-1] and a[i-1] == b[j] then we can consider dp[i-2][j-2] + cost_transposition. But that only works when the transposition is on the last two characters. This is correct for edit distance where only adjacent swaps are allowed, but it's more complex: The classic Damerau–Levenshtein distance (with adjacent transpositions) allows insertion, deletion, substitution, and transposition of two adjacent characters. The recurrence is:
dp[i][j] = min( dp[i-1][j] + delete_cost (del a[i]), dp[i][j-1] + insert_cost (insert b[j]), dp[i-1][j-1] + (a[i] == b[j] ? 0 : replace_cost), if i>1 and j>1 and a[i] == b[j-1] and a[i-1] == b[j] then dp[i-2][j-2] + transposition_cost )
But careful: The transposition operation swaps a[i-1] and a[i] to match b[j-1] and b[j]. After swapping, they both match. So it assumes we are aligning the two positions in order after swap. Also, it assumes that no other edits are done in between? The classic DP works.
We need to adapt to costs: delete = td, insert = ti, replace = tr, swap = te.
But there is a nuance: The inequality 2*te >= ti+td is given to ensure that it's never beneficial to do a swap and then a delete/insert combination that would be cheaper? Actually, it ensures that the DP with transposition as described is correct? In standard Damerau-Levenshtein, there is a known issue that the naive recurrence may not be optimal for arbitrary costs if the transposition cost is too low relative to insert/delete, because it might be cheaper to do a transposition plus an insertion/deletion than a direct operation? But they gave that constraint to guarantee that the classic recurrence works? Or perhaps to avoid the need for more complex handling.
I recall that for edit distance with adjacent transpositions, if the cost of transposition is less than the sum of insertion and deletion, then you might want to use a transposition to simulate a deletion and insertion of a character? But a transposition exchanges two characters; it's not a deletion+insertion. However, if transposition cost is too low, you could swap a character with a placeholder? Not allowed. Actually, the constraint ensures that it's never beneficial to use a swap to "move" a character by multiple swaps rather than delete+insert? Wait, if we want to move a character from position i to j, we could do a series of adjacent swaps costing (distance)te. Compare with td+ti. The constraint 2te >= ti+td means that for moving a character one position (distance 1), cost te >= (ti+td)/2, which could be less than ti+td, but moving by d positions costs dte. For large d, dte could exceed td+ti if te > (ti+td)/2? Actually, if te = (ti+td)/2 + epsilon, then dte < td+ti for d=1 but for d=2, 2te >= ti+td (by equality or greater). So moving a character by 2 positions costs at least ti+td. So any movement beyond 1 swap is at least as expensive as delete+insert. Thus, it's never beneficial to move a character more than one position by swaps because the cost would be at least delete+insert. This simplifies the DP: only adjacent swaps (transpositions) are potentially beneficial; longer sequences of swaps are not needed because you can achieve the same effect with delete+insert at lower cost. Also, performing multiple swaps intermixed with other operations might create better combos, but likely the constraint ensures that the optimal solution can be represented by the classic DP with transpositions only considered for directly adjacent mismatched pairs.
But we must be careful: Could there be a scenario where swapping two non-adjacent characters via multiple swaps, combined with other edits, yields lower cost? For example, you might want to reorder the string by swapping many times, but the cost per swap is moderate. However, given the inequality, a series of k swaps costs kte. If we want to move a character by d positions, we need at least d swaps, costing dte. Since 2te >= ti+td, we have te >= (ti+td)/2. So dte >= d*(ti+td)/2. For d>=2, d*(ti+td)/2 >= (ti+td) because d/2 >=1. So dte >= ti+td. So moving a character by two or more positions via swaps costs at least as much as deleting it and inserting it at the target location (which costs td+ti). Thus, it's never better to move a character more than one position using swaps. However, you might also consider moving a character while also adjusting others; but if you have to reorder many characters, it might still be cheaper to use multiple swaps? But if each character movement beyond one position can be replaced by delete+insert, the total cost of swaps might be higher. However, what about moving two characters? For example, to transform "ab" to "ba", we can swap adjacent -> cost te. That's moving both characters? Actually swap exchanges them. That's moving each by one position. So it's exactly d=1 for each. For longer permutations, like "abc" to "cba"? You could swap a and b -> "bac", then swap b and c -> "bca", then swap b and c? Actually to get "cba", you might need multiple swaps. But moving 'a' from position 1 to 3 would require two swaps (or moving via two swaps). That costs 2te. Since 2te >= ti+td, we could instead delete 'a' and insert at end costing td+ti, which might be equal or less. And also we need to move 'c' from position 3 to 1, which also could be done with two swaps or delete+insert. However, maybe using two swaps total? Actually to transform "abc" to "cba", you could swap 'a' and 'b' -> "bac", then swap 'a' and 'c'? But after first swap, we have b a c. To get c b a, we need to move c to front. Swap a and c -> b c a; then swap b and c -> c b a. That's 3 swaps. So cost 3te. Alternatively, we could delete 'a' and insert at end, and delete 'c' and insert at front: cost 2*(td+ti). If te is just slightly above (ti+td)/2, then 3te could be > 2(ti+td)? Actually 3te >= 1.5(ti+td) >? 2*(ti+td) is bigger; so 3te might be less than 2(ti+td) if te is small enough? Let's check: Suppose ti=td=1 => ti+td=2, (ti+td)/2=1, te could be 1 (since 21=2 >=2). Then 3te=3, 2*(ti+td)=4, so swaps cheaper. But wait, we assumed 2te >= ti+td. With ti=td=1, te can be 1, then 2te=2, which is >=2. So condition holds. For d=2, 2te =2, which equals ti+td=2. So moving a character two positions via two swaps costs exactly 2, same as delete+insert. For moving a character three positions via three swaps, cost=3, while delete+insert costs 2. So for distance 3, swaps are more expensive if ti+td=2 and te=1 (since 3 > 2). Actually 3 > 2, so delete+insert cheaper. So for longer distances, swaps become more expensive. So it's not beneficial to move a character more than 1 position if you consider only that character's movement; but if you have many characters moving, you might get some synergy? However, the classic Damerau-Levenshtein algorithm only considers transpositions of adjacent characters that are adjacent in both strings? Actually, the transposition operation aligns the two characters swapped only if they are next to each other in both strings, but they might be further apart originally. The recurrence uses dp[i-2][j-2] + cost, assuming that the two characters are matched in a crossed way. That works for single adjacent swap, not for a sequence of swaps. However, you could achieve a longer permutation through a series of swaps; but given the cost structure, it's never optimal to use more than one swap between any pair of characters? Not exactly. But there is known result: For edit distance with insert, delete, replace, and adjacent transposition, if the transposition cost is at least the average of insert and delete (i.e., 2te >= ti+td), then the optimal edit distance can be computed by the classic DP (with the transposition recurrence). Actually I'm not entirely certain, but many problems with such operations use DP with states (i,j) and consider swap only for i>1, j>1 condition, and it's sufficient given the inequality. This is reminiscent of the classic "edit distance with swap" problem (e.g., Codeforces problem). Let's search memory: I recall a problem "Edit distance with swap" on Codeforces? Actually there is a known problem: "Edit Distance" with costs and swap operation. It is also on USACO? There is a problem "edit" where you have costs and swap. Usually solution uses DP with O(n^2) and an extra array to handle swaps efficiently. The condition 2*te >= ti+td ensures that you never need to consider swapping non-adjacent characters.
We can adopt DP as follows: Let dp[i][j] = min cost to transform prefix A[1..i] to prefix B[1..j] (1-indexed). Standard recurrence:
dp[i][j] = min( dp[i-1][j] + td, // delete A[i] dp[i][j-1] + ti, // insert B[j] dp[i-1][j-1] + (A[i]==B[j] ? 0 : tr) // replace or match )
Then also if i>1 and j>1 and A[i] == B[j-1] and A[i-1] == B[j] then we can consider dp[i-2][j-2] + te.
But note: After swapping, we might need to consider that the swapped characters are now correctly placed, but there could be other edits in between? The recurrence above is classic.
However, there is a nuance: The swap operation as described might not be sufficient if we consider cases where we swap and then edit one of the swapped characters. But the DP with the condition covers exactly aligning the two pairs as they are after swap. Additional edits can be accounted by the DP states before the swap (i-2, j-2). So it should be correct.
But there might be more complex scenarios: For instance, you could swap two characters that are not adjacent in the strings? No, swap operation only exchanges adjacent balls, so it only directly affects two adjacent positions in the current sequence. If we want to simulate a swap of two characters that are not adjacent, we would need multiple swaps. As argued, due to the cost constraint, it's not optimal to do multiple swaps when you can delete and insert. So we can ignore sequences of swaps longer than one.
Nevertheless, is there a scenario where you would swap, then delete or insert something in between, then swap again? That would be covered by DP because DP considers sequences of operations. But the classic recurrence only considers a swap as a single operation that aligns two pairs at once. However, DP can combine operations: e.g., after a swap, you might delete a character. But DP can represent that because dp[i][j] is defined as min cost to transform prefix A[1..i] to B[1..j] using any sequence. The recurrence with transposition essentially says that if we align the last two characters via a swap, we then need to transform A[1..i-2] to B[1..j-2]. That assumes no other edits interleaved between the swap and the prefix transformation, but that is okay because any operations can be reordered? Typically in edit distance DP, we consider operations applied from left to right, but the recurrence is correct because any sequence of operations transforming A[1..i] to B[1..j] can be considered based on the last operation applied to the rightmost characters. The swap operation is one of those possible last operations. However, one must ensure that the swap operation is only considered when the two last characters in A correspond to the two last characters in B after swap. But what if we have a sequence where we swap two characters, then later insert something after them? Then the swap wouldn't be the last operation; the insertion would be. In DP, we can consider the last operation as insertion, not swap. So eventually we consider all possibilities.
Thus the recurrence is valid.
But we must also consider that the swap operation may be used not only when A[i]==B[j-1] and A[i-1]==B[j] but also maybe when one of the characters is later deleted or something. That would be covered by other operations.
Thus we can compute dp with O(nm). However, n and m up to 4000, so nm up to 16e6, which is okay memory if using 2 rows? But we need dp[i-2][j-2] for swap, which requires access to two rows back. If we use only two rows (rolling), we need to keep at least the previous two rows? Actually we need dp[i-1][j] (previous row same column), dp[i][j-1] (current row previous column), dp[i-1][j-1] (previous row previous column), and dp[i-2][j-2] (two rows back, two columns back). With rolling rows, we can keep three rows: dp for current i, previous i-1, and i-2. But also we need dp[i][j-1] from current row, so we need to fill row left to right. For dp[i-2][j-2], we need value from two rows ago at column j-2. That's doable if we keep an array for row i-2 as we go. So memory O(min(n,m)2?) Actually we need O(m) per row, and we keep three rows: prev2, prev1, cur. That's O(3m) which is fine (3*4000 ~ 12k). But careful: we need to access dp[i-2][j-2], which is from prev2 row at index j-2. As we fill cur row from left to right, j-2 is already computed (since j increasing). So we have prev2[j-2] available. So three rows suffice.
But also need to consider that lengths of A and B may differ; we can treat dp with rows = lenA+1, cols = lenB+1. That's 4001*4001 = 16 million if we store full matrix; that's about 16M * 4 bytes = 64 MB, which might be borderline but possibly acceptable in C++ but in Python it would be huge (list of lists of ints: each int ~28 bytes => >400 MB). So we definitely need to use space optimization (rolling rows) to fit in Python. 16 million Python integers is too much. So we must implement with only O(min(n,m)) memory, using either two or three rows. But as we need dp[i-2][j-2], we need three rows. So we can allocate three lists of length (lenB+1). That's fine.
However, there is a catch: The swap condition also requires checking if A[i] == B[j-1] and A[i-1] == B[j]. That's easy if we have A and B strings.
Now, is there any other nuance? The inequality also might affect whether we need to consider the possibility that a swap could be simulated by a delete and insert (or replace) in a way that could be cheaper than the swap operation. But that's fine; our DP will consider all possibilities and choose min.
But wait, the swap operation as defined exchanges two adjacent balls in the current sequence. This corresponds to transposing two characters. However, we might also consider a swap plus a replace? For example, if you have two adjacent characters that are not exactly matching the target after swap, you could swap and then replace one of them. Could that be cheaper than just replacing both? Our DP should be able to represent that because we can first swap then replace one, but that would be two operations: swap then replace. The DP recurrence includes the possibility of doing a replace after swap? Actually the DP recurrence for dp[i][j] considers the last operation. If we swap the last two and then later replace one, then the last operation might be replace, not swap. So eventually the DP will consider that path. For example, transform A="ab" to B="cd". Could we swap then replace both? That would be swap (cost te) then replace a to c? But after swap we have "ba". Then we need to replace 'b' with 'c' and 'a' with 'd' (two replaces). So total cost te+2tr. DP could also do replace both directly: 2tr. Or delete+insert etc. So DP will compare. The swap-only case considered in recurrence only applies when the swapped characters exactly match the target (i.e., A[i]==B[j-1] and A[i-1]==B[j]), then dp[i-2][j-2] + te is an option. But if they don't exactly match, we wouldn't use that direct swap; we might still use swap as part of a series, but that series can be decomposed into other operations.
One potential tricky case: What if swapping two characters and then replacing one is cheaper than directly replacing both? For example, suppose tr is high, te is low, and the characters after swap are close to target but not exact. For example, A="ab", B="xb". If we swap, we get "ba", then replace 'b' with 'x'? Actually B is "xb": first char x, second b. Swapping gives "ba". To get "xb", we could replace 'b'->'x' and keep 'a'? That would be "xa", not "xb". So not good. But consider A="ab", B="ba". That's exact after swap. For non-exact, perhaps we could swap then replace one: A="ac", B="ca". Swapping gives "ca", matches exactly. So exact match after swap. For non-exact, swapping might still reduce number of replacements: e.g., A="ab", B="bc". Swapping gives "ba". Then we need to change 'b' to 'b' (ok) and 'a' to 'c' -> replace 'a' with 'c' costing tr. So total te+tr. Alternative: replace 'a' with 'b' and 'b' with 'c' (two replaces) = 2tr. Or delete 'a', insert 'c' etc. So if te+tr < 2tr i.e., te < tr, then swapping + replace could be beneficial. But our DP recurrence for swap only considers case where both match after swap. In this example, after swap we have "ba" and target "bc". The last two characters: A[i] = 'b' (since after swap the last character is originally A[i-1]? Wait careful: In DP, we are aligning prefixes. For i=2 (A[1]='a', A[2]='b'), j=2 (B[1]='b', B[2]='c'). The condition A[i]==B[j-1]? A[2]=='b', B[1]=='b' -> true. A[i-1]==B[j]? A[1]=='a', B[2]=='c' -> false. So condition fails. So our recurrence would not consider dp[i-2][j-2] + te because swap would not make both match. However, maybe we could still use a swap as part of transformation? Let's think: Starting with "ab". To get "bc", we could swap to get "ba". Now we have "ba". Then we need to transform "ba" into "bc". That is an edit distance between "ba" and "bc": we could replace the second character 'a' with 'c' (cost tr). So total cost = te + tr. This is a sequence of operations: swap then replace. How would DP capture that? In DP, when we compute dp[2][2] for "ab"->"bc", we consider the option of doing a replace on the last character: dp[1][1] + cost of replace A[2] with B[2] (since A[2]='b', B[2]='c', replace cost tr). dp[1][1] would be cost to convert "a" to "b". That could be replace (a->b) cost tr. So dp[2][2] would consider tr+tr = 2tr. But what about the swap then replace path? That path corresponds to: first swap (cost te), resulting in "ba". Then replace the second character 'a' with 'c' (cost tr). After swap, we have "ba". Now we need to align with "bc". In DP terms, we can think of performing a swap operation that consumes two characters from A and produces two characters in B? Actually, after swap, the two characters become 'b' and 'a', but they are not yet aligned with B's two characters. We could then replace the second 'a' to 'c', which corresponds to a replace operation that changes the second character. But the swap operation is applied before the replace. How to represent that in DP over prefixes? The classic DP considers the last operation. If the last operation is replace on the last character, then before that we had transformed A[1..i-1] to B[1..j-1] after some edits. But if we swapped first, the ordering of operations might be: we swap the two characters (changing the order), then we replace the second character. After these operations, the final alignment of A's characters to B's is not necessarily one-to-one in original index order. However, edit distance DP inherently assumes that we process strings from left to right, and operations affect the string in order. But swapping disrupts the order. However, the DP with transposition recurrence works because it considers that the two characters are interchanged and then matched to B's two characters in reverse order. That's only when both match exactly after swap. If after swap they don't both match, then the swap alone does not complete the transformation; we need further edits on those two positions. But could we model that as a transposition plus a replacement on one of the transposed characters? In standard Damerau–Levenshtein distance, the transposition operation is defined as swapping two adjacent characters, with the assumption that after swap they match their counterparts. It does not consider transposition plus substitution. However, you can still achieve transposition plus substitution by using other combinations: e.g., first a replace on one character, then a swap, or a swap then a replace, etc. In DP, these combinations should be captured by sequences of operations, but the DP recurrence as given might be insufficient to capture cases where a swap is beneficial but the resulting characters are not exactly matching, because the direct swap-only recurrence doesn't apply. Yet, the sequence of swap then replace could be captured by considering a replace after a swap, but the DP might represent it as a replace operation on a later state that includes the swap effect implicitly? For instance, to get "ab"->"bc", we could think: from dp[i-2][j-2]? Not exactly. Perhaps we need to consider more general operation: swapping two characters and then optionally editing them. However, we can simulate swap+replace by doing a replace then a swap? Let's try: "ab" to "bc". We could first replace 'b' with 'c' -> "ac". Then swap 'a' and 'c'? That would give "ca", not "bc". Not good. Or replace 'a' with 'b' -> "bb", then swap? swapping does nothing, then replace second 'b' with 'c' -> "bc". That would be replace (a->b) cost tr, then replace (b->c) cost tr = 2tr. Not swap. Alternatively, delete 'a', insert 'c' -> "cb"? That's not either.
Maybe swap+replace could be represented as: first swap (ab->ba) then replace second (a->c). How can DP represent that? At the state where we've processed some prefixes, after swap we have "ba". That corresponds to the fact that we have consumed two characters of A (the original 'a' and 'b') and produced two characters of B? But after swap we haven't yet produced the final B characters; we still have "ba" which needs to be edited to "bc". So effectively, the transformation of "ab" to "bc" can be seen as: transform A[1..i-2]? Not exactly, because after swap, the characters are rearranged. To map to DP, we might need to consider that we can match A[i-1] to B[j] and A[i] to B[j-1] after a swap, but then we need to possibly change one of them. That is like a "swap with replacement" operation. Some extended edit distances allow for a "swapped match with substitution" but not standard.
Given the constraints and the inequality, perhaps such combination is never optimal? Let's examine with costs to see if there could be a case where swap+replace is better than other combos, and if the DP as described fails to capture it. Suppose tr is very high (like 100), te is low (like 1), ti and td moderate. Example: ti=50, td=50, tr=100, te=1 (satisfies 2te=2 >= 100? Actually ti+td=100, so 2te=2 < 100, condition fails because 2te >= ti+td is required. So te cannot be that low relative to ti+td. Condition forces te >= (ti+td)/2. So if ti+td is large, te is at least half that. For tr, there's no direct constraint. So tr could be arbitrarily high relative to te. For example, ti=1, td=1, so ti+td=2, so te >=1. So te could be 1, tr=100. That satisfies 2te=2 >= 2. So we have cheap swaps, expensive replacements. Consider A="ab", B="bc". As argued, swap+replace costs te+tr=1+100=101. Alternative: replace both: 2*100=200. Delete+insert: delete 'a' (td=1), insert 'b' at beginning? Actually to get "bc", from "ab": we could delete 'a' (1), then we have "b", then insert 'c' at end (ti=1) -> "bc"? That would be "b" then insert 'c' gives "bc". Wait we need "b" then "c". After deleting 'a', we have "b". Then we need to insert 'c" after 'b', costing ti=1, total 2. That's cheaper! Indeed, delete+insert is cheap (2). So swap+replace is not optimal. But consider a scenario where delete+insert are also expensive, but tr is even more expensive. However, the condition ensures te is not too low relative to ti+td, but ti+td could be large, making te also large. If ti+td=100, then te>=50. If tr=200 (very high), then swap+replace cost = 50+200=250, delete+insert=100, so delete+insert cheaper. If tr is moderately high, maybe swap+replace could be cheaper than delete+insert? Let's try ti=100, td=100 -> ti+td=200, so te>=100. So te=100. tr=150. For A="ab", B="bc": swap+replace = 100+150=250; delete+insert=200; still delete+insert cheaper. If tr=120, then swap+replace=220, delete+insert=200, delete+insert still cheaper. If tr=180, swap+replace=280, delete+insert=200. So delete+insert seems always cheaper when ti+td=200, te=100? Actually te could be 100 exactly, so swap+replace=100+tr. Delete+insert=200. So if tr<100, then swap+replace<200. But tr could be less than 100? Yes, tr can be less than ti or td. Example: ti=100, td=100, tr=50, te=100. Then swap+replace=150, delete+insert=200, so swap+replace is cheaper. So in this case, maybe we need to consider swap+replace. But is it optimal? Let's compute A="ab", B="bc". We could also do: replace 'a' with 'b' (50), replace 'b' with 'c' (50) =100. That's even cheaper. So replacement cheaper. So swap+replace not beneficial.
But what about a case where both replacements are expensive but one of the characters after swap already matches, so we only need to replace one. Could that be cheaper than two replacements? Yes if tr > te? For example, tr=100, te=1 (but te cannot be 1 if ti+td are not tiny). Let's find parameters that satisfy condition and make swap+replace possibly better than two replacements, but also better than delete+insert and other combos.
Set ti=1, td=1 -> ti+td=2, so te >=1. So te=1 (minimum). tr=3. Then A="ab", B="bc": swap+replace=1+3=4; two replaces=6; delete+insert=2. So delete+insert cheapest (2). So swap+replace not best. If we make delete/insert more expensive: ti=5, td=5 -> ti+td=10, te >=5. So te=5, tr=6. Then swap+replace=11; two replaces=12; delete+insert=10. So delete+insert cheaper. If ti=5, td=5, te=5, tr=4: swap+replace=9; two replaces=8; delete+insert=10; so two replaces cheapest. So swap+replace not best.
What about A="ab", B="ca"? Not sure.
Maybe there is a scenario where swap+replace is optimal. Let's attempt to design: Suppose ti and td are both high, te moderate, tr moderate. For swap+replace to be better than two replaces: te+tr < 2*tr => te < tr. So te < tr. Also must be better than delete+insert: te+tr < ti+td => te < ti+td - tr. Since ti+td likely > tr? Not necessarily. Also better than other combos like delete one and replace other etc.
Let ti=100, td=100 => ti+td=200. If tr=150, te < 150 (say te=100). Then te+tr=250, 2tr=300, delete+insert=200. So delete+insert still better. To have te+tr < ti+td, we need te+tr < ti+td => if ti+td=200, tr=150, te=49 (but te >= (ti+td)/2=100, so te cannot be 49). So te at least 100. So te+tr >= 250 >200. So delete+insert is always <=? Actually if ti+td is fixed, te >= (ti+td)/2, then te+tr >= (ti+td)/2 + tr. For this to be < ti+td, we need tr < ti+td - (ti+td)/2 = (ti+td)/2. So tr must be less than half the sum. But then two replaces cost 2tr, which might be even smaller. For example, ti=100, td=100 => half=100. If tr=80 (<100), then te>=100. So te+tr >=180. ti+td=200, so delete+insert=200, so swap+replace could be 180 <200, but also two replaces=160, which is even smaller. So two replaces better. If tr is very low, two replaces is cheap. So swap+replace not optimal.
But maybe there is a scenario where only one replacement is needed after swap, while other alternatives need two operations (like two replacements or delete+insert + something). But we found two replacements always costs 2tr, which may be less than te+tr if te<tr. However if te < tr, two replacements costs 2tr, but te+tr could be less than 2tr, yes. But we also have delete+insert costing ti+td. For swap+replace to be optimal, we need te+tr < min(2tr, ti+td, ...). So te+tr < 2tr => te < tr. Also te+tr < ti+td => tr < ti+td - te. Since te >= (ti+td)/2, then ti+td - te <= ti+td - (ti+td)/2 = (ti+td)/2. So we need tr < (ti+td)/2. Also te < tr, but te >= (ti+td)/2, so we need (ti+td)/2 <= te < tr, and tr < (ti+td)/2. That's impossible because tr < (ti+td)/2 and te >= (ti+td)/2, so te >= (ti+td)/2 > tr? Actually if tr < (ti+td)/2, then (ti+td)/2 > tr, so te >= something > tr, so te > tr, contradicting te < tr. So under the constraint 2te >= ti+td, it is impossible for te+tr to be simultaneously less than ti+td and less than 2tr? Let's double-check: For te+tr < ti+td and te+tr < 2tr, we need:
- te+tr < ti+td
- te+tr < 2*tr => te < tr.
From 2, te < tr. From 1, tr < ti+td - te. Since te < tr, then tr < ti+td - te => adding te both sides: te+tr < ti+td, that's the same. Now using te >= (ti+td)/2 (from 2te >= ti+td => te >= (ti+td)/2). Then plug into te < tr: (ti+td)/2 <= te < tr, so tr > (ti+td)/2. From 1: tr < ti+td - te. Since te >= (ti+td)/2, then ti+td - te <= (ti+td)/2. So tr < something <= (ti+td)/2. So we have tr > (ti+td)/2 (from te < tr and te >= (ti+td)/2) and tr < (ti+td)/2. Contradiction. Therefore, under given constraint, it is impossible for te+tr to be strictly less than both ti+td and 2tr. Hence swap+replace can never be better than both two replacements and delete+insert at the same time. But could it be better than one of them while the other is not applicable? In DP, we consider all possibilities, and the min will pick the best. So if swap+replace is not better than the minimum of two replacements and delete+insert, then it's not optimal globally. However, there could be combinations where two replacements aren't possible because one character might match after swap? Actually two replacements are always possible: you can replace each character individually. So that cost is always an option (2tr). Delete+insert is always an option (td+ti). So swap+replace can never beat both, so it will never be the absolute minimum under the constraint. That's a key observation! Therefore, we do not need to consider swap+replace as a combined operation; the DP with the transposition only for exact match is sufficient, because any path involving a swap followed by a replace on one of the swapped characters would be at least as costly as either two replaces or delete+insert. Similarly, what about swap+delete or swap+insert? Possibly similar reasoning.
But we must also consider scenarios where swapping allows a character to match for free (no replace) and the other character may be deleted or inserted. For example, A="ab", B="b". We could swap to get "ba", then delete last 'a'? Actually target is "b". We could delete 'a' from original "ab" -> "b", cost td. Or we could swap then delete 'a'? Starting "ab", swap -> "ba". Then delete last character 'a'? That yields "b", cost te+td. Since te >= (ti+td)/2, te+td >= (ti+td)/2 + td. Compare with td alone: we need te+td > td obviously. So not better. Or we could delete 'b' and insert? Not.
What about A="ab", B="a". Could swap then delete? "ab" -> swap -> "ba", then delete 'b'? That yields "a", cost te+td. Compare with delete 'b' directly (td). So worse.
So swap combined with other ops likely not beneficial due to inequality.
Now, consider a swap plus replace on both? That would be swap+2replace, which is obviously worse than 2replace.
Thus, the only beneficial direct swap is when after swap both characters match exactly, i.e., we can align two positions with a single operation. The classic recurrence captures that.
But is there a scenario where swapping two characters that are not adjacent in the original strings (but become adjacent after some deletions/insertions) could be beneficial? For example, you could delete some characters in between to bring two characters together, swap them, then reinsert others. This would be a more complex sequence. Does DP with the simple condition account for that? Possibly not, but the inequality might again make such sequences non-optimal. Let's analyze.
Suppose we have A = "axb", B = "bxa". Want to exchange a and b but there's an x in between. We could delete x (cost td), then swap a and b (cost te), then insert x back (ti). Total cost = td+te+ti. Could this be cheaper than other strategies? Alternatives: directly replace a->b and b->a? That's two replaces cost 2tr. Or delete a and insert a at end? Actually from "axb" to "bxa": one method: delete 'a', insert 'a' at end: cost td+ti -> "xb" + insert 'a' => "xba"? Not "bxa". Or delete x, etc. More systematically, edit distance with only insert/delete/replace would cost? We can compute: LCS? Maybe three operations. But the swap after deletion could be beneficial if te is low. Let's test with numbers: ti=2, td=3, tr=10, te=4. Check condition: 2te=8, ti+td=5, so 8>=5 holds. So te=4, ti=2, td=3, tr=10. Then td+te+ti = 3+4+2=9. Two replaces: 20. Other combos? Could delete a (3), insert b at front (2) -> "bxa"? Starting "axb": delete a -> "xb". Insert b at front -> "bxb". Replace middle x with x? Actually we need "bxa": after "bxb", replace second b with a? That would cost 10, total 3+2+10=15. Or delete b, insert a? Not. So the swap after delete x seems promising: delete x (3), then swap a and b? After delete x, we have "ab". Swap gives "ba". Then insert x in middle? Actually we need "bxa". After swap we have "ba". Insert x between b and a (ti=2) gives "bxa". So total cost: delete x (3) + swap (4) + insert x (2) = 9. That's cheaper than two replaces (20) and cheaper than other combos.
Now does the classic DP with swap condition (i>1,j>1, A[i]==B[j-1], A[i-1]==B[j]) capture this? Let's simulate: A="axb", B="bxa". Indices: A[1]='a', A[2]='x', A[3]='b'; B[1]='b', B[2]='x', B[3]='a'.
We want to consider dp[3][3]. The swap condition would require checking i>1 and j>1 and A[i]==B[j-1] and A[i-1]==B[j]. For i=3, j=3: A[3]=='b', B[2]=='x' -> false. So no direct swap. But what about after deletions/insertions? In DP, we consider state dp[i][j] as the min cost to transform prefix A[1..i] to prefix B[1..j]. The optimal sequence we described: delete A[2] (x) -> cost 3, then we have transformed A[1..3]? Actually after deleting x, we effectively have string "ab". But in DP terms, deletion of a character from A reduces the remaining prefix? Standard DP: When we delete A[i], we move to state (i-1, j). So to achieve our sequence, we might do: from dp[3][3], we could consider having deleted A[2] at some point. But let's see if DP can capture the swap after deletion. The sequence of operations we described:
- Delete A[2] (x) => cost td, resulting string: "ab". (Now we have consumed A[2]? Actually after deletion, we have processed A[1] and A[3]? But the order of operations matters; we can think of editing the string; DP considers any order.
In DP, we can model:
- First, consider dp[i-1][j] + td: delete current A[i] (if we decide to delete it at the end). But in our plan, we deleted the middle character (A[2]) before handling the ends. However, DP recursion allows any order because it's based on aligning prefixes. For the final alignment of full strings, we can think of aligning A[3] with B[3] etc. Let's attempt to see if DP can yield cost 9.
Compute DP table manually with these costs. We'll do DP[0..3][0..3].
Define dp[i][j] = min cost to convert A[1..i] to B[1..j].
Base: dp[0][0]=0. dp[i][0] = i * td (delete all). dp[0][j] = j * ti (insert all).
Now compute:
A:1='a',2='x',3='b' B:1='b',2='x',3='a'
ti=2, td=3, tr=10, te=4.
Compute row by row.
i=0: j=0:0 j=1:2 j=2:4 j=3:6
i=1 (A[1]='a'): j=0: td*1 =3 j=1: min( dp[0][1]+ti? Actually delete? Let's compute: from dp[0][1] + ti? Wait dp[i-1][j] + td = dp[0][1] + 3 = 2+3=5 (delete a) dp[i][j-1] + ti = dp[1][0] + 2 = 3+2=5 (insert b) dp[i-1][j-1] + (a==b?0:tr) = dp[0][0] + tr =0+10=10 swap not applicable (i<2) ) => min=5. So dp[1][1]=5.
j=2 (B[2]='x'): delete: dp[0][2] +3 =4+3=7 insert: dp[1][1] +2 =5+2=7 replace: dp[0][1] + (a==x?10) =2+10=12 =>7 j=3 (B[3]='a'): delete: dp[0][3]+3=6+3=9 insert: dp[1][2]+2=7+2=9 replace: dp[0][2] + (a==a?0) =4+0=4? Wait dp[0][2]=4, and A[1]=='a', B[3]=='a' so match cost 0 -> 4. So dp[1][3]=4.
i=2 (A[2]='x'): j=0: 2*td=6 j=1 (B[1]='b'): delete: dp[1][1] +3 =5+3=8 insert: dp[2][0] +2 =6+2=8 replace: dp[1][0] + (x==b?10) =3+10=13 swap: i>1,j>1? j=1 not >1 => no. =>8 j=2 (B[2]='x'): delete: dp[1][2] +3 =7+3=10 insert: dp[2][1] +2 =8+2=10 replace: dp[1][1] + (x==x?0) =5+0=5 =>5 j=3 (B[3]='a'): delete: dp[1][3] +3 =4+3=7 insert: dp[2][2] +2 =5+2=7 replace: dp[1][2] + (x==a?10) =7+10=17 swap: i>1,j>1? i=2,j=3>1, check A[2]==B[2]? A[2]='x', B[2]='x' -> true? Actually condition: A[i]==B[j-1] (A[2]==B[2]? j-1=2, B[2]='x', true) and A[i-1]==B[j] (A[1]=='a', B[3]=='a', true). So condition holds! Wait, for i=2, j=3, we have A[2]=='x', B[2]=='x', and A[1]=='a', B[3]=='a'. That satisfies A[i]==B[j-1] and A[i-1]==B[j]. So we can consider transposition: dp[i-2][j-2] + te = dp[0][1] + 4 = 2 + 4 = 6. So dp[2][3] = min(7,7,17,6) = 6.
So dp[2][3] = 6.
i=3 (A[3]='b'): j=0: 3*td=9 j=1 (B[1]='b'): delete: dp[2][1] +3 =8+3=11 insert: dp[3][0] +2 =9+2=11 replace: dp[2][0] + (b==b?0) =6+0=6 swap: i>1,j>1? j=1 no. =>6 j=2 (B[2]='x'): delete: dp[2][2] +3 =5+3=8 insert: dp[3][1] +2 =6+2=8 replace: dp[2][1] + (b==x?10) =8+10=18 swap: i=3,j=2>1? check A[3]==B[1]? A[3]='b', B[1]='b' true; A[2]==B[2]? A[2]='x', B[2]='x' true -> condition holds (since A[i]==B[j-1]? j-1=1, B[1]='b' true; A[i-1]==B[j]? A[2]=='x', B[2]=='x' true). So dp[i-2][j-2]+te = dp[1][0]+4 = 3+4=7. So dp[3][2] = min(8,8,18,7)=7. j=3 (B[3]='a'): delete: dp[2][3] +3 =6+3=9 insert: dp[3][2] +2 =7+2=9 replace: dp[2][2] + (b==a?10) =5+10=15 swap: i>1,j>1? i=3,j=3: check A[3]==B[2]? A[3]='b', B[2]='x' false -> no swap. Also maybe consider other swap? No. So dp[3][3] = min(9,9,15) = 9.
Thus DP gives 9, which matches our manual plan cost (delete x, swap, insert x) = 9. But note that the swap operation was used not directly on the original A[2] and A[3]? Actually the swap that contributed to dp[2][3] (when i=2,j=3) was between A[1] and A[2]? Wait dp[2][3] considered swap: A[2] (x) and A[1] (a) swapped to match B[2] (x) and B[3] (a). That corresponds to swapping the first two characters after deletion? In our plan, we deleted x first, then swapped a and b. That's different: In DP, at state (2,3), we have processed first two characters of A (a,x) and first three characters of B (b,x,a). The swap considered aligns A[1] and A[2] with B[2] and B[3] (x and a). That essentially swapped a and x? But we need a and b swapped, not a and x. However, the DP ended up with total cost 9, and we can trace back to see the operations: dp[3][3] came from delete (dp[2][3] + td) or insert (dp[3][2] + ti) both 9. It could be that the optimal path is: from dp[2][3]=6, then delete A[3] (b) cost 3 -> total 9. But dp[2][3]=6 came from swap? Actually dp[2][3] = 6 via swap from dp[0][1]=2 + te=4. Let's trace: dp[0][1]=2 (insert 'b'? Actually dp[0][1]=2 means empty->'b': insert 'b' cost 2). Then swap cost 4, giving state (2,3). That swap corresponds to taking A[1..2] = "ax" and B[1..3]="bxa"? Wait swap operation consumes two characters from A and two from B? Actually the swap transition uses dp[i-2][j-2] + te. Here i-2=0, j-2=1, so from empty A prefix and B prefix of length 1, we add a swap operation that transforms the next two characters of A into the next two characters of B. But that would require that the two A characters are 'a' and 'x' and the two B characters are 'x' and 'a'? Actually the swap aligns A[i-1],A[i] with B[j],B[j-1] after swap. So from state (0,1), we have already matched B[1] (which is 'b'). Then we take A[1]='a' and A[2]='x', swap them to become 'x','a' which match B[2]='x' and B[3]='a'. So this corresponds to: after having inserted 'b' at beginning (cost 2), we then swap the next two characters (a and x) to match x and a. That results in string: 'b' + after swap: 'x','a' => "bxa". That's exactly the target B. But what about A[3]='b'? In this path, we never used A[3]. That means we must delete A[3] (the 'b') because we have an extra character. Indeed, from dp[2][3]=6 we then delete A[3] costing td=3 to reach dp[3][3]=9. So the full sequence:
- Start with A="axb".
- Insert 'b' at beginning? Wait we need to see order of operations: The path suggests: first, we insert 'b' at beginning? Actually dp[0][1] indicates we transformed empty string to 'b' by inserting 'b'. But we started with "axb", not empty. So the DP is aligning prefixes; the state dp[0][1] means we have consumed 0 characters from A and produced 1 character of B (i.e., we have inserted a 'b' before processing any of A). Then we take the first two characters of A ("a" and "x") and swap them (cost te) to produce "xa" which matches B[2] and B[3]. So after swap, we have consumed A[1],A[2] and produced B[2],B[3]. So total we have produced B[1..3]="bxa". Then we still have A[3]='b' left, which we delete (cost td). So operations: Insert 'b', swap a and x, delete last b. That yields final string "bxa". Total cost: ti (insert b) =2? Actually insert b cost ti=2, te=4, td=3 = total 9. But is that sequence valid? Let's simulate: Start with "axb". Insert 'b' at beginning -> "baxb". Swap a and x? Which adjacent? We need to swap a and x to get "bxa". But after insertion, we have "b a x b". To swap a and x, they are adjacent positions 2 and 3: swap them -> "b x a b". Then delete last b -> "b x a". That's indeed "bxa". So it works. So the DP found a valid sequence.
Thus, even though we initially thought about deleting x, swapping a and b, then inserting x, the DP found an alternative: insert b, swap a and x, delete b. That is different but still yields cost 9. So the DP with the simple swap recurrence is capable of capturing complex interleavings of insert/delete with swap.
Thus, the DP recurrence seems sufficient.
Now, we need to implement efficiently. Since lengths up to 4000, we can do O(nm) with rolling rows. However, O(nm) with n,m up to 4000 is 16 million operations, which in Python is okay if optimized (maybe borderline but should pass with typical time limit 2 sec? But 16 million simple operations and Python loops might be okay with PyPy; we can aim for about 0.1-0.2 micro? Actually 16 million with inner loop doing few operations is okay; we need to be careful about using Python lists and loops.
We'll implement DP with three rows: dp_prev2, dp_prev1, dp_cur. Initialize dp_prev2 and dp_prev1 as lists of length (m+1). We'll iterate i from 0 to n, where i denotes number of characters from A considered. We'll maintain:
- For i=0: dp_cur = [j*ti for j in range(m+1)] (since insert all)
- Then for i>=1, we compute dp_cur based on dp_prev1 (i-1) and dp_prev2 (i-2).
But we also need to handle base case when i=1, we have no i-2; then swap not applicable.
We'll have A and B as strings; use 0-index but careful with indices.
Let n = len(A), m = len(B). We'll use 1-indexed for DP convenience: dp[i][j] for i from 0..n, j from 0..m. A[i] refers to character at position i (1-indexed). We can store A as list with dummy at index 0.
We'll maintain three lists: prev2 (for i-2), prev1 (for i-1), cur (for i). We'll start with i=0: cur = [j*ti for j in range(m+1)]. Then set prev2 = None? Actually for i=1, we need prev1 = dp[0] (the row we just computed). For i=1, we also need prev2 for swap? swap condition requires i>=2, so for i=1 we don't need prev2. So we can set prev2 initially as some list of length m+1 with large values? But we won't access it if i<2, we just need to ensure we don't use it. We'll handle conditionally.
Implementation steps:
- Read ti, td, tr, te.
- Read A, B strings.
- n = len(A), m = len(B)
- Convert A to list with a leading placeholder, e.g., " "+A, same for B to " "+B.
- Initialize prev1 as list of length m+1: for j in range(m+1): prev1[j] = jti (since dp[0][j] = jti).
- For i from 1 to n:
- Create cur list of length m+1.
- cur[0] = i * td (delete all first i chars).
- For j from 1 to m:
Compute delete cost (from row above)
del_cost = prev1[j] + td # dp[i-1][j] + tdInsert cost
ins_cost = cur[j-1] + ti # dp[i][j-1] + tiReplace or match
if A[i] == B[j]: repl_cost = prev1[j-1] # no cost else: repl_cost = prev1[j-1] + tr best = min(del_cost, ins_cost, repl_cost)Swap condition: i >= 2 and j >= 2 and A[i] == B[j-1] and A[i-1] == B[j]
if i >= 2 and j >= 2 and A[i] == B[j-1] and A[i-1] == B[j]: swap_cost = (prev2[j-2] if prev2 is not None else INF) + te if swap_cost < best: best = swap_cost cur[j] = best - After finishing row i, update prev2 = prev1, prev1 = cur, then continue.
At the end, answer = prev1[m] (since after i=n, prev1 holds row n).
But we need to handle the case when we use prev2 for i=2 onwards. So we can initialize prev2 before loop as None, and after first row (i=1) we set prev2 = dp[0]?? Actually after computing i=1, we need for i=2, prev2 should be row 0. So we need to store row 0 as prev1 initially. Then after i=1, we set prev2 = row0, prev1 = row1. So we can do:
prev2 = None (or a placeholder) prev1 = [j*ti for j in range(m+1)] # row0
Then loop i from 1 to n: cur = [0](m+1) cur[0] = itd for j in 1..m: compute as above, using prev1 and (if i>=2) prev2. after loop, set prev2 = prev1, prev1 = cur.
But careful: For i=1, we have prev1 = row0, prev2 is None. In swap condition we check i>=2, so we won't access prev2. Good.
Now, one more nuance: The swap operation could be simulated by a delete+insert pair? But we already handle it via the inequality. However, is there any need to consider that performing a swap might be cheaper than two deletes and two inserts? But DP will capture it.
But we must also consider the possibility of using a swap operation when the two characters are equal? If A[i] == A[i-1] and they both equal B[j] and B[j-1]? But swap does nothing, cost te, which is likely >0, so not beneficial. But DP will still consider, but min will avoid.
Now, what about using a swap to exchange two characters that are not originally adjacent but after some insertions/deletions they become adjacent? That's effectively captured by the DP because we can intermix insert/delete with swap. The DP state considers prefixes, meaning we process strings from left to right. If we want to bring two characters together by deleting something in between, that corresponds to skipping some characters (deleting them) before processing the two characters. In DP, if we delete a character, we move to next i without consuming a B character, effectively removing it. So later we can consider swapping the next two. So it's captured.
Thus the DP should be correct.
Now, one more nuance: The inequality 2*te >= ti+td may also be used to ensure that we don't need to consider using swap to simulate a replacement? For example, if we swap a character with a neighbor and then replace one of them, we argued it's not beneficial. But the DP as is does not consider that, and that's fine because it's not optimal under the constraint.
Now, let's test with provided examples.
Example 1: ti=1, td=1, tr=1, te=1 A = "youshouldnot" B = "thoushaltnot" Output 5.
We can run mental? We trust DP.
Example 2: 2 4 10 3 ab ba Output 3. Compute DP: n=2,m=2. ti=2,td=4,tr=10,te=3. dp[0][0]=0 dp[0][1]=2, dp[0][2]=4 dp[1][0]=4 dp[1][1]: min( dp[0][1]+4=2+4=6, dp[1][0]+2=4+2=6, dp[0][0]+ (a==b?10) =0+10=10) =>6 dp[1][2]: j=2 B='a'? Actually B is "ba", so B[1]='b', B[2]='a'. For i=1 (A[1]='a'), j=2 (B[2]='a'): delete: dp[0][2]+4=4+4=8 insert: dp[1][1]+2=6+2=8 replace: dp[0][1]+ (a==a?0)=2+0=2 =>2 dp[2][0] = 2*4=8 dp[2][1]: i=2 (A[2]='b'), j=1 (B[1]='b'): delete: dp[1][1]+4=6+4=10 insert: dp[2][0]+2=8+2=10 replace: dp[1][0]+ (b==b?0)=4+0=4 swap: i>=2,j>=2? j=1 no. =>4 dp[2][2]: i=2,j=2 (A[2]='b', B[2]='a'): delete: dp[1][2]+4=2+4=6 insert: dp[2][1]+2=4+2=6 replace: dp[1][1]+ (b==a?10)=6+10=16 swap: i>=2,j>=2 and A[2]==B[1]? A[2]='b', B[1]='b' true; A[1]==B[2]? A[1]='a', B[2]='a' true => dp[0][0]+te=0+3=3 So dp[2][2]=3. matches output.
Example 3: 1 10 20 30 a za Output 1. Compute: ti=1, td=10, tr=20, te=30. A="a", B="za" (lengths:1 and 2). The answer 1 suggests it's cheaper to insert 'z' at front (ti=1) than replace? Actually delete+insert? Let's see DP: n=1,m=2. dp[0][0]=0 dp[0][1]=1, dp[0][2]=2 dp[1][0]=10 dp[1][1]: min( dp[0][1]+10=1+10=11, dp[1][0]+1=10+1=11, dp[0][0]+ (a==z?20)=20 ) =11 dp[1][2]: min( dp[0][2]+10=2+10=12, dp[1][1]+1=11+1=12, dp[0][1]+ (a==a?0)=1+0=1 ) =>1. So answer 1. matches.
Thus DP works for examples.
Now, we need to ensure we handle the inequality correctly? Not needed for DP, but we rely on it to avoid missing better sequences with multiple swaps? But DP already considers only single adjacent swap per operation. However, could there be an optimal sequence that uses two consecutive swaps (i.e., swapping two pairs) that is not captured because each swap is considered separately? But the DP would capture that because after the first swap, the state advances by two characters, and later another swap could be applied on later characters. For example, to transform "abc" to "cba", we could do: swap a and b -> bac, swap a and c? Actually we need three swaps? Let's compute optimal under given costs. Suppose costs: ti=2, td=2, tr=100, te=3, and 2*te=6 >= ti+td=4, holds. A="abc", B="cba". DP should find min. Let's test manually:
Option 1: three swaps? Actually we can do: swap b and c -> acb, then swap a and c? Actually from "abc": swap b and c -> "acb", then swap a and c -> "cab"? Not "cba". Another sequence: swap a and b -> "bac", swap a and c -> "bca", swap b and c -> "cba". That's 3 swaps, cost 9. Option 2: delete a and insert a at end: delete a (2), insert a (2) -> "bc" + insert a => "bca"? Actually start "abc", delete first a => "bc", insert 'a' at end => "bca". Then swap b and c? That's 2+2+3=7. Option 3: delete c and insert at front: delete c (2) -> "ab", insert 'c' at front (2) -> "cab", then swap a and b? That gives "cba"? Actually "cab", swap a and b -> "cba" cost 2+2+3=7. Option 4: replace all three? 3*100=300. Option 5: maybe a combination. So optimal is 7. Can DP achieve 7? Let's compute DP with n=3,m=3.
We'll do quick: ti=2, td=2, tr=100, te=3.
A: a b c B: c b a
dp[0][0]=0 dp[0][1]=2, dp[0][2]=4, dp[0][3]=6 dp[1][0]=2 dp[1][1] (a to c): min(del: dp[0][1]+2=2+2=4, ins: dp[1][0]+2=2+2=4, rep: dp[0][0]+100=100) =4. dp[1][2] (a to cb): j=2 B[2]=b? Actually B[1]=c, B[2]=b. So dp[1][2] = min(del: dp[0][2]+2=4+2=6, ins: dp[1][1]+2=4+2=6, rep: dp[0][1]+ (a==b?100)=2+100=102) =6. dp[1][3] (a to cba): min(del: dp[0][3]+2=6+2=8, ins: dp[1][2]+2=6+2=8, rep: dp[0][2]+ (a==a?0)=4+0=4) =4.
dp[2][0]=4 dp[2][1] (ab to c): i=2, j=1 (B[1]=c): min(del: dp[1][1]+2=4+2=6, ins: dp[2][0]+2=4+2=6, rep: dp[1][0]+ (b==c?100)=2+100=102, swap: i>=2? j=1 no) =6. dp[2][2] (ab to cb): i=2,j=2 (B[2]=b): min(del: dp[1][2]+2=6+2=8, ins: dp[2][1]+2=6+2=8, rep: dp[1][1]+ (b==b?0)=4+0=4, swap: check A[2]==B[1]? A[2]=b, B[1]=c false) =>4. dp[2][3] (ab to cba): i=2,j=3 (B[3]=a): del: dp[1][3]+2=4+2=6 ins: dp[2][2]+2=4+2=6 rep: dp[1][2]+ (b==a?100)=6+100=106 swap: i>=2,j>=2 and A[2]==B[2]? A[2]=b, B[2]=b true; A[1]==B[3]? A[1]=a, B[3]=a true -> condition holds. Then swap cost = dp[0][1] + te = dp[0][1]? i-2=0, j-2=1 => dp[0][1]=2 +3=5. So min=5? Actually 5 < 6, so dp[2][3]=5. But wait dp[0][1] is 2, plus te=3 =5. So dp[2][3]=5.
Now dp[3][0]=6 dp[3][1] (abc to c): i=3,j=1: del: dp[2][1]+2=6+2=8 ins: dp[3][0]+2=6+2=8 rep: dp[2][0]+ (c==c?0)=4+0=4 swap: i>=2 but j=1 no. =>4 dp[3][2] (abc to cb): i=3,j=2 (B[2]=b): del: dp[2][2]+2=4+2=6 ins: dp[3][1]+2=4+2=6 rep: dp[2][1]+ (c==b?100)=6+100=106 swap: i>=2,j>=2 check A[3]==B[1]? A[3]=c, B[1]=c true; A[2]==B[2]? A[2]=b, B[2]=b true -> condition holds. Then swap cost = dp[1][0] + te = dp[1][0]=2 +3=5. So dp[3][2]=5. dp[3][3] (abc to cba): del: dp[2][3]+2=5+2=7 ins: dp[3][2]+2=5+2=7 rep: dp[2][2]+ (c==a?100)=4+100=104 swap: check A[3]==B[2]? A[3]=c, B[2]=b false; also check A[3]==B[2]? Actually condition is A[i]==B[j-1] and A[i-1]==B[j]. For i=3,j=3: A[3]==B[2]? c vs b false, so no. Also what about swap on i=3,j=3 with i-1,i? Could there be another swap? No. So min = 7. Thus DP gives 7, matching our manual optimum. So DP works.
Thus we can implement this DP.
Now, complexity: O(n*m). With n,m up to 4000, 16 million loops. In Python, if we do simple operations, it should be okay with PyPy (maybe 0.3-0.5 seconds per 10 million, 16 million maybe 0.8-1 sec). Also we need to handle three rows and condition checks. Should be fine.
Memory: three lists of size up to 4001: about 12k integers, trivial.
Edge Cases: Ensure we handle the case when ti, td, tr, te up to 100, but costs could be zero? Problem says 0 < ti, td, tr, te ≤ 100, so positive. So all operations have positive cost.
Now, about the inequality: do we need to consider that sometimes using two swaps might be cheaper than a delete+insert? But we argued due to inequality, not beneficial for distance>1. But the DP might still consider sequences of multiple swaps through successive applications of the swap transition. That's fine because each swap is considered separately and DP will combine them. For example, in the "abc" to "cba" we used two swaps? Actually the optimal path found by DP used swap at (2,3) and swap at (3,2) but we got total cost 7 via delete or insert? Actually dp[3][3] came from delete (dp[2][3]+td) which is 5+2=7. And dp[2][3]=5 came from swap (dp[0][1]+te). So the solution is: insert? Actually interpreting: dp[2][3]=5 from dp[0][1]+te: means we inserted one character? dp[0][1] is insert 'c'? Wait we can trace: dp[0][1]=2 (insert 'c'?). B[1]='c', so we inserted 'c' before any A chars. Then swap on A[1],A[2] (a,b) to match B[2],B[3] (b,a) cost te=3. That consumes first two A chars and produces B[2],B[3]. So we have transformed: inserted c, swapped a and b -> string "cba"? Actually after those, we have consumed A[1],A[2] and have produced B[1..3] = "cba"? Let's see: B[1] is c (inserted), B[2] is b, B[3] is a (from swap). So we have the full B already, but we still have A[3]='c' leftover, which we delete (cost td=2). So total 2+3+2=7. That's one swap. So not multiple swaps. Could we have a path with two swaps? Possibly if costs favor, but DP would find it if it's cheaper. For example, if te is very low relative to td+ti? But the constraint limits te's lower bound, but te could be exactly (ti+td)/2, which might make two swaps as cheap as delete+insert? For moving a character two positions, 2*te could equal ti+td. So both options are equal. DP would pick either. So that's fine.
Thus DP seems correct.
Now we need to implement carefully with Python.
We'll define INF as a large number, maybe 10**9.
Pseudo-code:
def min_time(ti, td, tr, te, A, B): n, m = len(A), len(B) # add sentinel at beginning to use 1-indexing A = ' ' + A B = ' ' + B # prev1 corresponds to row 0 prev1 = [j * ti for j in range(m+1)] prev2 = None # for i-2 row for i in range(1, n+1): cur = [0] * (m+1) cur[0] = i * td for j in range(1, m+1): # delete A[i] cost_del = prev1[j] + td # insert B[j] cost_ins = cur[j-1] + ti # replace or match if A[i] == B[j]: cost_rep = prev1[j-1] else: cost_rep = prev1[j-1] + tr best = min(cost_del, cost_ins, cost_rep) # swap if i >= 2 and j >= 2 and A[i] == B[j-1] and A[i-1] == B[j]: # need prev2 row swap_cost = prev2[j-2] + te if swap_cost < best: best = swap_cost cur[j] = best # shift rows prev2 = prev1 prev1 = cur return prev1[m]
Test with examples.
But we need to consider also possibility that performing a swap could be simulated by a delete+insert pair (cost td+ti). Since we have that option via DP (delete and insert separately), the min will pick the smallest.
Now, is there any scenario where performing two swaps on overlapping positions (like swapping a with b, then swapping b with c) might be beneficial and not captured because the DP's swap transition only aligns two characters at a time? But we can chain swaps: e.g., to transform "abc" to "cba", we could use two swaps: swap a,b then swap b,c? Actually that's three swaps? Let's see: start "abc". Swap a,b -> "bac". Swap a,c? positions 2 and 3? Actually after first swap, string is "bac". Now we want "cba". Swap b and a? That would give "abc" again. Hmm. Actually to get "cba", we might need three swaps. But DP with single swap and insert/delete gave 7. Could there be a sequence with two swaps? Suppose we swap b and c first: "acb". Then swap a and c: "cab"? Not "cba". Then swap a and b? "cba"? That's three swaps. So two swaps insufficient.
But consider "abcd" to "badc"? Not needed.
I think DP is fine.
Now we must ensure that the inequality is used to guarantee that we don't need to consider the possibility of swapping non-adjacent characters by using a swap operation on characters that are not originally adjacent but after some inserts/deletes become adjacent. However, the DP with prefix alignment already can simulate bringing characters together via deletions and insertions, and then applying a swap. So it's covered.
One more nuance: In the swap transition, we used dp[i-2][j-2] + te. However, some formulations of Damerau–Levenshtein distance also consider the possibility of doing a swap after a replace or something, but they have an additional condition that the characters being swapped are not equal to avoid redundant swaps. But we don't need that; it's fine.
Now, double-check the swap condition: It requires that A[i] == B[j-1] and A[i-1] == B[j]. This matches the scenario where the last two characters of A, when swapped, match the last two characters of B. It assumes that no edits are applied to those two characters other than the swap. But if we had previously inserted or deleted something in between, then the alignment of these characters might not be the last two. However, DP processes prefixes, so by the time we consider state (i,j), we have consumed i characters of A and j of B. The swap operation as a last step means that we took the last two characters of A (i-1,i) and the last two characters of B (j-1,j) and swapped the A characters to match B. That implies that before this, we transformed A[1..i-2] to B[1..j-2]. So it's exactly the recurrence.
Thus implementation as above is correct.
Now, consider the memory: using three lists of length up to 4001, fine.
Now, we need to think about performance: The inner loop has a few operations, but we also have condition checks and list accesses. Might be okay.
Potential micro-optimizations:
- Use local variables for costs, row references.
- Pre-store A and B as arrays of chars for faster access? But strings indexing is O(1).
- Use range and avoid function calls.
We'll implement straightforwardly.
Edge Cases:
- If A and B are empty? The problem says length between 1 and 4000 inclusive, so at least 1. So no empty strings. But we still handle 0 in DP for base.
Now, I'll produce final answer.
But before final, let's test with random small strings and compare with a brute-force for verification? Not needed.
But let's also consider if there could be a situation where using swap after an insertion before the two characters might be beneficial and not captured because the DP swap requires i and j to be at least 2. But that's okay because if we inserted before, that would be accounted in the state via dp[i][j-1] etc.
One more nuance: In the swap transition, we add te. However, there is also a possibility that swapping two characters and then deleting one of them could be better than something else. That's covered because after swap we could delete. DP will consider that because after the swap, we might then apply delete operation (by moving from state (i,j) to (i+1,j) if we delete extra? Actually swap consumes two characters and produces two; after that if we need to delete a character, we would do a delete operation as a separate step. That's captured by the DP because from state (i,j) we can go to (i+1,j) via delete. So the path with swap then delete is considered as a sequence of operations: first swap (which reduces i by 2, j by 2) then later delete from remaining. That's exactly the path we saw: dp[2][3] came from swap (using dp[0][1]), then later delete (from dp[2][3] to dp[3][3] via delete). So it's fine.
Now, confirm with second sample: we already did.
Now, potential bug: When using swap, we need to ensure that we do not double-count operations. The recurrence is sound.
Now, one more thing: Could there be a scenario where using a swap operation is beneficial even if the two characters are not exactly matching after swap because one of them could be later replaced, but the combined cost of swap+replace might be less than two replaces? We already argued that under the inequality, swap+replace is never better than both two replaces and delete+insert, but could it be better than a combination of insert and delete that involves only one of the characters? For example, suppose we have A="ab", B="ac". Replace b with c costs tr. Could swapping then replacing be cheaper? That would be swap (ab->ba) then replace a with c? That would give "bc", not "ac". Not working. For A="ab", B="ca"? Not.
But consider A="ab", B="bc" we already considered, and concluded not optimal under constraint.
Thus we are safe.
Now, final solution: implement DP as described.
But wait, there is another operation: "exchange (swap) two adjacent balls". It says you can exchange two adjacent balls. This operation directly swaps two balls in the current sequence. That's exactly transposition.
Now, are there any restrictions on using swap? Could we swap any two adjacent balls, even if they are not originally from A? After some inserts, we have a longer string, and we can swap adjacent balls that might be inserted ones. That's allowed. DP accounts for that because we can insert characters and then later swap them with neighbors. In DP, insertion adds a character from B; then later swap can involve that inserted character with an original character. This is captured because the swap transition doesn't care about whether the characters are from original A or inserted; it just aligns two characters from the transformed string. In terms of DP state, after we have inserted some characters, the alignment of prefixes might involve consuming characters from A and B in a certain order. The swap transition uses A[i] and A[i-1] from the original A (since we are matching prefixes of A to B). But what about swapping an inserted character with an original character? That would correspond to a sequence where we first insert a character, then later swap it with an adjacent original character. How is that represented in DP? Let's think: Suppose we have A: "a", B: "ba". We want to insert 'b' before 'a', then swap them to get "ba"? Actually starting with "a". Insert 'b' at front gives "ba". That's already target, no swap needed. But consider A: "a", B: "ab". Insert 'b' after 'a' gives "ab". No swap. Now consider A: "b", B: "ab". Insert 'a' at front gives "ab". No swap.
But consider a case where we need to swap an inserted character with an original character after some other edits. For example, A="ac", B="bca". Possibly you'd insert b, then swap with a? Let's see: start "ac". Insert 'b' at front: "bac". Then swap 'a' and 'c'? That gives "bca". That's insert then swap original characters? The swap is between original 'a' and 'c' (both original), not involving inserted 'b'. So it's captured by swap on A characters.
Now, could there be a scenario where swapping an inserted character with an original one is beneficial? For instance, A="a", B="ba". You could insert 'b' after 'a' to get "ab", then swap to get "ba". That is: insert 'b' (ti), then swap adjacent 'a' and 'b' (te). Total cost ti+te. Without swap, you could just insert 'b' before 'a' (ti) only, cost ti. So swap not beneficial. But if insertion before is not possible? Actually you can insert at any position, so you can insert at front directly. So not beneficial.
But suppose there is a case where you have to insert a character and also swap with an original because the target order requires that the inserted character is between two originals after a swap? For example, A="ac", B="bac". Could we: insert 'b' at front (ti) -> "bac". That's target. So no swap needed.
Maybe A="ca", B="ac". Swap original characters directly? te. Or delete+insert etc.
Thus, swapping inserted characters likely never needed if you can insert at correct position. However, there might be cases where you need to insert a character and then later swap it with another inserted character? That seems avoidable.
Nevertheless, DP as defined might not consider swaps involving inserted characters because the swap transition always consumes two characters from A. But what about sequences where we insert a character, then later swap it with an adjacent character from A? This would effectively mean that the inserted character appears in the final string, but its order relative to A's characters is changed after insertion. But can we simulate that with DP? Let's attempt to model: Starting with A="a", we want B="ba". Sequence: Insert 'b' after 'a' (cost ti) => "ab". Then swap 'a' and 'b' => "ba". Total ti+te. In DP terms, how would we represent transforming A[1..1]="a" to B[1..2]="ba"? According to DP, we compute dp[1][2]. Let's compute with costs: ti, td, tr, te whatever. dp[1][2] options: delete a? no; insert b? That would be from dp[1][1] insert b? Let's compute: dp[1][1] is cost to convert "a" to "b" (maybe replace or insert/delete). Then insert 'a'? Actually B[2] is 'a', so after converting "a" to "b", we need to insert 'a'? That would be "ba"? Actually dp[1][2] = min( dp[0][2] + td? no; dp[1][1] + ti (insert B[2]), dp[0][1] + (a==a?0) ... etc). Let's actually compute numeric example: ti=2, td=3, tr=5, te=4. Then dp[0][0]=0, dp[0][1]=2, dp[0][2]=4. dp[1][0]=3. dp[1][1] = min( dp[0][1]+3=2+3=5, dp[1][0]+2=3+2=5, dp[0][0]+5=5 ) =5. dp[1][2] = min( dp[0][2]+3=4+3=7, dp[1][1]+2=5+2=7, dp[0][1]+ (a==a?0)=2+0=2 ) =>2. So dp[1][2]=2, which corresponds to matching A[1] to B[2] (a==a) and inserting B[1] as extra (cost ti=2). That's the insert-at-front method (cost 2). The insert-then-swap method would cost ti (2) + te (4)=6, which is worse. So DP picks the better one. So not a problem.
But what if insert-at-front is not possible? It always is: you can insert at any position. So swapping an inserted character is never optimal because you could have inserted it in the correct position directly. Unless there are multiple characters and interactions? Possibly if you have to insert multiple characters and the order gets messed up due to other constraints? But you can always insert characters in the correct final order, because insert operation allows inserting any character at any position. So you never need to swap an inserted character with another; you can just insert them in the right order. Similarly, swapping an inserted character with an original can be avoided by inserting at the correct position relative to originals. So DP that only swaps original characters is sufficient.
Thus, the DP with swap only on A's characters (as in recurrence) is adequate.
One more nuance: Could there be a scenario where you swap two characters, one of which is the result of a previous replacement? That is, you replace a character, then later swap it with neighbor. This is like editing then swapping. In DP, this would be represented by performing a replace on a character (which is part of matching) and then later, when considering a larger prefix, performing a swap that involves that replaced character. The swap recurrence uses A[i] and A[i-1] original characters, not the replaced ones. So if we replace a character, its label changes. Then swapping it with neighbor would involve a character that is no longer the original A character. However, in DP we treat characters based on original A string; after a replace operation, we effectively change the character. The DP state dp[i][j] captures that we have transformed prefix A[1..i] into something that matches B[1..j], but we don't keep track of what the transformed string looks like except through the alignment. The swap recurrence relies on the condition that the two A characters, when swapped, exactly match two B characters. But if one of the A characters has been replaced, its label is different from the original A character. So the condition A[i]==B[j-1] would check the original character, not the replaced one. That could be a problem: if we replaced A[i] with something else, then later we might want to swap it. How does DP capture that?
Consider a case: A="ab", B="ba". We can replace 'a' with 'b' and 'b' with 'a' (two replaces) costing 2*tr. Or we could swap, costing te. But could we replace only one and then swap? That would be: replace 'a' with 'b' -> "bb", then swap? swapping identical does nothing, then replace the other? Not helpful.
But suppose we have A="ax", B="ya". Could we replace 'x' with 'y' then swap? Starting "ax". Replace 'x' with 'y' -> "ay". Then swap 'a' and 'y' -> "ya". That's replace then swap. Total cost = tr + te. Could that be cheaper than other options? Compare: directly replace 'a' with 'y' and 'x' with 'a'? Two replaces = 2tr. Or delete+insert? Possibly. With constraint, we need to check if tr+te could be less than min(2tr, ti+td). For this to be beneficial, we need te < tr (so tr+te < 2tr) and tr+te < ti+td. Under the inequality, is that possible? Let's try to find parameters that satisfy 2te >= ti+td and also te < tr and tr+te < ti+td. From te < tr and 2te >= ti+td, we get ti+td <= 2te < 2tr, so ti+td < 2tr. That doesn't directly conflict. But also we need tr+te < ti+td. Combine with ti+td <= 2te => tr+te < ti+td <= 2te => tr+te < 2*te => tr < te, which contradicts te < tr. So impossible. Thus, replace then swap cannot be better than both two replaces and delete+insert simultaneously. But could it be better than one of them while the other is worse? The DP will consider all sequences, but the swap recurrence does not capture replace-then-swap because the swap operation as modeled assumes the two characters are the original A characters, not replaced ones. However, the replace-then-swap sequence might be represented in DP as a swap after replace? Let's see if DP can capture it via other paths. In the replace-then-swap scenario, we first replace A[i] (or A[i-1]), changing its label, then swap the two (now modified) characters. Could that be represented as a swap first then replace? Possibly, because swap and replace commute? Not exactly. For "ax" -> "ya": Option 1: replace x with y, then swap a and y. Option 2: swap a and x first -> "xa", then replace x with y? Actually after swap we have "xa". Replace x with y -> "ya". That's swap then replace. So the same sequence but order reversed: swap then replace on one character. So the sequence "swap then replace" is captured by DP because the swap transition itself is a direct operation that consumes two characters and matches two B characters. If after swap we still need to replace one, that means the swap alone didn't match both; so we wouldn't use the direct swap transition; we would instead do a replace on one of them after the swap. In DP, that would be represented as: first, we do some operation to align prefixes? Let's try to see if DP can get cost tr+te for this example with swap then replace.
A="ax", B="ya". n=2,m=2. Suppose costs: ti=5, td=5, tr=10, te=4 (satisfy? 2te=8 >= ti+td=10? No, 8 < 10, violates condition. So need te >=5. So let ti=5, td=5, tr=10, te=5 (2te=10 >=10). Then tr+te=15, two replaces=20, delete+insert=10, so delete+insert is best. So replace then swap not best. To make it possibly best, we need te < tr and te relatively low, but must satisfy te >= (ti+td)/2. So set ti=2, td=2 => ti+td=4 => te>=2. So te=2 (min). tr=5. Then tr+te=7, two replaces=10, delete+insert=4. So delete+insert best (4). So replace+swap not best.
What about ti=10, td=10 => ti+td=20 => te>=10. Set te=10, tr=12 => tr+te=22, two replaces=24, delete+insert=20. So delete+insert best. So indeed, under constraint, replace+swap is never better than both alternatives. But could it be better than both in a scenario where delete+insert is not an option because of some interdependency? But delete+insert is always an option: you can delete a character and insert another anywhere. So it's always available. So replace+swap will never be optimal.
Thus, DP not capturing replace-then-swap is fine.
But what about swap then replace on one character? That's the same cost te+tr. So not optimal.
Thus, the DP recurrence is sufficient.
Now, we also need to consider that the swap operation may be used multiple times in a row. That's captured because DP can apply swap transitions multiple times at different steps.
Now, final step: implement solve() function.
Implementation details:
- Read input lines: first line four ints.
- Next line A (strip newline), next line B.
- Compute answer using function.
Now, test with sample inputs.
I'll write Python code.
Potential pitfalls:
- Using large numbers: we might need INF if prev2 not defined, but we guard with i>=2.
- Use list comprehension for initial row: prev1 = [j * ti for j in range(m+1)].
- In loop, for j from 1 to m, we compute.
But careful: cur[j-1] for insert cost is valid as we fill left to right.
Now, note: The costs are integers up to 100, and lengths up to 4000, so max cost could be up to 4000*100 = 400,000, safe in int.
Now, we should also consider that maybe we could use a swap as a combination of delete and insert? Not needed.
Now, produce final answer.
But wait, I recall that in some edit distance with swaps, you need to also consider the possibility of swapping two characters and then inserting/deleting in between, which could be represented by a more complex DP that tracks last characters. However, the classic Damerau–Levenshtein recurrence is known to be correct only when the cost of transposition is not too low relative to insert/delete. The condition 2*te >= ti+td is exactly the condition for the classic recurrence to yield optimal distance (I think it's to avoid the need for considering multiple swaps or swap+insert combos). So we are good.
Now, double-check with a tricky case where swap may be beneficial even if characters are not consecutive in the original A but can be made consecutive by deletions. In DP, this is represented by deleting the characters in between before applying swap. Let's test with an example:
A = "acb", B = "abc". We want to swap b and c? Actually A="acb", target "abc". One way: delete 'c'? That would give "ab", then insert 'c'? Not. Better: swap c and b (adjacent? In "acb", c and b are adjacent positions 2 and 3). So swap them: cost te -> "abc". So direct swap works. DP: n=3,m=3. Compute with costs say ti=2,td=3,tr=10,te=4. Should get te=4 maybe. Let's quickly test DP mental: condition A[3]==B[2]? A[3]='b', B[2]='b' true; A[2]==B[3]? A[2]='c', B[3]='c' true, so at i=3,j=3 swap cost = dp[1][1]+te. dp[1][1] for converting "a" to "a" =0. So dp[3][3] could be 4. Also other options maybe more. So DP works.
Now consider A="a x b" with x in between, B="b x a"? That's the earlier example. DP gave 9.
Now, consider A="a b c d", B="d b c a"? Something like moving a to end and d to front, with b,c in middle unchanged. Could do: delete a and insert at end, and delete d and insert at front: cost 2*(td+ti). Or could swap a with b, then swap a with c, then swap a with d? That would be three swaps moving a to end, and similarly moving d to front maybe by swaps in opposite direction? Actually to get from "abcd" to "dbca", we need to move d to front and a to end. Sequence: swap c and d -> "abdc", swap b and d -> "adbc", swap a and d -> "dabc"? That's three swaps; then need to swap b and c? Actually after three swaps we have "dabc", target "dbca" is different. It's messy. But likely delete+insert cheaper if 2te >= ti+td. Since moving a distance 3 costs 3te >= 1.5*(ti+td) which is > ti+td if ti+td >0, so delete+insert cheaper. So DP would choose delete+insert.
Thus, DP works.
Now, implementation details: We'll use sys.stdin.read().splitlines() to read.
Edge Cases: Strings may have trailing newline; we strip.
Now, about performance: Using Python lists and loops, we need to be careful about attribute lookups inside loops. We'll store local references: ti_local = ti; td_local = td; tr_local = tr; te_local = te; A_str = A; B_str = B; etc. Also store prev1, prev2 as lists. In inner loop, we might do many condition checks: A[i] == B[j] and for swap A[i] == B[j-1] and A[i-1] == B[j]. To avoid repeated indexing, we could precompute arrays of characters for A and B (as lists). But indexing string is O(1) and fine. However, to speed, we can convert to list of chars (or just keep as string with 0-indexed but with sentinel at index 0). We'll use list(' '+A) to have indexable list.
Alternatively, we can keep original strings and use A[i-1] (since i is 1-indexed) by doing A[i-1] if string is 0-indexed without sentinel? But we need A[i] for i from 1 to n, and also A[i-1] for swap. If we use 0-indexed strings (0..n-1), then for i in range(n): we need to map. It's easier to prepend a dummy.
We'll do: A = ' ' + A; B = ' ' + B.
Now, the DP rows: we will maintain prev1, prev2 as lists. Since we need to access prev2[j-2] only when i>=2, we need prev2 defined. At start, prev2 = None; when i==1, we don't use prev2. For i>=2, prev2 will be the row for i-2. After first iteration (i=1), we set prev2 = prev1 (row0) and prev1 = cur (row1). So for i=2, prev2 is row0, good.
Now, inside loop for j from 1..m, we compute swap condition. For i>=2, we need to check A[i] == B[j-1] and A[i-1] == B[j]. That's fine.
Potential micro-optimization: For each i, we can precompute the character A[i] and also A[i-1] if i>=2 to reduce indexing. But not necessary.
Now, we must also consider that te might be very high, but that's okay.
Now, finalize code.
I'll write:
import sys
def solve(): data = sys.stdin.read().split() if not data: return ti = int(data[0]); td = int(data[1]); tr = int(data[2]); te = int(data[3]) A = data[4].strip() if len(data) > 4 else '' B = data[5].strip() if len(data) > 5 else '' n = len(A); m = len(B) # add sentinel A = ' ' + A B = ' ' + B # dp[0][j] prev1 = [j * ti for j in range(m+1)] prev2 = None for i in range(1, n+1): cur = [0] * (m+1) cur[0] = i * td ai = A[i] # if i>=2, get aim1 = A[i-1] for swap condition aim1 = A[i-1] if i >= 2 else None for j in range(1, m+1): bj = B[j] # delete cost_del = prev1[j] + td # insert cost_ins = cur[j-1] + ti # replace/match if ai == bj: cost_rep = prev1[j-1] else: cost_rep = prev1[j-1] + tr best = cost_del if cost_ins < best: best = cost_ins if cost_rep < best: best = cost_rep # swap if i >= 2 and j >= 2: # need A[i] == B[j-1] and A[i-1] == B[j] if ai == B[j-1] and aim1 == bj: swap_cost = prev2[j-2] + te if swap_cost < best: best = swap_cost cur[j] = best prev2 = prev1 prev1 = cur print(prev1[m])
if name == "main": solve()
Now, test with provided examples.
Example1:
Input: 1 1 1 1 youshouldnot thoushaltnot
Our DP should output 5.
Let's manually trust.
Example2: 2 4 10 3 ab ba -> 3.
Example3: 1 10 20 30 a za -> 1.
All good.
Now, think about any possible overflow: Not.
Now, what about time: For n=m=4000, the inner loop runs 16 million times. Each iteration does a few integer ops and comparisons. That should be okay in PyPy (which is often used for Codeforces). I'll assume it's acceptable.
But there is a potential improvement: we can avoid re-checking i>=2 inside inner loop by moving swap check outside j loop? But we need j>=2 also, so we can start j from 2 for swap, but still need to check condition for each j. We'll keep as is.
Also, we can store B as list to access B[j-1] quickly. In swap condition we need B[j-1], which is just B[j-1] if B is a list. Since we have B as string with sentinel, indexing is fine.
Now, edge case: n or m = 1. Swap never applies. Works.
Now, confirm the condition 2*te >= ti+td is not used in code, but it's given to guarantee correctness of this DP. So we don't need to enforce it.
Now, finalize answer.
But wait, I recall a known problem: "Edit Distance with Swaps" sometimes requires a more complex DP using additional array to capture the scenario where you swap then delete etc., but with the given inequality, the simple DP works. Actually, I remember a problem from USACO named "levenshtein" or something? Not sure.
However, let's double-check with a more complex example from potential pitfalls. I'll write a small brute-force for small strings to test my DP against exhaustive search (for all possible sequences of operations? That's huge). But we can test for random strings and costs that satisfy the inequality and compare with a known algorithm (like using a more general graph shortest path on state space of string? Too heavy). But we can rely on reasoning.
One more nuance: In the swap recurrence, we used dp[i-2][j-2] + te. However, some formulations of Damerau–Levenshtein distance also include an additional possibility: dp[i-2][j-2] + (te) if the swap is used, but also sometimes they consider that if you do a swap and then a replace on one of the characters, it could be captured by doing a replace then swap? But we argued it's not optimal under constraint.
But wait, consider the possibility: A="ab", B="aa". Could we swap then replace? Swapping gives "ba", then replace 'b' with 'a' -> "aa". Cost te+tr. Alternative: replace 'b' with 'a' (tr) -> "aa". So cost tr. So not beneficial. Or delete+insert etc.
A="ab", B="bb": replace 'a' with 'b' (tr) -> "bb". So tr. Swap? swap gives "ba", then replace 'a' with 'b' -> "bb": te+tr > tr.
So no.
Thus fine.
Now, I'll produce final solution.
But there is another thing: The operation "replace any ball with any other ball" might also include replacing with same ball (which is a no-op), but cost is tr, which is >0, so we wouldn't do that. So our handling of match with 0 cost is correct.
Now, one more optimization: Use array module or use memoryview? Not needed.
Now, I'll finalize.
Before finishing, I should test with some random data mentally or via small script if possible, but can't run here. However, I'm confident.
Potential bug: In the swap condition, we used aim1 == bj and ai == B[j-1]. But we defined aim1 = A[i-1] if i>=2 else None. However, in the inner loop when i>=2, aim1 is defined. But we also need B[j-1]; that's fine. However, note that for j=1, j>=2 false, so swap not considered; we don't need B[0] which is sentinel space, but it's okay if we did, but we guard with j>=2.
Now, what about using sentinel: A = ' ' + A, B = ' ' + B. So A[0] and B[0] are spaces. When i>=2, A[i-1] is valid (since i-1>=1). So fine.
Now, final answer.
I'll produce the solution explanation and code. ```python import sys
def solve() -> None: data = sys.stdin.read().split() if not data: return ti = int(data[0]) td = int(data[1]) tr = int(data[2]) te = int(data[3]) A = data[4].strip() B = data[5].strip()
n, m = len(A), len(B) # 1‑indexing with a dummy character at position 0 A = ' ' + A B = ' ' + B # dp[0][*] prev1 = [j * ti for j in range(m + 1)] prev2 = None # will hold row i-2 when i >= 2 for i in range(1, n + 1): cur = [0] * (m + 1) cur[0] = i * td ai = A[i] aim1 = A[i - 1] if i >= 2 else None # for the swap condition for j in range(1, m + 1): bj = B[j] # delete A[i] cost_del = prev1[j] + td # insert B[j] cost_ins = cur[j - 1] + ti # replace (or match) cost_rep = prev1[j - 1] + (0 if ai == bj else tr) best = min(cost_del, cost_ins, cost_rep) # adjacent swap of A[i-1] and A[i] if i >= 2 and j >= 2: if ai == B[j - 1] and aim1 == bj: swap_cost = prev2[j - 2] + te if swap_cost < best: best = swap_cost cur[j] = best # shift rows prev2 = prev1 prev1 = cur print(prev1[m])if name == "main": solve()