WW
SRM 833 · 2022-07-08 · by misof
Problem Statement
Given is a
You like strings of the form WW: that is, strings that can be cut in half in such a way that the second half is the same as the first half.
You may rearrange S by making a sequence of edits.
In each edit you can choose an arbitrary subset of positions and rearrange the letters at those positions as you will.
The cost of each edit is computed as the sum of individual costs for relocating the individual letters that moved.
For each letter that moved during an edit, the cost of that movement is its ASCII value multiplied by the distance it moved.
(For example, the simplest non-trivial edit is swapping two letters. The cost of a swap is [the sum of the ASCII values of the two letters being swapped] times [the distance between them].)
Return the minimum total cost of rearranging S into the form WW, or -1 if that isn't possible.
Notes
- ASCII values of uppercase letters start at 'A' = 65 and end at 'Z' = 90. Lowercase letters range from 'a' = 97 to 'z' = 122.
Constraints
- S will have between 1 and 300 characters.
- Each character of S will be an English letter ('a'-'z', 'A'-'Z').
"topcoder" Returns: -1
This obviously cannot be rearranged into the desired form.
"aaaaa" Returns: -1
Neither can this. Even though all letters are the same, this isn't a string of the form WW.
"topcodertopcoder" Returns: 0
This obviously already has the desired form, no swaps necessary.
"intestines" Returns: 447
One optimal solution is to do two consecutive edits: Swap characters 't' and 'i' at positions 5 and 6. (Cost = 116*1 + 105*1 = 221.) Swap characters 't' and 'n' now at positions 6 and 7. (Cost = 116*1 + 110*1 = 226.) This produces the string "intesintes", which is of the form WW.
"appeases" Returns: 667
One optimal solution eventually produces the string "apesapes".
"aAAa" Returns: 162
The characters 'a' and 'A' are two distinct characters. The input is not a string of the form WW yet.
Submissions are judged against all 86 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WW with a public method int rearrange(string S) · 86 test cases · 2 s / 256 MB per case