Problem A:

Note that the k-th element is copied to the end. Then the (k+1)-th element from the initial sequence is copied, then (k+2)-th, … , n-th, k-th, (k+1)-th, etc. So all the numbers on the blackboard will become equal if and only if all the numbers from the k-th to the n-th in the initial sequence were equal. It's now also obvious that the number of operations needed for it is equal to the index of the last number that is not equal to the n-th element of the initial sequence, because it's exactly the number of deletions needed to eliminate the elements that are not equal to the last one. If this number is greater than k, than answer is -1. Complexity — O(n).

Problem B:

Let’s store the order of the rows and columns of table. Thus, row[x] is the number of the row x in the initial table and column[x] is the number of column x in the initial table. Then, the value of an element in the row x and column y in the current table is equal to t[row[x], column[y]], where t — initial table. When we get the update request, we need to swap the x-th element and the y-th element in the corresponding array. Complexity — O(n * m + k).

Problem C:

Let's factorize the numerator and denominator. Now for each prime integer x we know the extent of x in the factorization of the numerator(a[x]) and the denominator(b[x]). For each prime number x we can calculate the extent of x in the factorization of the numerator and the denominator after reduction : newa[x]=a[x]-min(a[x], b[x]), newb[x]=b[x]-min(a[x],b[x]). We have the numerator and the denominator of the answer in factorized form. Now we have to bring them into the form which is required in the condition. One of the ways to do it is to note that the fraction from the statement satisfies the conditions. We can factorize it again and in the answer we will have the same fraction for which there will not be such a prime x so that the degree of x in answer would be greater than newa[x] or newb[x]. (This operation can be called reduction) The result will satisfy the condition and the fraction will be equal to the required number. If you try to build answer greedily (put factors in the answer till their product <= 10^7), the count of numbers in the answer (n_out or m_out) will be bigger than 10^5. Factorization by O(sqrt(max)) received TL. You should have found a faster way. For example you could have used linear sieve of Eratosthenes. Complexity — O(max + n * log(max)). log(max) is size of factorization.

Problem D:

First of all, note that in any case the best place which Vasya can take is the first place for he can earn maximum points. Now we must find the worst place which Vasya can take. We need to find maximal matching in bipartite graph, where the edge between vertice i from the first part and vertice j from the second part exists if a[i] + b[j] >= x. To solve this task, it is enough just to sort the vertices in both parts of the graph by their weights and use two pointers method. Suppose that we have sorted all the vertices by non-increasing points (a1 >= a2 >= ... >= an). Let's take two pointers — L = 1 in the first part and R = N in the second part. While a[L] + b[R] < x we must decrease R to find the first vertice such a[L] + b[R] >= x. When we found such R, we must add this edge to the answer, i.e. increase the answer, increase L by 1, decrease R by 1. It is easy to show why this algo is correct and it finds the optimal solution. I have discovered a truly marvelous proof of this, but the margins of this analysis are too narrow to for him. Complexity — O(N log N) for sorting and O(N) for two pointers.

Problem E:

1) Solution with complexity O(n*m*m), using the dynamic programming: State — d[n][m] — the number of allowed chains of length n that ends in symbol m. Transition — sort out all possible characters, and check if you can put the symbol k after symbol m.

2) Solution with complexity O(m*m*m*log n): Note that the transition in the first solution is always the same. So we can make the transition matrix A of size MxM. If j-th symbol can follow i-th then A[i][j]=1 else A[i][j]=0. Define a vector of size 1хМ b={1,1,…,1}. We can see that b * a^(n-1) = answer. Now we can use fast exponentiation for computing a^(n-1). We should consider the case with n=1 separately. The answer is the sum of numbers in the vector ans. Complexity — O(m^3) from matrix multiplication and O(log n) from fast exponentiation.