909A - Generate Login

The most straightforward solution is to generate all possible logins (by trying all non-empty prefixes of first and last names and combining them) and find the alphabetically earliest of them.

To get a faster solution, several observations are required. First, in the alphabetically earliest login the prefix of the last name is always one letter long; whatever login is generated using two or more letter of the last name, can be shortened further by removing extra letter to get an alphabetically earlier login.

Second, the prefix of the first name should not contain any letter greater than or equal to the first letter of the last name, other than the first letter.

Thus, a better solution is: iterate over letter of the first name, starting with the second one. Once a letter which is greater than or equal to the first letter of the last name is found, stop, and return all letter until this one plus the first letter of the last name. If such a letter is not found, return the whole first name plus the first letter of the last name.

909B - Segments

Consider a segment [i, i + 1] of length 1. Clearly, all segments that cover this segment must belong to different layers. To cover it, the left end of the segment must be at one of the points 0, 1, ..., i (i + 1 options), and the right end — at one of the points i + 1, i + 2, ..., N (N - i options). So the number of segments covering [i, i + 1] is equal to M_i = (i + 1)(N - i). The maximum of M_i over all i = 0, ..., N - 1 gives us a lower bound on the number of layers.

Because the problem doesn't require explicit construction, we can make a guess that this bound is exact. max M_i can be found in O(N); alternatively, it can be seen that the maximum is reached for (for a central segment for odd N or for one of two central segments for even N).

The answer is .

We can also prove this by an explicit construction. Sort all segments in non-decreasing order of their left ends and then in increasing order of their right ends. Try to find a place for each next segment greedily: if i is the left end of current segment, and segment [i, i + 1] is free in some layer, add the current segment to that layer; otherwise, start a new layer with the current segment.

and yes, this is our O(1) problem! :-)

909C - Python Indentation

This problem can be solved using dynamic programming.

Let's consider all possible programs which end with a certain statement at a certain indent. Dynamic programming state will be an array dp[i][j] which stores the number of such programs ending with statement i at indent j.

The starting state is a one-dimensional array for i = 0: there is exactly one program which consists of the first statement only, and its last statement has indent 0.

The recurrent formula can be figured out from the description of the statements. When we add command i + 1, its possible indents depend on the possible indents of command i and on the type of command i. If command i is a for loop, command i + 1 must have indent one greater than the indent of command i, so dp[i + 1][0] = 0 and dp[i + 1][j] = dp[i][j - 1] for j > 0. If command i is a simple statement, command i + 1 can belong to the body of any loop before it, and have any indent from 0 to the indent of command i. If we denote the indent of command i (simple statement) as k, the indent of command i + 1 as j, we need to sum over all cases where k ≥ j: .

The answer to the task is the total number of programs which end with the last command at any indent: .

The complexity of this solution is O(N²).

909D - Colorful Points

We can simulate the process described in the problem step by step, but this is too slow — a straightforward simulation (iterate over all points when deciding which ones to delete) has an O(N²) complexity and takes too long. A solution with better complexity is required.

Let's consider continuous groups of points of same color. Any points inside a group are safe during the operation; only points at the border of a group are deleted (except for the leftmost point of the leftmost group and the rightmost point of the rightmost group, if these groups have more than one point). So, if current group sizes are, from left to right, N₁, N₂, ..., N_G - 1, N_G, group sizes after performing the first operation are N₁ - 1, N₂ - 2, ..., N_G - 1 - 2, N_G - 1, after the second operation — N₁ - 2, N₂ - 4, ..., N_G - 1 - 4, N_G - 2 and so on. This process continues until at least one of the groups disappears completely, at which point its adjacent groups may get merged if they are of the same color.

This way, multiple operations can be simulated at once:

1. Find the number of operations that are required for at least one group to disappear.

2. Update group sizes after this number of operations.

3. Remove empty groups.

4. Merge adjacent groups of the same color.

One update done this way requires O(G) time. During such an update at least one point from each group is deleted, so at least O(G) points are removed. If N is the initial number of points, we can remove at most N points in total. Therefore, running time of the algorithm is O(N).

909E - Coprocessor

We want to minimize the number of communications between main processor and the coprocessor. Thus, we need to always act greedily: while there are tasks that can be executed on the main processor right away, execute them; then switch to the coprocessor and execute all tasks that can be executed there; then switch back to the main processor and so on. This can be done using breadth-first search. To run reasonably fast, this solution has to be implemented carefully: instead of searching for available tasks at each step, we want to maintain two queues of available tasks (for main processor and coprocessor) and add a task to a corresponding queue once all tasks it depends on has been executed.

Alternatively, we can define T_i as the lowest number of coprocessor calls required to execute i-th task, and derive a recurrent formula for T_i. If u is a task and v₁, ..., v_k are its dependencies, then clearly for each i T_u ≥ T_vi because u must be executed after v_i. Moreover, if v_i is executed on the main processor and u — on the coprocessor, then executing u will require an additional coprocessor call. Therefore, T_u = max_i(T_vi + s_i), where s_i = 1 if u is executed on the coprocessor and v_i — on the main processor; otherwise, s_i = 0. Now all T_i can be calculated by recursive traversal of the dependency graph (or traversing the tasks in topological order). The answer to the problem is max T_i.

909F - AND-permutations

Permutation p (p_i & i = 0)

If N is odd, the answer is NO. Indeed, any number in odd-numbered position i p_i must be even, otherwise the last bit of p_i&i is 1. For odd N there are less even numbers than odd-numbered positions, so at least one of the positions will hold an odd number, thus it's impossible to construct a required permutation.

If N is even, the required permutation exists. To build it, first observe that (2^k - i)&(2^k + i - 1) = 0. For example, for k = 5:

100000 = 2⁵

011111 = 2⁵ - 1

100001 = 2⁵ + 1

011110 = 2⁵ - 2

and so on.

We can use this fact to always match 2^k - i and 2^k + i - 1 with each other, that is, set p_2^k - i = 2^k + i - 1 and p_{2^k + i - 1} = 2^k - i.

The full procedure for constructing the required permutation is as follows. For a given even N, find the maximum power of two that is less than or equal to N 2^k. Match pairs of numbers 2^k - i and 2^k + i - 1 for each i = 1..N - 2^k + 1. If we are not done yet, numbers from 1 to 2^k - (N - 2^k + 1) - 1 = 2^k + 1 - N - 2 are still unmatched. Repeat the process for N' = 2^k + 1 - N - 2.

For example, for N = 18 on the first step we set 2^k = 16 and match numbers 15-16, 14-17 and 13-18. On the second step unmatched numbers are from 1 to 12, so we set 2^k = 8 and match numbers 7-8, 6-9, 5-10, 4-11 and 3-12. On the third and the last step the remaining unmatched numbers are 1 and 2, so we set 2^k = 2 and match numbers 1 and 2 with each other. After this no unmatched numbers are left, and we are done.

Permutation q (q_i & i ≠ 0)

We can do a simple case analysis for N = 1..7 manually, noticing that the answer is NO for N = 1..5, a possible answer for N = 6 is \textbf{3 6 2 5 1 4} as given in problem statement, and a possible answer for N = 7 is \textbf{7 3 6 5 1 2 4}.

If N is a power of two, then it is represented in binary as 10..0. We must have q_N ≠ N, therefore q_N < N, so the binary representation of q_N is shorter than that of N. It follows that q_N&N = 0, so the answer is NO in this case.

Finally, if N > 7 and N is not a power of two, the required permutation always exists, and can be built in the following way. Split all numbers from 1 to N into the following groups (k is the largest power of two which is still less than N):

1..7

8..15

16..31

\ldots

2^k - 1..2^k - 1

2^k..N

For the first group use the permutation that we found manually. For each of the remaining groups, use any permutation of numbers in this group (for example, a cyclic permutation). The numbers in each group have leading non-zero bit at the same position (which corresponds to the power of two at the beginning of the group), so it is guaranteed that q_i&i contains a non-zero bit at least in that position.