Hi everyone!
Forth round of COCI will be held this Saturday, January 16th at 14: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 paula, Shtef, dpaleka, pavkal5 and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you on Saturday!
Can you add these rounds in kattis for upsolving/practicing? I see some COCI rounds are there, some not.
Can it be postponed by 10-15 minutes so that there is some gap between arc and coci.
Is there any online mirror?
It is here: https://evaluator.hsin.hr/events/ -- is this what you are asking?
Thanks
Is it possible to add a gym contest on Codeforces?
We were going to add a "COCI season icpc-style contest" to the gym sometime. I think oj.uz has separate contests usually.
Thanks! :)
Is it just me or was this round tougher than usual? An interesting experience still, but I feel like first problem was way too easy as compared to the others.
And why wasn't there a story behind second problem? :(
Yeah, I take responsibility for the lack of storytelling in this round. But I think the story for Patkice compensates for Vepar and Hop.
The second problem on COCI is usually intended as an educational one in the Croatian version of the contest, so we may keep the stories shorter there.
How to solve D? I wrote centroid decomposition with fenwick tree of ordered_set, but this got TL and only 15 points...
It's centroid decomposition. In each subtree count number of pair $$$(v, u)$$$ such that $$$max(high(v), high(u)) - k\ge depth(v) + depth(u)$$$, where $$$high(v)$$$ is the maximum edge from root to $$$v$$$ and $$$depth(v)$$$ is the depth of $$$v$$$. This can be calculated using fenwick tree only.
Did you use any other structure like ordered_set?
No, you can just sort all the nodes by $$$high(v)$$$ increasingly. And enumerate the one as larger $$$high(v)$$$. And this reduces to finding numbers of $$$u$$$ such that $$$high(v) - k - depth(v)\ge depth(u)$$$, which is sufficient to just use fenwick tree.
Are the results to be released? Also how to solve p3 Hop?
The rest of the full point sols are on my github: link.
Let $$$B_i = \lfloor \log_2 A_i \rfloor$$$. If there is an edge between $$$x, y$$$, then $$$B_x < B_y$$$. And $$$0 \le B_i \le 59$$$.
Now take a length-3 base-4 representation of $$$B_i$$$. For all $$$i, j$$$, print the first position where two length-3 numbers differ.
Do you know of problems with a similar trick? I vaguely remember seeing similar stuff before but cannot pinpoint where.
Yes. If you come up with the logarithm, it's more or less just this.
:(
Damn I'm rusty. Didn't participate in any contests for quite some time, but I thought COCI was usually on easier side :P
Anyway, was a Dijkstra on 16 million vertices not supposed to pass in the last task? I got time limit, and because the tests are grouped very unpleasantly, I got nothing for the whole 80 points subtask :P Not a fan of grouping tests that aggresively. (Unless my program just hangs on that test or something :P)
mkisic's implementation with Dijkstra runs in 1s (out of 2s TL), but the intended solution is the asymptotically faster 0-1 BFS, if I'm not mistaken.
The grouping of the tests into clusters is what IOI does, and COCI is primarly intended as a training contest for Croatian high school competitors. Although, I guess we could work on making clusters more granular.
Digression: we encourage feedback like this, all contestants (both on COCI and the Croatian version) who have feedback on the problems, the best place is these Codeforces threads for COCI.
There were only 4 million vertices though, right? What I did, and I assume it's the intended solution, was 0-1 BFS which probably makes a significant difference.
This was my implementation of 0-1 BFS
Okay, my solution was that the graph's vertices are of the form: (row, column, direction) and it means the shortest path from the start to a given field, assuming we change the arrow on that field to point into a given direction. The cost is 1 when the field you're about to enter has a different arrow than the one we're about to set. ... but yeah now that you mention it, I can see that this third dimension isn't strictly needed, if we assume we modify the arrow from the field we're departing from, instead of the one we're arriving at.
... and yeah, I did remember you could get away with a special BFS in this case, but I didn't assume organizers would be that mean ;)
Solutions are posted: https://hsin.hr/coci/
Hello! I am reading editorial for task B and in Necessary skills I noticed Vp. What is it and where i can find related sources to understand Vp? Please help me:)
Sorry, I should have elaborated a bit more, but writing is hard...
The notation $$$v_p(x)$$$ denotes the "largest power of $$$p$$$ that divides $$$x$$$". For example, $$$v_2(8) = 3, v_5(100) = 2, v_3(7) = 0$$$. You may have seen the Fundamental Theorem of Arithmetic in this form: $$$n = \prod_{p} p^{v_p(n)}.$$$
This $$$v_p$$$ comes up in problems that ask for divisibility, because if $$$y$$$ is a multiple of $$$x$$$, then $$$v_p(y) \ge v_p(x)$$$.
In this task, we use https://en.wikipedia.org/wiki/Legendre%27s_formula to calculate $$$v_p$$$ of an interval -- although you could probably come up with the formula by yourself, the proof is a single line.
Can anyone well versed in Codeforces problems give an example where a similar approach is used?
Thanks a lot!
Where can I upsolve this contest?
go to this website Tasks-> HONI-> 2020./2021. -> 4.kolo
You can solve all problems here: https://oj.uz/problems/source/540