Day2–Problem TimeIsMoney. You have a graph with two costs (A and B) on each edge. Find a spanning tree that minimizes (its total A-cost) * (its total B-cost) [that's "times" in the middle]. Desired running time: polynomial. Sharper bounds are possible (I think I get O(n2m log)) but this is hard enough. To be entirely fair, the contestants just need to find an algorithm, not to prove it runs in poly-time, which may be easier (but I'm writing for a theory audience so consider yourself challenged).
Day2–Problem Trapezoid. Consider two horizontal lines, and n trapezoids stretching from one line to the other. The proverbial picture worth 1000 words:
Find the maximal set of nonintersecting trapezoids. Running time: O(nlg n).Day 2–Problem Compare. Alice gets a number a, and Bob gets a number b. Both are integers in {0, ..., 4095}. Bob's goal is to compare b to a (and output "greater than", "less than" or "equal"). Charlie is helping them. Alice can send Charlie a set A ⊂ {1, ..., 10240} (intuitively, think of Alice marking some bits in an array of 10Kbits). Bob can ask Charlie whether some x is in A or not (think of Bob as querying some bits of the bit vector). The goal is to minimize (for worst-case a and b)
T=|A| + the number of queries made by Bob
Desired solution: We know how to get T=9. In the Olympiad, T=10 was enough for full score, but we left the problem open-ended, so T=9 would've earned you 109 points.
Somewhat unusually for computer olympiads, in this problem we could test contestant solutions exhaustively: we ran their code for all 40962 choices for (a,b) and really computed the worst-case T.
Interesting stuff. Two questions:
ReplyDelete1) in Compare, Bob's queries are adaptive, right?
2) On the TimeIsMoney problem: Not being an algorithms person, I'm curious how often publishable results of form "Problem X is in poly-time" appear. Of course, you should try to optimize the runtime, but how often is just placing in poly-time a real achievement? And how many open problems of this type get solved in a given year? I'd be curious to hear anyone's impressions on this.
Yes, Bob's queries are adaptive.
ReplyDeleteNot being an algorithms person, I'm curious how often publishable results of form "Problem X is in poly-time" appear
Very often in certain areas, e.g. approximation algorithms and fixed-parameter tractability. As an algorithms person myself, I often don't find such results interesting, since most algorithmic work is hidden inside a few big hammers that get used.
Here I'm stating the goal as "poly time" to make the difficulty close to the Olympiad problem. In the Olympiad, you could get full score by doing "something reasonable" without analyzing the run time (of course).
A first guess about the first problem: By the geometry of the objective, observe that there is some 0 <= s <= 1 such that minimizing (total A-cost)*(total B-cost) is equivalent to minimizing s*(total A-cost) + (1-s)*(total B-cost). However, trying "all" s does not work, but we can iteratively increase s and update the spanning tree whenever necessary. Every time we update, we also compute (total A-cost)*(total B-cost). Its not clear that we only have to update a polynomial number of times. To see this, recall that a minimum spanning tree can be constructed via a simple greedy procedure (always add the smallest outgoing edge). On the other hand, for any pair of edges a and b, there is exactly one "breakpoint" s' such that we prefer edge a for s <= s' and b for s > s'. This gives that there are at most n^2 breakpoints. Eternal glory?
ReplyDeleteYes, eternal glory for you. :)
ReplyDeleteToo bad you didn't sign, we don't know whom the glory goes to. But feel free to correct this.
yay, this made my day! Thanks for posting interesting stuff and see you at wads in three weeks. best, tim
ReplyDelete