The Nordic Olympiad in Informatics 2019 was held yesterday. The contest is an IOI style practice contest for students from Denmark, Finland, Iceland, Norway and Sweden.
This year's contest is now available as an open virtual contest at:
The length of the contest is 5 hours, and there are 3 tasks. The contest follows the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.
You can start the contest at any time between 7 March 2019, 9:00 and 10 March 2019, 15:00 (UTC). After that, the results will be published.
Reminder: You have about 24 hours time to start the contest
The contest has now ended and the results are here.
Congratulations to Jatana for winning the contest by solving the last task!
Is there going to be editorial?
Thank you for great problems! It's sad that I was too busy to participate.
The last task is a slightly harder version of Southern Subregional 2016 K (no link cause CF is broken now). When I virtually participated in it, I spent about 3 hours on K but got almost no idea from it. Could you tell me how to solve it?
https://en.wikipedia.org/wiki/Bipolar_orientation
If we have valid source and sink then we can construct a valid orientation with ear decomposition as follows:
Take any path from source to sink. Then, add each ear one by one to the current construction and numerate added vertices in the correct order.
To find valid source and sink let's look at the biconnected components of our graph. They must form a 'bamboo' because if there is a some component out of our 'bamboo' we can notice that it is impossible to orient edges correctly.
For a valid source and sink we can select any vertex(except articulation point) from the leftmost biconnected component and any vertex(except articulation point) from the rightmost biconnected component on our 'bamboo'.
Even if biconnected components form a bamboo, we won't necessarily find a solution, right? I'm concerned about this case:
I've never implemented the ear decomposition. Can you tell me if the following approach is correct for adding a new ear? We have some already visited vertices, let's call them "fixed". We run DFS from one of fixed vertices, say a, go through some non-fixed vertices and always check all neighbours and if any of them is fixed but not a, then go to that vertex and we have an ear (now we mark all its vertices as fixed too). If we never can go to a fixed vertex different than a, there is no ear decomposition (like on a drawing above). Sounds ok?
In your case 3 is a cut vertex, and there is a separate biconnected component hanging in 3, so it's not a bamboo. Maybe this is not formally correct, but at least this is what he was trying to say.
Wikipedia has a much clear statement: The graph has an orientation iff it becomes 2-vertex-connected after adding edges between s and t.
Btw, I tried to do the ear decomposition, but I don't know its correctness. I know that 2-vertex-connected graph has an ear decomposition. Does it still have an ear decomposition, if I force to start from some arbitrary cycle?
Your ear decomposition algorithm sounds good at least I have something similar. Do not forget that the start of ear and end of the ear must be different.
Just solved the problem using tarjan's algo and block-cut-tree last night..