Hi everyone!
The fourth round of COCI will be held tomorrow, January 29th 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 ominikfistric, Bartol, paula, pavkal5, and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
The timing does not work for me, unfortunately. But I really want to try the problems. How can I virtual it (or upsolve the problems)?
You can view old COCI problems on the judge by going to tasks (HONI). The problems from this round will be added once the round is over, within a day or two.
Any success with adding rust?
No, sorry. :(
We didn't manage to do it for this round. We'll try to do it for the next one.
Thanks for info. Let's hope
If you want to try to do C in linear time, here's a version with higher bounds.
How the fuck have ~50 people managed to solve the third problem? Is there any easy solution which I could not find? I see two solutions with either sqrt decomposition or divide and conquer plus some tricky observations, O(N*log^2(N)) or O(N*sqrt(N)) complexities.
I think the idea of problem C might be a bit classic and old. It has appeared in a Chinese contest about five years ago, and also in the contest mentioned by xiaowuc1. So probably some of the participants have seen this problem before.
I'm not sure of the details of your sqrt decomposition approach, but if your method is to enumerate the majority element — then with only minor modifications you can get a beautiful $$$O(n)$$$ approach.
problem Parkovi (D) is similar to Atcoder ARC116_E — Spread of Information
Can someone please explain the idea behind problem B?
I tried using a modified Floyd-Warshall, also storing the current number of transfers in a 2D array(similar to the distance array). Then let
r = 2and iterate untilmin(n,k)and update the distance and transfer arrays with Floyd-Warshall, if possible (sum of transfers from the two chosen nodes is less thanr) and desired (sum of the distances is less than the current distance). Then the queries can be answered in O(1).I got 40/70 pts, so I'm wondering if my approach is nearly correct or if I'm actually completely wrong.