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