Hi all,

The Central European Olympiad in Informatics (CEOI) 2022 is starting on Sunday and we'd like to invite you to participate in two online mirror contests that will feature the same problems as the two competition days.

The day 1 mirror will take place on Tuesday, July 26th, 10:00 CEST, and day 2 mirror will take place on Thursday, July 28th, 10:00 CEST. Both contests will last for 5 hours, contain 3 IOI-style problems, and have full-feedback.

In order to participate in the CEOI 2022 Online Mirror contests, you'll need an account on evaluator.hsin.hr. After logging in, you can register for the Mirror contests on the "Events" page.

Hope you'll enjoy the contests.

Btw, evaluator.hsin.hr is amazing online judge.

EDIT: The starting time of the mirror was wrong. The mirror starts at 10 am local time. Sorry for the inconvenience.

Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).Is there any way to register late for the mirror?

We've increased the registration period. You can register up to 14 CEST.

Is Abracadabra just

Spoilersimulation using treap?

un/fortunately yes (or maybe not lol)

Yes

You can do it using only segment tree

wtf how

You can recover the permutation if you know the prefix maximums.

I used a segtree,a Sparse Table and a set.

code...

Why are u using register so much?

I found someone else using register when I started learing and I kept using it until now even when I know it is useless, it's hard to change.

Can you explain a bit?

You can do it using only BIT.

Codereally liked the part of the contest where i got to implement the problems

Is it possible to get a full score with sqrt-decomposition in Abracadabra?

Was the mirror same as the real contest in terms of time limits and the judging machines? I struggled a lot with Time Limit in "P3. Prize". My time complexity is $$$O(N + (K + T) \cdot \log N)$$$ and only got 19/100 points.

Could it matter that I answered queries immediately instead of all at once? I didn't flush the output each time so it should be ok, right?

Me the same. I struggled with (19/100) TLE for a really long time!!Then I accidentally changed my way of answering queries and passed!!

I used to answer queries one by one, flushing my output every time I read a new one.

Then I changed to reading all the queries at once and it passed. I really don't know why..

flushing is expensive

I tried out locally (on prize.in.1a) your last submission that scored 19 pts, and it didn't finish under 20 seconds (then I killed it).

Didn't analyze the code, but it doesn't look like it's due to the way you answer queries.

Was it some special test? I tried chain, star, random tree — each type was below 1s locally.

EDIT: I've just downloaded that test from the system. I get 0.15s locally, strange. Maybe there is UB, I will try to figure it out.

Where can i upsolve this contest?

the same happened to me in the real contest :( , it’s most probably from the way queries are answered…

Yes, I am 99,9% sure that was the problem. I've spent more than 2 hours optimizing everything in my code, but still got 19/100. I started reading queries first, and only than answering. Got 100 immediately. And yeah,I didn't flush either and was sure it should be fine. Very frustrating...What's worse, there are official contestants who got 19 points on this problem. Likely those were the absolutely correct solutions, cause solving only sub task K<=200 is almost impossible(at least I think so).

When will CEOI day1 results be published?

https://ceoi.hsin.hr/preliminary-ranking/Ranking.html

I think B is similar to this CF problem.

I don't understand the point of such tight limits in an interactive problem.N<=2000 would have been completely fine as well.The only additional thing required for higher N is how find distance between 2 nodes in O(logn) which is well-know and doesn't serve any purpose

The main point of large N was to differentiate between subtasks 3 and 4 (gauss vs erdos). This also influenced some of the decisions regarding time limits.

Our solutions and all of the testers that solved the problem fit it comfortably under 3.5 seconds (2-2.5 seconds usually), and we didn't feel it would cause many problems in the contest.

pick one

maybe the high constraints on N and T wouldn’t have caused any problems if the interactor wasn’t so janky

How to upsolve problems?

Can someone explain how to solve Abracadabra and Prize?

AbracadabraMain idea: greedily divide the permutation into disjoint ranges, so that the first element in each range is greater than the rest of the elements (call such ranges

valid). For example, with the sample we haveNote that the first elements of the ranges must be sorted in increasing order. Then, in each move:

If we maintain the set of integers that are the first elements of a range, along with the range sizes, it's possible to get the kth element in the permutation in $O(\log n)$ with something like a Fenwick tree. This allows us to both get the $$$(\frac{n}{2} + 1)^\text{th}$$$ element (necessary for splitting the ranges) and answer the queries.

PrizeSingle tree, $$$Q = K - 1$$$: choose any $$$K$$$ nodes, sort them by preorder, then ask queries about consecutive pairs (v1, v2), (v2, v3), (v3, v4), ..., (v[k-1], v[k]). You should also find lca(v1, v2), lca(v2, v3), lca(v3, v4), and so on. All of that is enough to know all the distances that you need.

Two trees, $$$Q = K - 1$$$: greedily choose the first $$$K$$$ nodes encountered by DFS in the first tree. Then focus on the second tree and apply the logic from before. The answers that you get turn out to be enough in the first tree too — because your nodes form a connected component including the root, and any LCA is one of the chosen nodes too.

Alternatively:

Prizeif you have a set of nodes where the lca of every pair is also in the set, you can simply ask K-1 queries of a constant node with every other node.

the cool thing is, you can always find a a set like that for both trees simultaneously, by starting with the full trees, and deleting nodes which have one or less children in both trees. for each node you delete you only need to update their parent and child, so the complexity for the process is O(N).

There's always a node to delete because the amount of nodes with degree 2 or less in a tree is strictly bigger than the amount of nodes with degree bigger than 2 (pretty easy to prove), so the two such sets for both trees have at least one common node at any given point

Did anyone mange to get $$$O(n^2)$$$ complexity to get the $$$n=10^4$$$ subtask on A? I think calling

`atan2`

$$$10^8$$$ times probably made it TLE. I changed it to dot product but now it WAs for some weird reasonI wonder whether making tests for these problems is harder than the problems themselves

Is there a way to submit? I'm still struggling with C. I found it difficult to implent, is there a good way to do it?

I lost all my time trying to debug it. on the one hand I want to find the bug now and finally get ac, but on the other hand I don't want to see that problem ever again :'D

I have a though about Drawing, but i am not sure that isn't it is the correct solution.Because the node can adjacent to more than three other nodes in this solution.

DrawingWe can just take the point which is the highest (the highest y-axis) as the root, let call it $$$R$$$ .Than we can find a straight line through R that separate the remaining point to some parts.

So,if the root $$$R$$$ have $$$cnt$$$ subtree, we can separate the remaining point with $$$cnt$$$ part. And do it do it recursively.

And how to proof that the edge will not intersect?

Let us suppose that the edge in each subtree will not intersect first. And can proof that the edge of different subtree will not intersect too, because they are separated into two part, and there are no any edge between them (they are in different subtree).

So we can draw it and no any edge intersect.

And that is all my though, I am not sure it is correct or not. Maybe some some statements are not accurate because my english is bad.

Also, I didn't how to implement this idea in $$$O(NlogN)$$$, or we need to use the condition that "each node is adjacent to at most three other nodes"? I hope that someone can help me about this problem, Thanks!

I may be found a similar solution. Firstly choose the uppermost point and set it as root. Then polar sort all of the points according to root. We'll continue with the leftmost available vertex for the first child of the root, now when we look at the process, we're again at a plane with some points and we rooted it from some convex hull point. Implementation:(dfs2 and the polar sort) Your text to link here..., I really feel like the solution is wrong btw. (Also the checker is corrupted probably, for(int i = 1; i <= n; ++i) gets AC).

All accepted solutions of CEOI 2022

(Warning: my solution to drawing is garbage.)

Can you explain how to solve drawing?

SpoilerIt is known that the decremental convex hull problem can be solved in $$$O(n \log n)$$$ time. I copypasted it from here. I don't think this is implementable in the usual OI environment.

Given the solution to the decremental convex hull problem, we can simulate the process efficiently. Take the rightmost point of the hull, and repeatedly remove its adjacent point. If you repeat this $$$k$$$ time, you can obtain the first $$$k$$$ points from the angular order of the rightmost point. For the smaller subtree, initiate a new decremental CH and recurse. For the largest subtree, remove the points from the smaller subtree and recurse.

The time complexity is $$$O(n \log^2 n)$$$. I needed a little bit of constant optimization.

I think this paper contains an $$$O(n \log n)$$$ solution. It could be slightly more implementable from scratch. I don't think it's really interesting though.