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 to challenges at a later time, enjoy solving yourself for now. =)
Problem B. Number as a gift
Topics: greedy.
Since we aim to maximize the number, let us look what is the largest first digit we can possibly place. Let d denote the first digit of n.
- d > y
- d = y
- x < d < y
- d = x
- d < x
In case 1 we can place y, in case 3 we can place x, and in case 5 we are forced to make the number shorter by one digit (effectively, placing 0). Since the new number is already compared less than n, the rest can be maximized without restraint, that is, filling with y's.
If d = x or d = y we may have a chance to match the first digit. However, we cannot tell right away if the first digit can be actually extended to a complete number that does not exceed n, e.g. n = 20, x = 1, y = 2.
We may proceed over digits of n until we meet a digit d' other than x and y, or the end of the number. In the latter case, the answer is just n.
If d' > x, then the number can be extended to the end (refer to the initial rule for the first letter). If d' < x, the number can not be extended further and we have to roll back and make some of the eariler digits smaller.
Naturally, we can only decrease y to x, hence we find rightmost placed y, change it to x and maximize the rest of the number (since we placed smaller digit at an earlier point).
It follows that n starts with x and proceeds with a digit smaller than x. We can see that there is no satisfactory number of the same length, hence we should decrease the length.
Come on, this is easy to come up yourself (or find in the above spoilers). I mean, seriously?
One can see that this is an O(n) solution since we make at most one backward pass, and at most two forward passes.
You may want to check the following:
- Can your answer start with a zero?
- Can your answer be a zero?
- Do you handle n = 10100 000 correctly?
- Okay, I don't know. Try stresstesting!
How many (modulo 109 + 7) positive numbers are there that consist only of digits x and y and do not exceed n? Solve in O(n) time.
I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)
Problem C. Recursive Generator
Topics: hashing/string algorithms.
As a start, how can we prove why the Fibonacci sequence as described in the statement is not 1-recursive?
Then there must exist a function f(x1) such that f(ai) = ai + 1. But then we must have simultaneously f(1) = 1 and f(1) = 2, a contradiction!
Indeed, suppose that any occurence of a number x is followed by the same number y (or the end of the sequence). It means that the function defined by f(ai) = ai + 1 has no contradiction, and the sequence is 1-recursive.
We can see by now that k-recursiveness is all about non-contradicting continuations of k-tuples: if there are two consecutive k-tuples of elements followed by different numbers, then the sequence is not k-recursive. Otherwise, the function defined by f(ai - 1, ..., ai - k) = ai is consistent.
We could do that explicitly by writing out all k-tuples along with the subsequent elements, and check for conflicts. This takes O(n3) time when done explicitly,
time if we sort the tuples,
time if we hash the tuples using the rolling polynomial hashes.
