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.

For problem D:

Observation: we can try change matching to include

anyelement (Proof: if elementaisn't in optimal matching, but exist elementb, thata + b >= x, we can add pair (_a_,b) to matching (possibly instead of previous pair withb)).So we can simply check for all elements from

Aif there exist large enough element inB(and erase it fromB). We should take smallest possible element fromBof course.My solution as examlple: http://codeforces.com/contest/222/submission/2115578

Author makes us smile with: "I have discovered a truly marvelous proof of this, but the margins of this analysis are too narrow to for him".

For the people who don't know about this line, it is related to Fermat's Last Theorem.

I can't understand how the first solution for Problem E can work. since n can be 10^15 and O(n * m * m) will surely get TLE for this n. wont it?

Dynamic approach was just a sample as a naive solution. So it sure gets TLE. See the matrix binpow solution.

Actually considering the case n=1 as a separate case is not necessary as we can start the multiplication from the identity matrix. In that way we can call a function solving the problem without any restrictions as n=1 and thus there is no need to consider the case separately.

for problem E, can anyone explain me the logic of why we can represent the problem as matrix exponentiation?

Suppose we have computed the number of valid sequences of length

nfor any pair of beginning and trailing characters. We store this inold[i][j]. Now we want to compute the same result,new[i][j], for lengthn+ 1. You can see thatwhere

f(k,j) = 0 if the pair is forbidden andf(k,j) = 1 if it is not. Now, this is precisely the definition of multiplication of the matrixoldby the matrix formed byf. It remains only to find a starting matrix that describes then= 1 case, and repeatedly multiply it byf.Thank you very much for this nice explanation.

isn't problem "B. Cosmic Tables" incorrectly worded?

the description says that n is the number of columns, and m the number of rows.

yet the tests don't work that way as test 4:

there is 1 column with 2 rows. yet the first statement is to swap column 1 with column 2.

how is that possible?

No, there are 2 columns and one row. Pay attention that the first number is a number of rows and the second — number of columns. So I guess there are no mistakes here