International Olympiad, Day 1

The problems for Day 1 of the IOI have been posted (in many languages). Exciting! Here are the executive summaries. (Though I am on the International Scientific Committee (ISC), I do not know all the problems, so my appologies if I'm misrepresenting some of them. In particular, the running times may easily be wrong, since I'm trying to solve the problems as I write this post.)

The usual rules apply: if you're the first to post a solution in the comments, you get eternal glory. (If you post annonymously, claim your glory some time during the next eternity.)

Problem Fountain. Consider an undirected graph with costs (all costs are distinct) and the following traversal procedure. If we arrived at node v on edge e, continue on the cheapest edge different from e. If the node has degree 1, go back on e. A walk following these rules is called a "valid walk."

You also have a prescribed target node, and an integer k. Count the number of valid walks of exactly k edges which end at the prescribed target node. Running time O~(n+m) ["O~" means "drop logs"]

Problem Race. You have a tree with integer weights on the edges. Find a path with as few edges as possible and total length exaclty X. Running time O(nlg n) [log^2 may be easier.]

Problem RiceHub. N rice fields are placed at integer coordinates on the line. The rice must be gathered at some hub, which must also be at an integer coordinate on the line (to be determined). Each field produces one truck-load of rice, and driving the truck a distance d costs exactly d. You have a hard budget constraint of B. Find the best location for the hub, maximizing the amount of rice that can be gathered in the budget constraint.

Running time: O~(N).

Balkan Olympiad (Day 2)

Now is time for the problems on day 2 (of 2). See here for day 1. Feel free to post solutions in the comments (you get eternal glory if you're the first to post one) and discuss anything related to the problems.

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(n²m 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 4096² choices for (a,b) and really computed the worst-case T.

Balkan Olympiad

The Balkan Olympiad is over, and I am slowly recovering from the experience of chairing the Scientific Commitee. For your enjoyment, I will post summaries of the competition problems. Perhaps this post should be titled "Are you smarter than a high school student?"

Day 1 – Problem 2Circles. You are given a convex polygon. Find the largest R such that two circles of radius R can be placed inside the polygon without overlapping. Target running time: O~(N). I think this problem illustrates the rather significant difference between coming up with an algorithm on paper and actually implementing it (only 4 contestants scored nonzero; the committee says ``Sorry!'').

Day 1– Problem Decryption. We define the following pseudorandom number generator:

• initialize R[0], R[1], R[2] with random values in {0,..., 255}
• let R[n] = R[n-3] XOR R[n-2].

We also define the following cypher:

• let π be a random permutation of {0,...,255}
• to encrypt the i-th byte of the message, output π(Message[i] XOR R[i])

You have to implement a chosen plaintext attack. You get a device implementing this cypher. You may feed it a message of at most 320 bytes (you give the device one byte at a time, and observe the encyption immediately). Your goal is to recover the secret keys (R[0..2], and π).

Day 1–Problem Medians. Given an array A[1..n] of integers, we define the prefix medians M[0..(n-1)/2] as M[k] = median(A[1..2k+1]).

The problem is: given M, recover A. O~(n) running time.

PS: This was by far the best prepared Committee that I've been on, and I think we conclusively proved that, no matter how much work you do before the Olympiad, there's still a lot left to do during the Olympiad itself. Many thanks to everybody who volunteered their time. I wish I could do more to express my gratitude, but for lack of other ideas, it is my pleasure to acknowledge the committee here:

• Marius Andrei - Senior Software Engineer, Google Inc.
• Radu Ștefan - Researcher, Technische Universiteit Eindhoven
• Dana Lica - "I.L. Caragiale" High School, Ploiești
• Cosmin Negrușeri - Senior Software Engineer, Google Inc.
• Mugurel Ionuț Andreica - PhD, Assist., Polytechnic University, Bucharest
• Cosmin Tutunaru- Student, Babes-Bolyai University, Cluj-Napoca
• Mihai Damaschin - Student, Bucharest University
• Gheorghe Cosmin - Student, MIT
• Bogdan Tătăroiu - Student, Cambridge University,
• Filip Buruiană - Student, Polytechnic University, Bucharest
• Robert Hasna - Student, Bucharest University
• Marius Dragus - Student, Colgate University NY
• Aleksandar and Andreja Ilic -- University of Nis, Serbia; external problem submitters, who were not intimidated by the fact that I only posted the problem call in Romanian :)

Please submit...

1. Papers to MASSIVE 2011. This will be a SoCG satellite workshop (think Paris in June...). Publication here does not hinder publication anywhere else.
   
   
2. Algorithmic problems for the Balkan Olympiad (BOI 2011). I am chairing the Scientific Committee, and we need your help in putting together an interesting set of problems. If your problem is selected for the competition, you will be invited to be a member of the Scientific Committee, and you get a free trip to the Olympiad if you accept (think Bistrița in July...). Anybody can submit problems, but I think the free trip only applies if you're starting somewhere in Romania and you are a Romanian/EU^(?) citizen. Hence the call for problems is in Romanian; sorry.
   
   
3. Comments to other blogs. This blog is now on full moderation after I had to delete a batch of comments that did not score particularly high on the sanity scale. Don't worry, the main point of this is not censorship; nasty but coherent comments will continue to be accepted.

Complexity Theory

If you're a student thinking of going into complexity theory, take a good look around and ask yourself: "Do I really want to be in a field with this amount of groupthink?" [1,2,3,4,5, and last but certainly not least 6]

Back in the day, I was myself saved from a career in complexity by Omer Reingold's logspace connectivity.

FOCS 2010

I am back from FOCS 2010, where I gave two talks:

• a tutorial on data structure lower bounds: PPSX, PDF
• a regular conference talk on distance oracles: PPSX, PDF (for this paper coauthored with Liam Roditty).

This paper caused some amount of fun in certain "inner circles", which I think I should share with a wider audience. If you read the paper, the algorithms repeatedly grow balls (aka shortest path trees) around vertices of the graph. After obsessing about growing these balls for more than a year, I found it natural to name the paper "How to Grow Your Balls". At least it allowed me to begin various talks by telling the audience that, "This is a topic of great economic importance; I receive email about it almost every day."

The committee took its role as Cerberus at the gates of Theory very seriously, and refused to accept the paper under the original title. In the process, many jokes were made, at least some of which transpired outside the PC room. I won't post them here, as the PC probably intends to keep some decorum. (But if you get a chance, ask your friend on the PC about that proposed proceedings cover.)

So the title changed, but I stretched the joke a bit further by titling the tutorial "How to Grow Your Lower Bounds".

This episode confirmed two things that I already knew. First, this community insists on taking itself way too seriously. For comparison, the title certainly triggered some PR alarms inside AT&T. But it made it through, perhaps because I told people that it's in the interest of AT&T Labs to prove publicly that it's a real research lab: it lets researchers be researchers, which includes being silly at times. Given the reputation of PR departments in American telecoms, it's a bit sad to find that the theory community has a higher bar on form.

Secondly, I should turn it down a notch with this blog. Several people said they had expected me to withdraw the paper rather than change the title. I found it quite amazing that people had such an image of me. Perhaps it is time to emphasize that I'm doing my research because I think it's important and cool. The horsing around is, well, not quite the main message.

Problem solving versus new techniques

This is a guest post by Mikkel Thorup:

--------------------------

I think there is nothing more inhibiting for problem solving than referees looking for new general techniques.

When I go to STOC/FOCS, I hope to see some nice solutions to important problems and some new general techniques. I am not interested in semi-new techniques for semi-important problems. A paper winning both categories is a wonderful but rare event.

Thus I propose a max-evaluation rather than a sum. If the strength of a paper is that it solves an important problem, then speculations on the generality of the approach are of secondary importance. Conversely, if the strength of the paper is some new general techniques, then I can forgive that it doesn't solve anything new and important.

One of the nice things about TCS is that we have problems that are important, not just as internal technical challenges, but because of their relation to computing. At the end of the day, we hope that our techniques will end up solving important problems.

Important problems should be solved whatever way comes natural. It may be deep problem specific understanding, and it may build on previous techniques. Why would we be disappointed if an old problem got solved by a surprising reuse of an old technique?

Elegant reuse of old techniques is not a bad thing. After all, when we develop new techniques, we are hoping they will be reused, and from a teaching perspective, it is great to discover that the same general technique applies to more diverse problems. The last thing we want is to encourage authors to hide reuse. Of course, reuse should be highly non-obvious for a strong conference, but for established open problems, non-obviousness will normally be self-evident.