### pllk's blog

By pllk, history, 5 years ago,

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:

Link to the contest system is here:

http://cses.fi/

You can already register an account to the system. The link to each contest will be activated 15 minutes before the contest.

• +56

 » 5 years ago, # |   0 Awesome! Are there any prizes or certificates for the online mirror?
•  » » 5 years ago, # ^ |   +10 No prizes, it's for fun and practice
 » 5 years ago, # |   +22 Why is it soooo early in the morning :(
•  » » 5 years ago, # ^ |   +42 You can think that it's late in the evening 8)
•  » » » 5 years ago, # ^ |   0 it's 9 AM in my time so too late :D
•  » » » » 5 years ago, # ^ |   +5 Whatever, those online contests are just "service" for them after all.. :)
•  » » » » » 5 years ago, # ^ |   0
 » 5 years ago, # |   0 Where to register?
•  » » 5 years ago, # ^ |   0 We'll post the link here a bit later
•  » » » 5 years ago, # ^ |   0 Will the problems in Russian ?
•  » » » » 5 years ago, # ^ |   +44 with google translate, yes
 » 5 years ago, # |   +3 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.
•  » » 5 years ago, # ^ |   +11 That's a good idea. We'll publish both contests as virtual contests after BOI.
•  » » » 5 years ago, # ^ |   0 Please inform us when it's ready :D
•  » » » 5 years ago, # ^ |   +21 So has this been done?
•  » » » » 5 years ago, # ^ |   +10 Thanks for the reminder :)Day 1 virtual contest: https://cses.fi/87/list/Day 2 virtual contest: https://cses.fi/88/list/
 » 5 years ago, # |   +15 The first contest will start in 15 minutes!
 » 5 years ago, # |   +26 WoW! Outstanding performance of Polish team, especially JanPawel2 and zdolna_kaczka.Are online mirror results published somewhere?And the last one, how to solve that shitty spiral? :P
•  » » 5 years ago, # ^ |   +15 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.
•  » » 5 years ago, # ^ |   +33 Still better task than Bowling
 » 5 years ago, # | ← Rev. 2 →   +8 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.
•  » » 5 years ago, # ^ |   +5 Now it's possible to upsolve the tasks in the system.
 » 5 years ago, # |   +16
 » 5 years ago, # |   +18 The second contest will start in 15 minutes!
 » 5 years ago, # |   +8 How to solve Cities for k={4,5} ?
 » 5 years ago, # |   +3 Stuck solving subtask 1 of problem Cities (52+27+100) 479 in total
 » 5 years ago, # |   +10 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) :(
•  » » 5 years ago, # ^ |   +5 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
•  » » » 5 years ago, # ^ |   +10 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.
•  » » 5 years ago, # ^ |   +5 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)?
•  » » » 5 years ago, # ^ |   0 What is that n3k in your solution ? Maybe I have calculate my complexity wrong.
•  » » » » 5 years ago, # ^ |   +5 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
•  » » 5 years ago, # ^ |   +13 my solution is O(K^2MlgM + K!N) and I'm surprised how diverse the complexity is :p
 » 5 years ago, # | ← Rev. 3 →   0 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.
•  » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +10 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!
•  » » » » 5 years ago, # ^ |   +10 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
 » 5 years ago, # | ← Rev. 2 →   0 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): ox#....o# .#..#..#o ...#..#.. ..#..#... o#..#..#. #..#..#.. ..#..#..# ....#o..o...so I suspect that the solution is based on using diagonal lines like these, but better.
•  » » 5 years ago, # ^ |   +26 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).
 » 5 years ago, # |   0 Slightly unrelated, but is there any judge where we can find past BOI tasks to practice on?I couldn't find any via Google :/
•  » » 5 years ago, # ^ |   +6 Two editions (2008, 2015) are here: http://main.edu.pl/en/archive/boi
 » 5 years ago, # |   +3 Is it possible for the official contestants to view their solutions now? I would love to view my codes from BOI.
 » 4 years ago, # |   0 Hi! I would like to invite you also to Deadline24 marathon. The registration of the teams is up until March 9, so only few days left. For more information visit www.deadline24.pl (Sorry, but I didn't know where I can put this information)