August 2010 Contest Problem Editorials |
1) Optimizing Production and Sales (written by Zachary Friggstad)
The problem is, perhaps, one of the most well-studied NP-hard optimization problems. It is more commonly known as the metric "Facility Location" problem where the word metric is used to indicate the supply costs satisfy the triangle inequality. If the supply costs are not metric, then one can show that no polynomial-time algorithm can approximate the minimum cost within a factor o(log n) unless P = NP.
If one has the metric property, as was guaranteed in this month's problem, then the optimum solution can be approximated within a constant factor. The first such algorithm was based on rounding the variables in a linear programming-based formulation of the problem and guaranteed the resulting solution cost no more than 3.16 times the optimum [1]. The first constant-factor approximation algorithm that did not rely on linear programming was a very simple "local search" algorithm. Given a solution, a "local step" is to try and close an open factory, open a closed factory, or swap an open factory with a closed factory. Once one of these is tried, reassign the stores to their nearest factory. If there is such a step that improves the cost, then take it. Otherwise, output the current solution. This very practical heuristic is known to produce a solution whose cost is, in the worst case, no more than 3 times the optimum cost. This has been analyzed in a few papers, but the simplest is in [2].
An alternative algorithm that produces a solution whose cost is within 3 times the optimum is found in [3]. The advantage here is that the algorithm is still easy to implement and has running time only O(m log m) where m = S*F. Modifications to this algorithm yield an algorithm that guarantees a solution of cost no more than 1.52 times the minimum cost, but the running time increases to O(n^3) where n = S+F [4]. There are many other heuristics I haven't mentioned (the best is actually a 1.5-approximation); the point is that the problem is well studied and there are many easy to implement heuristics that run fast in practice and guarantee good solutions.
Many of the results cited here are also analyzed to be tight in that instances are given to show the heuristic performs almost as bad as the worst-case guarantee. The test data for this problem included many such bad examples. Also, for the interested, even metric facility location cannot be approximated better than roughly 1.463 unless every problem in NP can be solved with an algorithm whose running time is n^O(loglog n) [5]. This statement is stronger than P != NP, but is still an open question.
[1] J-H. Lin and J. Vitter, Approximation Algorithms for Geometric Median Problems.
[2] A. Gupta and K. Tangwongsan, Simpler Analysis of Local Search Algorithms for Facility Location
[3] K. Jain and V.V. Vazirani, Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation
[4] K. Jain, M. Mahdian, E. Markakis, A. Saberi and V.V. Vazirani, Approximation Algorithms for Facility Location via Dual Fitting with Factor-Revealing LP
[5] S. Guha and S. Khuller, Greedy Strikes Back: Improved Facility Location Algorithms
2) Genetics (written by Ivan Mistreanu)
The solution is based on using some data structure which allows to perform all the operations in the problem in O(logn) time. One of those can be Cartesian trees (or treaps). We will use treaps with implicit keys.
Treap with implicit keys are good for this problem. Let’s describe how we can use them to implement all operations needed in the task. We will keep the following information in each node: the base, the sum of each of the bases in the subtrees of this node. The main operations on the Cartesian trees are split and merge. Using those operations we can implement all other such as inserting elements in the tree, deleting elements, updating elements. Also many other rather powerful operations can be perfomed with good complexity. The treap with implicit keys actually resembles an array. The keys being the order of the element in the treap. So such treaps can easily be split and then merged again.
First we need O(nlogn) time to construct a treap (There are also O(n) algorithms, but O(nlogn) is ok as well) for each initial DNA. We will use implicit keys and random priorities. With this the expected depth of each DNA will be logarithmic. Then we can each of the operations in logarithmic expected time in the following way.
• Cross operation: we call D1 = split(DNA1, k1) and D2 = split(DNA2, k2)and then merge(D1[1], D2[2]) and merge(D2[1], D1[2]). Both split and merge operations can be implemented with O(depth) complexity which is O(logn) in our case. Also important thing is that we need to implement persistent treaps, because we need to store all previous DNAs as well. But each cross operation will produce two new DNAs of about the same length. So when we have 10000 DNAs of length less than 2000000000 we can easily run out of memory. However while performing split and merge operation we create about O(depth) new nodes. So the increase in memory is onlu logarithmic.
• Mutate operation: this can easily be performed by deleting the element and then inserting a new one in the same position or just implementing update operation carefully. Once again this can be done in O(depth) time. No new DNA should be produced.
• Count operation: we call D1 = split(DNA, k1), then D2 = split(D1[2], k2-k1+1). Now we have the needed part of the DNA in D2[1]. So we just take the sum of each of the bases from the root of this treap. Once again the complexity is O(depth).
So the whole problem can be solved in O(nlogn + qlnMAXL) time, where MAXL is the maximum length of the DNAs. It must be noted the length of the DNAs can grow exponentially after cross operations so this can be an issue. But treap can give us O(lnMAXL) expected depth so the mentioned above expression can be used and this is good enough.
Cartesian tree is very powerful data structure. I suggest you read more about it in the literature and on the internet.
3) Obstacle Course (written by David Stolp)
Consider the cones and circles as vertices of a graph, where the edge between any 2 vertices has length equal to the distance between the corresponding elements of the obstacle course. Note that the longest edge in the graph is the one that connects the edges corresponding to the 2 circles. Our goal is to partition the vertices of the graph into 2 sets representing the "inside" and "outside" of the car's path, so that the distance between any two vertices from different sets is at least the diameter of the car. We do this by constructing the minimum spanning tree (MST) of the graph, then removing the longest edge on the path from the outer edge of the track to the inner edge. Because the spanning tree is minimal, no two verticies from different sets can have an edge longer than the removed edge. Because there exists a path from the outer circle to the inner circle consisting only of edges not exceeding the length of the removed edge, there cannot be a partition which is separated by a longer distance. Therefore the length of the removed edge is the maximal diameter.
The MST can be easily computed in O(N2) time using Prim's algorithm, though a O(N2log N) algorithm such as Kruskal's will suffice. Both Prim's and Kruskal's can be modified to compute the length of the edge in question without actually computing the MST itself. Because the graph is mostly Euclidean, a more complicated O(N log N) solution also exists.
4) Exit Code (written by AnhDQ)
5) Swarm of Polygons (written by Ivan Mistreanu)
6) Stepping Numbers (written by Michael Dorfing)
Comments
please explain the term
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
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
@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 :)
nice problem :)
1st problem is not mine :p
1st problem is not mine :p
A few comments: 1. Optimizing
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
@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
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
To avoid confusion let's say there are c cycles. So (n-|tail|-|head|)/l = c
Genetics: Naive
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,
@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
why no editorials for July 10 Contest??????
The July editorial was done
The July editorial was done ages ago.. http://www.codechef.com/wiki/editorials-codechef-contest-problems
Regarding the periods, you
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 :
@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 :
@Przemyslaw Derengowski : nCycle = c in your notation.
@Subrahmanyam: Very
@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
@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
@Subrahmanyam Velaga: Thx for help :)
I think you can always do
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
@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
@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
@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
@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,
@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
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
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
Ok, signed up with username michaeld.
I've shared a project with
I've shared a project with you. My id is vlsubra. I am guessing you will be notified.
It follows that
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
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
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
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
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
Can some body throw some more light on ECODE.
Thanks in advance!!
@Gunjan Sharma: this
@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
Thanks Max
Now thats makes more sense to me!!!! :)