Hi everyone!
The 18th season of COCI is starting soon! The first round will be held this Saturday, November 4th at 13:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.
The round was prepared by ppavic, ToniB, mlicul, itiamhr and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you and good luck!
Update: the round has been moved to start 1 hour earlier because of the Meta Hacker Cup.
Auto comment: topic has been updated by vito1036 (previous revision, new revision, compare).
I like COCI. Excited :)
Will register be here: https://evaluator.hsin.hr/events/? When it will be?
Yes it will be here. Idk when will it be open though
It will appear on late Friday and be available until the contest starts on Saturday.
Why the bitset is in the tags of the blog?
We're gonna need bitsets
Hello, I want to register but unfortunately I cannot see the captcha, How can I do?
Maybe try different browser / different device? I really don't know, it should appear.
Sadly Meta Hacker Cup will start as soon as this contest is ended.
We'll try to move it earlier by one hour. Perfect warm up for MHC :)
Auto comment: topic has been updated by vito1036 (previous revision, new revision, compare).
With the 1h moving it overlaps 40 minutes with ABC. So the best time would have been 13.50 UTC, leaving 10 looong minutes between ABC and COCI and between COCI and MHC :D I'm joking, for this only Saturday I will give up ABC in favour of COCI
Reminder: the contest starts in one hour.
Is there a $$$n*m$$$ solution for the problem C? I have tried 3 different $$$n*m*logn$$$ solutions but they did not pass :D (with RMQ, segment tree, and set)
Anyway, thanks for the nice problem setting!
However, I did not understand why $$$n*m*logn$$$ did not pass in 4 seconds.
Yes, our intent was to force O(n*m) solutions, but if optimized enough even O(n*m*logn) could pass.
Try using minimum queue.
I strongly believed that it would pass :)
Anyway, thanks a lot I will look into it.
Problem is in too big constant factor (for set/segment tree)
For RMQ isn't memory N^2 log N? Then it was clear why it was not working
I solved it in O(n*m*logn) with Fenwick Tree and binary search on it (bit by bit) (finding last non-zero element in cnt[20000] aray)
It seems you learned reducing constant factor after the accident lol
true xd
If you use "short int" you will be fine.
no
I accepted it using short int and RMQ
Here is my NMlog^2NM solution that is AC. 2d segtree is fast enough.
Problem E is so annoying, where can I upsolve the problems after contest?
It should be available on the tasks page in the HONI category soonish.
You can now upsolve the problems here.
Go to HONI > 2023./2024. > 1. kolo, and you should be able to see all the tasks.
When, you will add editorials and test cases?
Thanks for good contest :D
They will be uploaded in a day or two, probably.
How E?
Ah yeah, I should write it today. In short, you find a dfs-tree and fix some backedge, then by careful analysis of the other backedges you can figure out if it's good or not.
Let (u, v) be a backedge, and let u be the node closer to the root (suppose u is not the root). Then you can think of three important components, UP (part with the root), MID (part between u and v) and DOWN (children of v). The other children of u have to be connected to UP and that can be easily checked. There are two important cases:
There is some component in DOWN connected to both UP and MID. Then it is enough to check whether all the components from DOWN are connected to either UP or MID.
There is no such component. Then there has to be a backedge from MID to UP. And again all DOWN components are connected to either UP or MID.
All of the checks can be preformed with segment trees. A helpful thing to precalculate is for every node, the highest and lowest backedge going out of it. It can be done either with small to large or segment trees.
Great problem btw!
I immediately thought of DFS trees, but it seemed too complicated to track the cases, so I tried using SQRT decomposition. For nodes with more than SQRT(M) degree, do DnQ over all N nodes excluding the edges coming from that node, and for nodes with less, do a DnQ over time. But it comes out to O(sqrt(M) * log(M) * (M + N)) which sadly doesn't pass all :(
I will try to solve it with DFS trees some day... Is there some other interesting solution for it?
Delete Two Vertices Again (editorial)
:(
My solution needs segment tree merging, is it necessary?
Can you share your idea in problem B and problem C,I found problem C very interesting problem,thanks for author of problems
Let's denote each color by some bit. $$$P=1, C=2 , Z=4 , N=8.$$$
We can build adjacency lists from the input in the beginning using what I said above.
Now for each query let's do DFS from $$$(a,b)$$$. But how will we find minimum number of colors? Let's add a third parameter $$$mask$$$ which is a bitmask representing what colors we took until now. When we go from a cell to another we make $$$mask = mask | edge$$$. Now let's see the minimum number of active bits for all masks we visited $$$(c,d)$$$ with.
Time complexity: $$$O(2^{colors}qnm)$$$
The problem is very simple. Take the maximum of every subgrid with dimensions $$$(r,s)$$$ this can be done with sliding window, or optimized BIT.
Time complexity: $$$O(nmlogn)$$$ or $$$O(nm)$$$ depending on implementation.
in sliding window -> what is your time limit?
which date structure did you use in sliding window?
Deque. Check this
how D?
Thank you!
Can you please add the results?
Results for neither COCI nor HONI are public yet.
asdasdasd