Hey!
I am not related to the organization of this competition, however there doesn't seem to be any blog post regarding it (and there's not much time left), which is unfortunate so that's why I'm writing this :).
Today (in approximately 4.5 hours, 14:00 UTC) starts this year's COI — Croatian Olympiad in Informatics. The contest is open and the registration page is here (while this page contains a redirect to the registration, along with their past problemsets).
The competition should be close to IOI style; It seems to contain ~4 problems and from what I understood, has a duration of 5 hours. A big difference is that there is no full feedback during the contest: every submission is only tested on the samples provided during the contest (I would expect them to change this format for COI but it doesn't seem to be the case).
Good luck! Let's discuss the problems and the solutions here after the contest ends :).
I put all my time into B (after finishing A though it might be wrong/have corner cases, as I did not prove it)... so my score wouldn't be high but I had a lot of fun. Hopefully I'll get something high on B (hopefully there won't be bugs...).
Regarding C and D, I'd like to know how people solved C (for 100 points). As for D, I still want to think about it.
What is your strategy to pick high points from B?
I had many cases. I managed to convert some to others to shorten my work, but still there were many left. I believe my solution is optimal, because for all cases the polygon I build has 0 points inside (besides the case where a = b = 0, where I'm not sure if what I did was optimal but it seems so).
I'll probably share it, later though.
Edit: I got most of the tests right, on all others I recieved "Invalid number of segments of some type"... I guess I need to bugfix now :P
Seems you got 30) Can you please now eleborate your solution?
How to solve paprike?
Deleted. I thought B was finding max area polygon. Stupid..
Results are available!
Can C be solved with antipodal points and segment tree?
UPD: Yes, it can. Just got AC.
I forgot that there may exist colinear points so that I can't get AC during the contest.My code: https://paste.ubuntu.com/p/VJ9HH5wcYd/
How to solve C,D?
A : DFS and greedy. For each subtree, calculate the minimum cut, and the cost going up toward the root after the cut. You can find it in bottom-up fashion, with sorting
C : Think about a huge circle of radius 10^100, which have a center inside of polygon. It will be so big that the polygon will now look like a point. We will place a point in such circle (because why not, large distance is better).
A segment will be lit when the point is in certain circular arc of a huge circle. This means, if we place a point in a certain circular arc, we get a reward — the length of segment. We should place a point, where gives maximum profit. Also, for each query, two segment disappears and one segments appears, which means we have only O(N+Q) events of reward modification. Maintaining the maximum reward point can be done by coordinate compression (on angles) + lazy segtree.
D. We inductively maintain a partial order P. Suppose we have a partial order for numbers < i. When we add number i, we check whether there is an relation from j to i. This can be done by making queries of (numbers < i && !jPx) i (numbers < i && jPx) (numbers > i). Given partial order we can find a lexicographically minimum answer with greedy. The inputs are small so any poly algorithm will work.
Can you explain much about Coordinate Compression?
Our circular arcs (let’s just say “queries” from here) have at most O(n+q) distinct endpoints — where the rewards decrease or increase. This means we don’t have to consider all real numbers but a query’s endpoints, or any point arbitrarily close to them.
So if we consider all queries offline, we will use coordinate compression in those endpoints, which can be represented with vectors from origin — essentially a integer pair, that can be compared with angular sorting.
In my code, I used some tricks to ease implementation. Code
What do you mean by "(numbers < i && !jPx) i (numbers < i && jPx) (numbers > i)" in problem D?
I think it's better to attach my code doing that part :
sorry to bother, Can you explain how do we greedy in pA :(((
You can submit all problems here: https://oj.uz/problems/source/311
fixed
How can I deal with the error 'The response parameter is missing' when I'm registering. Thanks.
Problem B (Pick) Super ad-hoc problem. Many cases have a polygon that does not have any inner points. Find a base shape type 1~4. Grow to the right using a. Grow to the up using b, c, and d.
Type 0: a, b, c, d = 0, 0, 2r, 2s. c and d are positive. Corner case that is given sample input 2.
Type 1: a, b, c, d = 2p, 2q, 2r, 2s. a and b are positive.
Type 2: a, b, c, d = 2p, 2q, 2r, 2s. a and c are positive.
Type 3: a, b, c, d = 2p, 2q, 2r + 1, 2s + 1. a, c, and d must be positive.
Type 4: a, b, c, d = 2p + 1, 2q + 1, 2r + 1, 2s.
Otherwise, swap(c, d). It is mirrored problem with a line x = 0. More otherwise, swap(a, b). It is mirrored with a line y = x. I think there is no polygon for remaining cases, but I don’t have proof.