I'm surprised there's no blog post to this... just so nobody misses it:
Round 3 of Croatian Open Competition in Informatics takes place at this time today, and lasts 3 hours.
You can log in to the contest site at evaluator.hsin.hr, or register an account there if you don't have one already. Make sure to select the right contest from the list when logging in — it's not HONI, but COCI.
Everything related to the contest should be posted here in a few weeks' time (except the solutions, it seems).
Feel free to discuss the problems here after the contest is over.
Isn't KOLINJE solvable in linear?
Yeah, it should be, and easily. I don't know why the constraint on N is so low. Maybe preparing people for FB Hacker Cup and its fake constraints :D
I failed most tests on it, though — because I didn't write
long longinstead ofintonce. Punishing such silly mistakes excessively is the main unfairness of contests without feedback...How to solve 6th problem?
Is the idea of the sixth problem to maintain a set of slopes (convex hull method) to find the nearest covered points to the left and right of each building?
My idea involved keeping a convex hull of a decreasing sequence of buildings seen so far, from which one of those points can be directly extracted. But it should work with a structure for set of slopes as well, since it's not much different.
Test are very simple on KOLINJE!
Anyone know how to you solve 5th problem?
I could wait for the official solutions, but yeah they're a bit slow with them.
Suppose that you're counting the "difference" of 2 numbers, X and Y. How many times will the i-th digit of X be equal to x? And how many times will that digit of Y be equal to y? You can count that (it's actually the same result for X and Y if x = y), and from it count how many times will you count |x - y| into the result. Loop that over all x, y and i.
How to count how many numbers in the interval [A, B] have x as the i-th digit? That interval is the difference of [0, B] and [0, A - 1], and so are the answers, so let's just take A = 0. Well, if the part of the number before the i-th cipher is strictly smaller than in B, we can choose all digits from i + 1 to last position to be anything from 0 to 9; it can't be larger, and if it's equal, the part of the number after the i-th position must be ≤ to that in B. Using modular arithmetic, it's not hard to count it using this.
Awesome, thanks.
repetition
Как решалась задача PAROVI ? Никакая идея не пришла в голову. И пожалуйста, по возможности на простом языке можно объяснение, так как я начинающий?
Сверху предлагают на английском.
The full results are up in the system.