I would like to invite you to participate in the online mirror of the Croatian Olympiad in Informatics which is held this Saturday.
The problemset will consist of 3-5 IOI stlye tasks and you will have 5 hours to solve them. The expected difficulty is greater than usual COCI rounds, but lesser than IOI.
Click here to see where the coding begins in your timezone.
I see new backup menu in evaluator. What is that for?
Thanks in advance :)
You can backup files on the judge if you are afraid you will accidentally erase them loacally or something. As far as I know, nobody really uses it.
It tell's me that I am not allowed to log in from this location. Can anyone help me?
You should select "Croatian Olympiad in Informatics" in the dropdown menu.
This is a problem in every Croatian contest, so maybe the organizers could fix this?
Will there be an immediate feedback like in IOI?
yes
Nice! If I remember correctly, last year there was no feedback during the contest
Unfortunately, there is no full feedback :(
sorry, I was wrong, there is no full feedback
Start delayed by 15 minutes?
Yeah for me too.
.
There actually isn't real feedback. The system just says whether we have passed the samples or not.
Really nice contest.
How to solve 3 and 2?
with centroid decomposition intended to pass for 100?
On 1 is O(N * M) the intended solution?
On 4 is
Also when will results be available?
How did you solve 1?
I solved 4 for 40 points. Suffix array + LCP for chain, dfs O(n2) for n ≤ 1000.
How to solve for 100?
2) Divide and Conquer
wow the solution comes really easy when someone tells you to think about divide and conquer :/
But you need to carefully handle case when "middle row" components are connected in upper and bottom part simultaneously
When will there be results?
They are out now :)
Solution sketch + 100p Codes
Flood fill from all 0. If x_i don't have to be, we just set them as 1. For all ?s,
? can't be 1 if it can't reach any x_i = 1.
? can't be 0 if there exists some c_i = 1 such that, if ? becomes 0 they can't reach any x_i = 1.
We can check them independently. So let's do that.
First part can be easily checked in O(N) for each c_i.
Second part can be checked in O(N^2) for each c_i naively. However, if we run bfs from any x_i = 1, which can't be reached by that ?, we can determine if there exists that c_i. So it can be reduced to O(N) per ?. total O(N^2)
https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_ili.cpp
If we have the spanning forest, component size = |V| — |E|. Group each column's consecutive 1s as one node. Now let’s make spanning forest for [0, N-1]. Some edges will be in spanning forest, but some are not. However, you can observe that the graph is planar. So we can calculate the cycle which that edges belong. (we should do it enough smart to maintain O(NM) time complexity) If the cycle goes broken, then we should use that edge.
In conclusion, we can know what edges do [i, N-1] spanning forest contains. This also enables us to know what edges do [i, j] spanning forest contains. To solve it faster, for each edge and vertex, compute how many interval uses them. You can do some math to figure out that.
Some details are omitted as they are hard to explain. My implementation is about 100 lines, so it’s not that long.
total O(NM * Ackermann(NM)) https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_raspad.cpp
We can carefully model the given structure as a grid graph. Something like :
Every block has a center. If the center's position is (X, Y), We color that block as (X + 3 * (Y mod 2)) mod 6 + 1. It's not hard to prove that for every placement this coloring works. So we need to find any block placement which completely covers the grid. I found that with O(4^N * N^2) bitmask dp. I think constant factor is not that bad.. but eh, let's see. https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_trapezi.cpp
Do centroid decomposition. Say the centroid is "(", then we append some others to make it as L(R. Find all possible L, and (R with DFS. correct L should look like ((( + expression + (( + expression + ... . For R it's simillar. Now we find all pairs of correct L and correct R, with same extra ( and )s. this can be done by storing counts. total O(NlgN) https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_zagrade.cpp
For p3, constant factor was not a problem. (worst tc in 0.05s) I fixed one typo (y -> y + 1) and got 100 points. So sad to miss 400p
Sad news : Problem 4 was already posed at JAG contest. (http://jag2015spring.contest.atcoder.jp/tasks/icpc2015spring_a)
Still, the problems were really interesting. I really enjoyed solving it. Thanks for the great effort!