Tuesday, July 12, 2011

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


Anonymous said...

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?

Mihai said...

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.

Anonymous said...

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