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

Refer to the link above for the discussion of the O(n²) DP algorithm to the LCS problem.

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 s_i and its destination counterpart in the second string t_j. Respective to s_i, we are only allowed to move characters from right part of s to the left.

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.

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. =)

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?

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

time if we sort the tuples and compare only the adjacent pairs,

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

Suppose that we choose to spend only i-th good, then we have to spend ε / d_i, with our perceived value being ε·c_i / d_i. Hence, it is optimal to choose the good that minimizes c_i / d_i.

Breaking x into small ε portions and applying the previous argument, we can see that we should gradually use goods by increasing of c_i / d_i until the vendor agrees to sell. Note that goods with equal c_i / d_i can be taken in any order.

A key idea is that it is unnecessary to know the values of c_i / d_i, 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 c_i / d_i comparison.

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 c_i / d_i to the highest.

The only constraint is that we can't choose Δ to be too large since we may over/underflow a_i. We know that the common value of a_i 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(c_i) ≤ 0.1, hence Δ ≤ 10^- 5 is pretty much fine.

Note that the value of will be 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!).

One solution would be to make slightly larger than x so that not to suffer from precision fluctuations (warning: this can break most of the present analysis, do at your own risk).

Note that most sort algorithms are resilient to this kind of problem (e.g., merge or insertion).

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

.

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

On one hand, the is clearly (sum of degrees of Red's vertices) — (sum of degrees of Blue's vertices).

On the other hand, a red edge (with both endpoints red) has +2 on it, as a blue edge has -2. A neutral edge has 0 on it. It follows that the same total is equal to 2(e_R - e_B).

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)