Baltic Olympiad in Informatics 2016 will take place in Helsinki, Finland, May 11–15.
https://www.cs.helsinki.fi/group/boi2016/
Besides the official contest, there will be an online contest that will be open for everybody.
The format is like IOI: two contest days, five hours time to solve three tasks, full feedback.
On both contest days, the online contest runs simultaneously with the official contest, i.e., the contest times are:
- Contest 1: Thursday May 12, UTC 6:00–11:00
- Contest 2: Friday May 13, UTC 6:00–11:00
Link to the contest system is here:
You can already register an account to the system. The link to each contest will be activated 15 minutes before the contest.
Awesome! Are there any prizes or certificates for the online mirror?
No prizes, it's for fun and practice
Why is it soooo early in the morning :(
You can think that it's late in the evening 8)
it's 9 AM in my time so too late :D
Whatever, those online contests are just "service" for them after all.. :)
Service :( :(
Where to register?
We'll post the link here a bit later
Will the problems in Russian ?
with google translate, yes
Any chance the system allows offline participation (practice) after the competition is over? I have school both days and some tests I can't skip but I was really hoping to practice on BOI tasks.
That's a good idea. We'll publish both contests as virtual contests after BOI.
Please inform us when it's ready :D
So has this been done?
Thanks for the reminder :)
Day 1 virtual contest: https://cses.fi/87/list/
Day 2 virtual contest: https://cses.fi/88/list/
The first contest will start in 15 minutes!
WoW! Outstanding performance of Polish team, especially a.piasta and zdolna_kaczka.
Are online mirror results published somewhere?
And the last one, how to solve that shitty spiral? :P
My solution goes something like this. Let's observe the lines y = x and y = -x. Notice that those lines correspond to the "turning points" of the spiral. Every query can be split into O(1) rectangles such that every rectangle is a square whose diagonal is a part of the line y = x or y = -x, or a rectangle which is not crossed by those lines. Now, the sum in each of those rectangles(and special squares) can be expressed as a polynomial of degree 4.
It is easy to implement a function that calculates the value of a certain position in O(1). Using this, we can calculate several positions in a rectangle and using interpolation calculate the entire sum.
Still better task than Bowling
Can you please enable practice soon? I finished problem spiral 3 minutes after the end of the competition and I want to know if I was that close to getting 300.
PS: I saw that we can view the tests, so I run them on my PC and it seems it worked.
Now it's possible to upsolve the tasks in the system.
Day 1 results of official contest
Day 1 results of mirror contest
The second contest will start in 15 minutes!
How to solve Cities for k={4,5} ?
Stuck solving subtask 1 of problem Cities (52+27+100) 479 in total
How to solve A? I solved A in O(2knlogn) which should be just fine, but somehow I have to use fast IO and switch from Dijkstra using set to using priority queue to get AC (1.98s/2s) :(
Can you tell your solution? In my solution, I'm trying all possible cases for all k values. It's O(N * log(N)) but code is so disgusting and doesn't work for k > 5
It's something like dp(x, i) is the minimum cost of a tree rooted at i connect the important city in bitmask x. State transition should be simple. Just note that to update from dp(x, i) to dp(x, j), use a priority queue like in Dijkstra algorithm.
Well i have O((2 ^ k)nlogn + n * (3 ^ k)) and i got TLE on the last subtask, how did you remove the n * (3 ^ k)?
What is that n3k in your solution ? Maybe I have calculate my complexity wrong.
well i updated dp[mask][v] by dp[sub][v] and dp[mask ^ sub][u] that's why it was 3 ^ k — but now i know how to remove it thanks :D
my solution is O(K^2MlgM + K!N) and I'm surprised how diverse the complexity is :p
Ok, the contest is over and I, as any other conscientious student, tried to solve the problems after the contest. Of course, I don't think that I'll be able to find the solution to the second problem by myself, but at least I've tried the 3rd problem. Guess what? No result. Can someone who got 100 points on it, explain it to me? I've got 68 points in contest with some sort of dynamic programming with memoization which can be showed to be called at most Nlog times. It keeps something like the best string that can be obtained applying moves on the nodes in the subtree supposing that the root has a specific value. I managed to keep the string in a smart way which works due to the particularity of the reccurence. My final solution has Nlog^2 time complexity. And as far as I was able to see in the other codes, they all use almost the same recursive method.
well i didn't save the string i saved the best state to which we can go in every state and i have some function show which is for generating the string — first it calculates the dp and after that it will go to the best state that dp has
http://cses.fi/57/result/26804
I think I understood your code but I still have a big question: why does it work? As far as I can see, you store in dp[v][x] the position where the root, considered to have value x will end in the minimal lexicographic solution of v's subtree. Ok, the problem is: why can you compare two solutions, distinguishing which one is better based only on the final position of the root's value? The states of the dp are exactly the same as mine, but I don't know how to prove this assumption (that states that just the final position matters). Can you, please, post a more detailed solution, or, at least, some steps of the proof?
Thanks in advance!
Well i didn't have a prove in the contest but i can kinda say why it works
well there's a fact that the minimum of the root and childs remain in the root and the others will be at the root of one of the childs now imagine we have 2 ways of giving the max element and min element (lets call them mx and mn) to the childs. let's see the first distribution min will end up in lmnpos and max will end up in lmxpos
well let's call the other way rmnpos and rmxpos
well from the minimum of the four elements i declared above to the root all the elements will be the same in both distributions now i just have to say that the minimum of the four elements is the minimum element for sure :D — lmxpos > rmnpos (since the minimum element get's a better position for sure !!) and rmxpos > lmnpos
so the one who's minimum is the leftmost is surely the best state
Does anybody know the optimal solution to Maze (B)? I got 65 points doing something like this (putting the coins into places with three walls around them):
...so I suspect that the solution is based on using diagonal lines like these, but better.
I generated the "most challenging mazes found by the jury" using a dynamic programming solution http://paste.dy.fi/c9e that should give optimal results. In this solution, we construct a tree with at most k + 1 leaves in the grid by filling the grid row by row, maintaining the cells of the boundary and information about which boundary cells are connected to each other. The optimal mazes look somewhat irregular: http://paste.dy.fi/uJN/plain . The code ran for a long time and took a lot of memory, and therefore using a solution like that during the contest time would still require a lot of optimization (for example, pruning some cases out of the dynamic programming).
Slightly unrelated, but is there any judge where we can find past BOI tasks to practice on?
I couldn't find any via Google :/
Two editions (2008, 2015) are here: http://main.edu.pl/en/archive/boi
Is it possible for the official contestants to view their solutions now? I would love to view my codes from BOI.