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 :)

## 3 comments:

What Problem 3 seems to ask implies that you can encode a sequence of N integers in a sequence of N/2 integers, which is obviously impossible. Is there something missing in the problem statement?

Anonymous, you have it wrong. What you just argued is that for an average M[], there are many possible solutions A[] (this is basic counting). The problem asks to find one of them.

Solution for the first problem: do binary search. Suppose we have fixed R, now we want to check if it is possible to place 2 circle with radius R. Let's move all sides of the polygon by R inside, and then check if the diameter of the resulting polygon is greater or equal to R. And yes, I wouldn't like to implement this. :)

Post a Comment