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 and compare only the adjacent pairs,
time if we hash the tuples beforehand using the rolling polynomial hashes.
The rest of the solution is binary search on k, with the resulting complexity 
, or 
.
Solve the problem:
- in with simple string algorithms (no hashes!)
- in O(n2) with simple string algorithms (no hashes!)
- in with harder string algorithms (no hashes either!)
Problem D. Trading
Topics: greedy, sorting, implementation.
Suppose that we're willing to spend some amount of goods so that vendor's perceived price is a small ε.
Suppose that we choose to spend only i-th good, then we have to spend ε / di, with our perceived value being ε·ci / di. Hence, it is optimal to choose the good that minimizes ci / di.
Breaking x into small ε portions and applying the previous argument, we can see that we should gradually use goods by increasing of ci / di until the vendor agrees to sell. Note that goods with equal ci / di can be taken in any order.
According to the considerations above, it is beneficial to know the order of goods sorted by ci / di.
A key idea is that it is unnecessary to know the values of ci / di, but only be able to compare them.
Our query capacity is very limited: a simple YES/NO answer, that we have to apply to precisely comparing numbers. A correct way to do this would be to obtain a configuration with 
with high precision, and then make alterations to it so that the balance is decided on ci / di comparison.
Simply make all ai equal and binary search on their common value. About 40-50 iterations should result in a practically precise double value (more on precision issues below).
Let us choose a small, but positive Δ. To compare fractions for i-th and j-th goods, alter the balanced configuration by performing ai - = Δ·cj, aj + = Δ·ci. The value of 
will be changed by the value of Δ (cidj - cjdi), which has the same sign as ci / di - cj / dj. Note that comparison takes only one query (except for the equal fractions case which may be undecided as of now, more on that later).
Since we now know the order, we can binary search on the total volume of goods we're paying. Greedy considerations above tell us to distribute them greedily from the lowest ci / di to the highest.
The resulting solution makes roughly 
queries, in practice this number is about 450 on the present constraints.
This pretty much concludes the idea description.
The only constraint is that we can't choose Δ to be too large since we may over/underflow ai. We know that the common value of ai in the balanced configuration will be at least 0.1 away from the borders. To keep the alteration within this distance we have to satisfy Δ max(ci) ≤ 0.1, hence Δ ≤ 10 - 5 is pretty much fine.
Note that the value of will be Δ |cidj - cjdi| ≥ Δ away from x provided we are comparing distinct fractions, hence we are free from precision problems at this point.
This is a bad spot to be. One possible situation when this issue arises when you're using std::sort to sort the fractions with the custom comparator that makes the queries itself. std::sort likes to make additional comparisons to check certain properties of your comparator, such as transitivity. Not only that provides an overhead on the query number, but can also lead to RE if your comparator does not behave well on comparing equal objects: it must always return false on equals.
The reason why our comparison is bad for this prupose is that the value of changes ever so slightly when add practically zero number to it, so that it can dance around x and returns random values on comparisons (note that there is no tolerance in ? query!).
