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 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 :)
First time I will say , why downvotes ?
Can you describe solution on problem 2 more ? I understand everything ( but I really want to hear how you check does it exist A[i]>2*A[i-1]).
Problem three is very bad, I don't like brute force solutions ( probably with some recursion ).
Well suppose that you have list of all indices where A[i]>2*A[i-1]. Then you simply have to check with the property described in the statement. You must check whether S[i-1]>=A[i], and computing S[i-1] can be done efficiently using lots of structures. I used a dynamic segment tree with 10^12 leaves (using dynamic memory you can keep it by creating log vertices on each update query) with a leaf representing each possible value. So for example when I'm adding coin with value K, I just add K to leaf K, and then sum up to the root. So when I want to calculate S[i-1], I can just get the sum in interval [1; A[i-1]], as this will give me the sum of all numbers less than or equal to A[i-1].
Sorry if it is not very well written, it is quite late and I'm tired after the long day, if you do not understand the main idea please tell me and I'll try to be more clear.
P.S.
About downvotes — I have no idea, maybe my explanations are not written very well as it is quite late.
I have never used dynamic seg. tree, but I understand what do you want !
Thanks and good luck second day ;)
Thank you, I will post my ideas about the problems once again after the second day :)
Hey, I was told that you got 300. What went wrong?
Oh? I do not know, I got 251 in total, which makes 3rd place. Nobody got 300 so someone must have confused the scores :)
I can't open tasks :(
My solution for Happiness runs in O(QKlgM) time without BBST. Although I am almost certain about this sln, I am bit afraid because I experienced a lots of WA even I was certain :(
Make a dynamic segment tree which has these values in nodes :
1 : Value,
2 : Count of elements having these values
3 : Sum(Value of subtrees)
4 : Min(Sum(Value — 1) — Ai + 1) of subtrees
5 : lazy propagation etc.
When we should insert the value, add the values, and update +Value for [Value + 1, inf].
When we should delete the value, erase the values, and update -Value for [Value + 1, inf]. if value 2 become zero, set value 4 to inf.
We are happy if Min{Sum(Value — 1) — Ai + 1} >= 0 in the root.
Please correct me if I was wrong!
Any chance of virtual contests / possibility to submit?
Well I doubt the organisers will do any kind of submission options. If they publish the tests after the competition, setting up a gym contest so people can submit should be easy :)
Is it possible to see the results of BOI 2015?
BOI 2015 isn't over yet.
Here are the results from day 1 : http://www.boi2015.uni-ruse.bg/competition/results
Tomorrow is day 2 and you can watch live scoreboard here : http://ranking.boi2015.uni-ruse.bg/Ranking.html (it will be active during the contest)
this year the organisers told me when i said "my computer is freezing and i have to restart" they said "the problem is from geany" and he didnt anything
Hello! I tried to solve task Ultimate TTT but I don't know how to check my code. Test data contains only blank solutions and nobody has solved it yet on Baekjoon online judge (I am not even sure if grader works correctly, https://www.acmicpc.net/problem/11554). Can somebody please send me AC code or grader or something so I can check my code?
Fortunately, the author of the problem recently created a judge of his own, containing all (or most) of his problems. Here is the problem, you can register here. I think you should be fine with some google translate.
Thank you very much
Do you happen to have AC code for this problem? I got 95/100 but I am not sure if my code is wrong or maybe there is a problem with judge (nobody solved this problem here as well). If the numbers of test cases are the same as in test data given by organizers then my code surely works right on test 15 (on this judge it doesn't).
Nope, I haven't tried to code it yet. Though, I remember people telling me they were getting 95 during the contest (it was in my city) and just found the hash of the test and guessed the answer :D
I did what you suggested. I downloaded test cases and solved them by hand (twice). Problem is that all my outputs coincide with these solutions. For now I will say that my code works but if some day you decide to solve it and get 100, please let me know.