Hello everybody,

The annual Balkan Olympiad in Informatics is being held in Ruse, Bulgaria and the first day has just passed. Every year I post the problems and my solutions/thoughts about them, but this year the organisers were kind enough to upload the problems themselves, so here are the tasks.

Circus

The first problem actually turned out to be the hardest. The problem has a few quadratic complexity solutions that take up to 51 points and can be found easily. Only one person had 100 on this problem, and only two others had more than 51 (having 82). The solution of all three was similar and was a bit "risky" as it relied on an unproven fact — the path will change direction very few times. As it turns out, the path has the general form of "go right for some time — go left for some time — go right". This is not proven but I couldn't find any tests disproving it (any ideas of why is it correct would be nice) and it seemed to give full score if an idea based on it was implemented nicely.

The actual solution was actually to run a Dijkstra algorithm starting from position M, and for each rope to calculate the minimum distance that you can hold on to it and still be able to reach the final. The trivial implementation is O(N^2) as you may have to consider all N^2 pairs, but it turns out that there is some way to optimize it and make it somewhere around O(NlogN). There is no analysis yet, so this is the vague idea I understood.

I got 51 points on the problem as I couldn't come up with anything better than quadratic complexity.

Happiness

This problem was solved by about 8-10 people. The solution wasn't very difficult — one had to notice that a problem might occur at such i, that A[i]>2*A[i-1]. As the numbers were up to 10^12, you could have at most log 10^12 such points, and you could easily check whether each one is a problem in O(log) per check, making the total complexity O(log^2) per query.

As far as I know, one could implement O(log) per query complexity solution using Balanced Binary Search Tree, but it wasn't required. I scored full score with an O(log^2) solution.

TTT

This problem was the easiest. It is not hard to see that the grid quickly becomes smaller and there are not too many valid states, so simply brute-forcing them all with some memoization could solve all test cases instantly. I also managed to get full score on this problem.

In the final ranking Hristo Venev (Bulgaria) and Marko Stanković (Serbia) got 1st place, both with 282 points. Looking forward to day 2 :)