### keko37's blog

By keko37, history, 4 months ago,

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!

• +63

 » 4 months ago, # |   +15 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)?
•  » » 4 months ago, # ^ |   +13 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.
 » 4 months ago, # |   +33 Any success with adding rust?
•  » » 4 months ago, # ^ |   +7 No, sorry. :(We didn't manage to do it for this round. We'll try to do it for the next one.
•  » » » 4 months ago, # ^ |   +6 Thanks for info. Let's hope
 » 4 months ago, # |   +32 If you want to try to do C in linear time, here's a version with higher bounds.
 » 4 months ago, # | ← Rev. 2 →   +13 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.
•  » » 4 months ago, # ^ |   +34 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.
 » 4 months ago, # |   +19 problem Parkovi (D) is similar to Atcoder ARC116_E — Spread of Information
 » 4 months ago, # |   0 Can someone please explain the idea behind problem B? My approach: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 = 2 and iterate until min(n,k) and update the distance and transfer arrays with Floyd-Warshall, if possible (sum of transfers from the two chosen nodes is less than r) 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.