By DBradac, history, 3 years ago, ,

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.

• +48

 » 3 years ago, # |   0 I see new backup menu in evaluator. What is that for?Thanks in advance :)
•  » » 3 years ago, # ^ |   +6 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.
 » 3 years ago, # |   0 It tell's me that I am not allowed to log in from this location. Can anyone help me?
•  » » 3 years ago, # ^ |   0 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?
 » 3 years ago, # | ← Rev. 2 →   0 Will there be an immediate feedback like in IOI?
•  » » 3 years ago, # ^ |   +4 yes
•  » » » 3 years ago, # ^ |   +1 Nice! If I remember correctly, last year there was no feedback during the contest
•  » » » » 3 years ago, # ^ |   +6 Unfortunately, there is no full feedback :(
•  » » » 3 years ago, # ^ |   +18 sorry, I was wrong, there is no full feedback
 » 3 years ago, # |   +6 Start delayed by 15 minutes?
•  » » 3 years ago, # ^ |   +1 Yeah for me too.
 » 3 years ago, # | ← Rev. 2 →   +5 .
 » 3 years ago, # |   +9 There actually isn't real feedback. The system just says whether we have passed the samples or not.
 » 3 years ago, # | ← Rev. 2 →   +4 Really nice contest.How to solve 3 and 2? On 1 is O(N * M) the intended solution? On 4 is with centroid decomposition intended to pass for 100? Also when will results be available?
•  » » 3 years ago, # ^ |   0 How did you solve 1?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I solved 4 for 40 points. Suffix array + LCP for chain, dfs O(n2) for n ≤ 1000. How to solve for 100?
•  » » 3 years ago, # ^ |   +9 2) Divide and Conquer
•  » » » 3 years ago, # ^ |   +12 wow the solution comes really easy when someone tells you to think about divide and conquer :/
•  » » » » 3 years ago, # ^ |   +9 But you need to carefully handle case when "middle row" components are connected in upper and bottom part simultaneously
 » 3 years ago, # |   +14 When will there be results?
•  » » 3 years ago, # ^ |   0 They are out now :)
 » 3 years ago, # | ← Rev. 5 →   +43 Solution sketch + 100p Codes Problem 1Flood 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 Problem 2If 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 Problem 3We can carefully model the given structure as a grid graph. Something like :  (N-3, 2) - ........ | (N-2, 1) - (N-2, 2) - (N-2, 3) - ........ | | (N-1, 0) - (N-1, 1) - (N-1, 2) - (N-1, 3) - ........ | | (N , 0) - (N , 1) - (N , 2) - (N , 3) - ........ | | (N+1, 1) - (N+1, 2) - (N+1, 3) - ........ 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 Problem 4Do 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.cppFor 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 400pSad 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!