izban's blog

By izban, 12 years ago, translation, In English

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.

  • Vote: I like it
  • +52
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D:

Observation: we can try change matching to include any element (Proof: if element a isn't in optimal matching, but exist element b, that a + b >= x, we can add pair (_a_, b) to matching (possibly instead of previous pair with b)).

So we can simply check for all elements from A if there exist large enough element in B (and erase it from B). We should take smallest possible element from B of course.

My solution as examlple: http://codeforces.com/contest/222/submission/2115578

»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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?

»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose we have computed the number of valid sequences of length n for any pair of beginning and trailing characters. We store this in old[i][j]. Now we want to compute the same result, new[i][j], for length n + 1. You can see that

    where f(k, j) = 0 if the pair is forbidden and f(k, j) = 1 if it is not. Now, this is precisely the definition of multiplication of the matrix old by the matrix formed by f. It remains only to find a starting matrix that describes the n = 1 case, and repeatedly multiply it by f.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much for this nice explanation.

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

1 2 3
1 2
c 1 2
g 1 1
g 1 2

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

how is that possible?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I failed at test case 42 .

How to solve C??

my solution gives more than 10^5 number.

I used factorization method of every number.

May be It is the wrong process>

but I don't understand the editorial.

plz somebody help me .

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How come my solution is showing TLE in qestion B? My logic is same as that in the tutorial. My solution --> https://codeforces.com/contest/222/submission/74291671

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Proof of problem D anyone?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B: my code is https://codeforces.com/contest/222/submission/86359093 can anyone suggest how to overcome TLE??

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems impossible, the servers have changed since the problem was written.