August 2010 Contest Problem Editorials

please explain the term lexicological in exit code clearly. and what is the output for the case 12 11 111 92.

thanx.

Re: StepNums, Nice problem and solution.

I tried diagonalizing the adjacency matrix to take advantage of faster exponentiation of diagonal matrix. But the diagonal entries(roots of P(x)), sqrt(3) did not exist in Z_mod. Anybody sees a way of converting to an equivalent diagonal matrix or is this approach doomed ?

@Subrahmanyam Velaga: What happens if you try and work in Z_p[sqrt(3)]? i.e. work with numbers of the form a + b sqrt(3), with a and b in Z_p, like in the intended solution.

nice problem :)

1st problem is not mine :p

A few comments:

1. Optimizing Production and Sales: All these people tied for first have optimal answers (or at least within the rounding error).

3. Obstacle Course: Prim's algorithm has complexity O(N^2).

4. Exit Code: O(10^(n/2) * log 10^(n/2)) = O(10^(n/2) * n).

@Michael Dorfling:  Makes sense. Now I see that the solution you mentioned is pretty similar to diagonalization working in Z_p[sqrt(3)]. The fact that n is even allows us to convert the uglier radicals (sqrt( 2 + sqrt(3) )) into manageable 2 + sqrt(3).

I searched for patterns initially and found that for small prime moduli, a small look back (I observed 4, not 5) determined the next number and the sequence also had a period. So, I suspected a form a1^n + a2^n + .. + a4^n. But, I abandoned it since each ai has a period of P-1 and the whole expression should have a period P-1 which was not the case. I did not realize that it could be (a1,b1)^n.

I don't uderstand what are nCycle and c1,..,cb in task Swarm of Polygons. Suppose our cycle has length l, it consists of xi,..,x[i+l-1] points on each side and there are n cycles, can somebody please express formula for R2 using these symbols?

To avoid confusion let's say there are c cycles. So (n-|tail|-|head|)/l = c

Genetics:

Naive implementation of Cartesian trees should get TLE on worst test cases (because when we cross the same DNA many times - tree will contain many nodes with equal priorities ("y" keys), and may become imbalanced, height==5000 in worst case).

There are some randomisations in merge procedure, which reduce tree height. But unfortunately they weren't required to get AC. I wish there were challenge system on codechef.

Examples of worst case:

actually input: https://docs.google.com/leaf?id=0Bxx7QSPZZj2gYWRhZWM5NjUtZDM3Yi00ODE3LTlmYTctZmJhMzNmZTIwMjJm&hl=ru

test generator: http://codepad.org/4FooJo83

@Subrahmanyam Velaga: Yes, it's much the same thing, but I prefer your approach. It shows directly that there is a formula that involves exponentiating the eigenvalues only. That the formula mod p can be calculated exactly using integer arithmetic still has to be checked, but of course it turns out that it can. Another advantage of your approach is that it can work even if the answer is not a linear combination of entries of a power of  A.

It's interesting that you mention the period: I went to some trouble to find a p such that the sequence has period greater than p. Such p's are surprisingly rare. You can show that 2+sqrt(3) has order p-1 or p+1 in Z_p[sqrt(3)], but for most primes p (near 2^32 anyway) it is p-1. 4294967143 is the largest prime below 2^32 for which the order is p+1.

why no editorials for July 10 Contest??????

The July editorial was done ages ago.. http://www.codechef.com/wiki/editorials-codechef-contest-problems

Regarding the periods, you answered my next question :)

During the contest, I initially mistook MOD for 2^32 - 1 and factored it and obtained 3, 5, 17, 257, 65537 as factors; (2^(2^t) + 1) , t = 0, 1, 2, 3, 4 (which is an identity, after i thought about it :) ).

And for t=0,1,2,3 the periods for s_n were 6, 12, 144, 33024 which are all (p-1)*(p+1)/2 (except for p=3), meaning that 2 + sqrt(3) has period p+1 in Z_p[sqrt(3)] for these primes. I noted O(p^2) growth and abandoned this approach as t=5 would have period of ~2^32.

So, it seems I inadvertently ran into the moduli with 2+sqrt(3) having a period p+1 and I did not bother working out the period for 2^16 + 1.

Since you mentioned that primes where 2 + sqrt(3) has period p+1 in Z_p[sqrt(3)] are rare, i suppose it does raise an interesting question: P = If 2^(2^t) + 1 is a prime ( are there only finite of these ? I don't know.. ) then does 2+sqrt(3) have an order P+1?

@Przemyslaw Derengowski :  Here is a small example which might clarify things.

Consider a few partitions of b = 7:

Partition (k1, k2,..., ks) (c1, c2,..., cb)

1+2+2+2             (1,2,2,2)             (1,3,0,0,0,0,0)

2+2+3                 (2,2,3)                (0,2,1,0,0,0,0)

1+3+3                 (1,3,3)                (1,0,2,0,0,0,0)

1+2+4                 (1,2,4)                (1,1,0,1,0,0,0)

1+6                     (1,6)                   (1,0,0,0,0,0,1)

7                         (7)                     (0,0,0,0,0,0,1)

@Przemyslaw Derengowski : nCycle = c in your notation.

@Subrahmanyam: Very interesting. Numbers of the form 2^(2^t)+1 are Fermat numbers. The only known values of t for which they are prime are precisely t=0,1,2,3,4 and it is believed there are no more. That the order of 2+sqrt(3) is p+1 if p=2^(2^t)+1 is prime follows from Pepin's test.

@Michael Dorfling: It does indeed follow from Pepin's test. I had no idea about this test or the Fermat's numbers. Thank you for pointing those out :)

Summarizing (Let A be the adjacency matrix of a undirected graph)

To obtain a closed form for a function F(A^n) where F(B) is a linear function of its entries Bij, look at linear combinations of the nth powers of eigen-values.

To "compute" a function F(A^n), where F(B) is a (not necessarily linear function) of its entries Bij, diagonalize A: A = X * D * inv(X), with D diagonal and output F( X* D^n * inv(X) ). The difficulty arises in keeping the computations modulo P. With some luck, the entries of D and X (and thus inv(X)) might be members of a different (finite) field and computations could be done in that system and casted back to P.

Would you know if there are infinite analogues ? Infinite graphs with locally specified adjacency matrices and count replaced with probability/expectation. I am thinking random walks.

@Subrahmanyam Velaga: Thx for help :)

I think you can always do computations in some other system, namely R=Z_p[x1, . . , xn] where the xi's are the eigenvalues. It would be nice to have a proof though. As for infinite analogues, I have no idea.

@Michael Dorfling - I found Stepping Numbers to be one of the nicest problems I've solved in a long time :)

@Michael Dorfling: I am not sure if detecting a system is easy, even if such a system does exist. Given that Z_3[sqrt(3)] is not a field (no multiplicative inverse for (0,x), (2,1) has order 6 etc.), how would computation proceed if MOD were 3 ?

@Stephen Merriman: Glad you liked it :)

@Subrahmanyam Velaga: I think I've got it. First let's forget about MOD, and just show that there is a formula for F(A^n) involving only rationals and eigenvalues, assuming A is rational and symmetric. The smallest subfield of C containing Q and all the eigenvalues of A is a finite extension of Q, so it equals Q(a) for some a. Every element of Q(a) has the form b_0+b_1*a+b_2*a^2+ . . + b_{n-1}a^{n-1}, where all b_i's are rational. In particular, the eigenvalues have that form.

Since A is real and symmetric it is diagonalisable. Consider the standard diagonalising procedure: You compute an eigenvector corresponding to each eigenvalue and let X be the matrix with columns consisting of these eigenvectors. Then X D inv(X)=A. The eigenvectors are obtained by solving the linear systems (A-lambda*I)u=0, which shows that all entries of X are in Q(a). Now each entry of X A^n inv(X) is a linear combination of n-th powers of the eigenvalues, with all coefficients in Q(a), so we have a formula for F(A^n) that can be computed in Q(a). (We actually need some assumptions on F.)

Each element of Q(a) can be written as (c_0+c_1*a+c_2*a^2+ . . + c_{n-1}a^{n-1})/q where q and all c_i's are in Z. It follows that F(A^n)=p^n/((q^n)*r)*(d_0*l_0^n+d_1*l_1^n+ . . + d_{n-1}*l_{n-1}^n) where p, q, r are in Z and all d_i's and l_i's are in Z[a]. The only problem with computing this modulo some M is if q or r is not relatively prime to M. Can you find a way to deal with that?

@Michael Dorfling:  I have read through what you've written and I am still thinking about it. Its been a fair few years (5+) since I last studied a bit of field theory, so I shall claim ignorance straight up :)

There seems to be a bit of a mix up in using 'n' (the exponent) and 'm' the size of the matrix. So, the dimension of the number field Q(a) is probably 'm' and not 'n' the exponent. I tried to clear up at http://docs.latexlab.org/docs?#1MY7mvVHH4E5Hb7hfE3RtQvXQub8AOQ-NjpYvnFUNT3k . Its a latex doc I've made based on what you wrote above and you can edit it. Its more convenient to eyeball the equations.

The last paragraph, I am still trying to make sense.

@Michael Dorflin: For now, we could restrict F(B) to be a polynomial in Bij. We could probably use more field extensions to handle different types of F, but polynomial Fs should let us work with Q(a).

Sorry about using n for two different things.

I'm getting an invalid document id when trying to access that doc of yours. Being able to use latex will be awesome.

Seems like latexlabs still doesn't have real collaboration, I thought they did from their headlines.

http://www.scribtex.com/ is a pretty neat collaborative latex editor as well as provides online compilation into pdf, so if you have a simple browser pdf plugin, you are set to go.

If you are willing to sign up (it is free), let me know your username and I can add you to the list of collaborators for the document.

Ok, signed up with username michaeld.

I've shared a project with you. My id is vlsubra. I am guessing you will be notified.

It follows that F(A^n)=p^n/((q^n)*r)*(d_0*l_0^n+d_1*l_1^n+ . . + d_{m-1}*l_{m-1}^n) where p, q, r are in Z and all d_i's and l_i's are in Z[a].

Sorry if this is trivial, I still don't get it; there seem to be many undetermined quantities.

A few things as I understand:

1) q is fixed (as the lcm of all denominators of all coefficients of all the eigen values in Q(a) )

2) a is "unknown". We want to "eliminate" it and alleviate determining a candidate 'a'. Is it true that if A has characteristic polynomial C, then C(a) = 0? (i.e. is it correct to treat the extension as quotient ring Q[x]/C ?)

I don't get how the expression you gave is sufficient in itself.

if C = (x^2-2)*(x^2-3), can you outline the steps of the computation ?

Ok, you were showing "existence" of a field in which computations can be done "exactly" i.e. with essentially integer arithmetic.  (for MODs which satisfy some conditions, like rel prime to q)

I was thinking that you were suggesting a constructive algorithm. As of what I understand now, one would still need to identify some 'a' so as to be able to define the operations on the field elements. (like (a,b) *(c,d) = (ac+3bd, ad+bc) in the a + b*sqrt(3) case) I still can't see a way of automatically identifying appropriate 'a' (factorization isn't easy, is it?).

Sorry. I was still thinking of linear combinations. F(A^n) would involve products of l_i's, and q would be a power of the lcm of denominators of eigenvalues. There is also still some confusion about m. Let d be the degree of Q(a). Then every element of Q(a) has the form b_0+b_1*a+ . . +b_{d-1}*a^{d-1}. It is not true that C(a)=0, but p(a)=0 where p is the minimal polynomial for a.

This approach isn't necessarily faster than computing A^n directly. The idea is that it can be considerably faster. When d is small, for instance, or if exponentiating eigenvalues simplifies in some other way.

I was only showing existence, yes. It's a general approach, not an algorithm. You may not have to explicitly find an a. All you really need is a polynomial p (of degree less than m) such that Q(a) contains all eigenvalues of A for some root a of p, which then defines multiplication via p(a)=0. I don't know if finding such a polynomial is any easier than finding a. It should be, since there need not even be a radical expression for a.

d = number of non rational roots of C, correct? I was imagining extending the field one root at a time (actually two since they occur in conjugates), and you need to increase the dimension as many times as the non rational roots.  So, d < m in any case.

Yes, seems like the time savings may not be significant. Assuming we can find a 'p' via which we define multiplication, a straightforward multiplication would be O(d^2). So, with this method it would  be O(m * d^2 * ln(n) ) versus O( m^3 * ln(n) ) for the straightforward multiplication.

So, while we are reducing the number of multiplications, we are paying more per multiplication.

However, this is a legitimate and potentially good approach as you pointed out, when either 'd' is very small or if the multiplication (or exponentiation) turns out to be simple enough. (for example, MOD = 2 i.e. we want the parity)

d would be at most the number of non-rational roots of C, I think. It can be much less, like when C=(x^2-2)(x^2-3) . . (x^2-k).

I don't know if it helps any, but the eigenvalues are algebraic integers, and we can also take a to be an algebraic integer. The integers of Q(a) form a free abelian group of rank d. Maybe you can use that to speed up computation.

Can some body throw some more light on ECODE.

Thanks in advance!!

@Gunjan Sharma: this technique is called meet in the middle. Instead of investigating all possible 10^n sequences we build all prefix sequences   a1a2...an/2  and suffix  an/2+1an/2+1...an  . Now we should glue it somehow. Binary search fits our needs because if the prefix sequence has remainder r1 and we know that r1+r2 = G, then the suffix sequence has to have remainder r2 = G-r1. We can find whether it has this remainder via binary search in sorted array.

Thanks Max

Now thats makes more sense to me!!!! :)