Hi everyone!
The fifth round of COCI will be held tomorrow, March 5th 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, pavkal5, and me.
Feel free to discuss the problems in the comment section after the contest ends.
Support for rust will be added either for the next round or for the next season.
Hope to see you tomorrow!
wow
I left the contest when I read the first two problems, Sorry, But this is an Olympiad contest or heavy implementation contest? I didn't like the first two problems this time ...
I agree that A was super toxic but imple for B is quite simple and short?
What is your implementation for B? I rotated the table by 45 degrees and then it can be easily solved, but it wasn't short at all.
https://pastebin.com/eP4wtRVr
Thanks! That implementation was so elegant :orz:
One small question tho, what do
a,b,c,ddo here:I know that they will help you to calculate the area of the diamond (if it is), but I don't know how does it relate to
i+jandi-j.It's just to rotate $$$(i,j)$$$ by 45 degrees. You can read here.
Here is a visualization.
So the smallest rectangle that bounds the area after rotating 45 degrees is something like $$$[a,b] \times [c,d]$$$
Is there any simple solution for task Radio? My approach is really ugly and I don't think it's the intended one...
GCD(x, y) != 1 iff exists some prime number that divides both x and y.
Let's say A[1], A[3], A[4], A[10] are divisible by p, then segments [1, 3], [3, 4] and [4, 10] are "bad", i.e. answer is "DA" if the given segment contains some "bad" segment.
It is clear that the number of bad segments doesn't exceed O(q*k), where k is the maximal number of prime divisors of some number (k <= 7).
Let's update each l with the minimum r such that [l, r] is bad. The answer is "DA" if getmin(l, r) <= r.
Complexity O(n + qklog(n)), where k<=7
Great. I'm so stupid that I used 2D data structures for the last part of the solution. Thank you so much for sharing your solution.
it would be GCD(x, y) != 1 iff there exists some prime number that divides both x and y. also, k <= 8
Yes, you are right, that should be GCD(x, y) != 1.
But k <= 7 as
2*3*5*7*11*13*17 = 510510 <= 1e6and2*3*5*7*11*13*17*19 > 1e6.Can you show me your code
How much does it take to post the tasks in the archive? I think I fixed my bug for Radio and I'm very eager to submit it.
How to solve Usmjeravanje(the last problem)?
Here is my solution:
The problem is essentially just directing the edges in a way to have the minimum possible number of total SCCs.
Let's say that we directed all the edges from left to right initially. Some edges won't have an impact on the compressed SCC graph. An example of this is if you have the edges "4 1" and "2 3". If you include the edge "4 1", you can notice that adding the edge "2 3" doesn't do anything since node 2 on the left side is already connected to node 3 on the right side. Let's call edges like "2 3" in this example with the term "useless" and all other edges "useful". There are many ways to find the useful edges but I used a segment tree RMQ to do it. After finding all the useful edges, I direct the useful edges from left to right and I direct the useless edges from right to left. After, you can just build the graph and run any SCC algorithm to count the number of SCCs.
The approach focusing on directing the edges from left to right is cool! thanks!
I was stuck on directing both directions simultaneously and failed to get any points :(
It's also possible to direct the edges without RMQ by using a simple greedy approach: Sort the edges decreasing by x and in case of equal x increasing by y. (call sort on (-x, y)). Now go through the edges in sorted order and maintain the minimum y seen so far (initially -inf). If y < minY, direct the edge right (from left to right), else direct it left.
The reason why this works can be explained by "useful" and "useless" edges as well: If y >= minY, we could move to the left and increase our x until we reach the edge leading to minY. So directing the edge right would be useless. Otherwise we can reach a lower y and the edge is useful.
Can someone help me optimize my solution for problem B?
Let's define a function f(x,y,z) = number of '#' inside the diamond with its top cell being (x,y) and its size being z. We can calculate this function using prefix on diagonals and some observations using triangles.
Then, I binary searched the length of the smallest correct diamond for each cell(x,y). There is at most one correct diamond for each cell so if it exists then I add 1 to the total answer.
Complexity: O(n*m*log(n)), I got TLE on the second sub-problem.
Here is a brief description of the solution to task Fliper.
Clearly, a necessary condition is that the length of each cycle is divisible by 8. It turns out that this is also sufficient.
We can figure out which obstacles belong to which cycles by going over the obstacles and finding the closest other obstacle in all four directions. Once we decompose the obstacles into cycles we do the following.
Create a graph where each node represents a cycle, and for each obstacle that belongs to different cycles add an edge between the corresponding nodes. There is also a dummy node for when the ball flies off to infinity and there might be self-loops in the graph. The problem can now be rephrased as: given a graph where each node has degree divisible by 8 (except maybe the dummy node), color the edges in 4 colors so that each node (except dummy) has an equal amount of each color.
To solve this we start an eulerian tour from the dummy node and color the edges alternately black and white. Then we run eulerian tours again separately on white and then again on black edges and color alternately again. Then we will have four colors appearing equally. The parity condition ensures things work out nicely.