Problem A. Shifts
Topics: dynamic programming.
Suppose that we are allowed to make left circular shifts as well as right ones.
First of all, making a shift is effectively moving a character to a different position in the string. Clearly, moving a character more than once makes no sense since we could have just moved it to its final destination instead without wasting any operations. Also, it obvious that the number of occurences of each character should be the same in both strings since it is preserved by shifts.
Now, consider the characters that are not moved by any operation made, and match them with their final destinations in the second string.
Both sets have to respect their relative order since we are not allowed to move them around. Hence, they have to form a common subsequence of the two strings. Note that if the solution made k operations, the common subsequence will have length n - k.
Moreover, we can make any common subsequence of size k into a solution that makes exactly n - k operations: just move all non-stationary characters to their destinations.
We can see that the minimal number of operations is exactly n - k, where k is the size of the longest common subsequence
... think about how the answer could be larger or smaller than this quantity, and try to reach a contradiction with the help of the previous spoilers.
Refer to the link above for the discussion of the O(n2) DP algorithm to the LCS problem.
Ok, nevermind.
Clearly, the number of occurences of each character must still agree in both strings. Further, it still makes no sense to move the same character twice. Further, the stationary characters still have to form a common subsequence. However, the second sample case shows us that the answer can be greater than n - LCS(s, t).
Consider a stationary character si and its destination counterpart in the second string tj. Respective to si, we are only allowed to move characters from right part of s to the left.
Consider a symbol x. Count its occurences to the right of si and tj, denote the counts A and B. The above reasoning must imply A ≥ B. For si and tj to be possibly matched, this condition must hold for all symbols.
A reasonable line of action is to implement the DP solution for LCS while requiring the conditions above. But are the conditions strong enough to allow only valid solutions (that is, stationary sets of characters that can be extended to a sequence of operations)?
It may not be easy to prove or disprove right away. This is a totally OK situation, even for experienced participants.
If you have a plausible guess that you can't prove but have to confirm, a good idea is to stress test it: implement a brute-force solution that is sure to be right, and check if it agrees with your hypothesis on many random cases. If it does, you are very confident that the guess is right, and if it doesn't, you have a counter-example and can investigate further.
Happily, yes!
We have to prove that a satisfactory common subsequence of length k gives rise to an operation sequence of length n - k, or, equivalently, that all non-stationary characters can be moved to correct positions. If there are no stationary characters, then everyone can be rearranged in any order with one operation per character, hence we are done.
Consider the rightmost stationary pair si and tj, and the character collections A and B that lie to the right of si and tj. We must have that 
in the sense that no character occurs more times in B than in A. We can easily obtain B in the final configuration by choosing an equal sub(multi)set in A and arranging them in the required order while staying to the right of si.
What should we do with all the rest elements A' = A\ B? We must spend one operation per element of A' to move them to the right of si into their final positions. However, we may as well postpone the decision and "merge" A' with the next group of characters to the left of si. We then continue with the new rightmost group, and so on until there are no stationary characters left.
Can you solve the problem much faster than O(n2), or provide hard evidence that a faster solution does not exist?
The problem is closely related to the LCS problem. What does the world know about the complexity of LCS? If we were to show that this problem is at least as hard as LCS, how would we do that?
I will post the solutions at a later time, enjoy solving yourself for now. =)
