Hi everyone!
The fourth round of COCI will be held tomorrow, January 25th at 14:00 UTC. You can access the judging system here. If you are not familiar with the COCI contest format, we encourage you to read the announcement.
The round was prepared by fbabic, vito1036, cel.in, psruk, and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
Hi. The contest doesn't show up on evaluator.hsin.hr . Is this normal?
Thanks
Yes, it is normal. It will show up before the contest
Thanks
I still don't see the contest.
You can see it now
Registration opened late so we moved it up 15 minutes to allow everyone to register on time. The contest will start at 14:15 UTC.
how to do p5 T-T
The edges without cats on them form a tree with a cycle (there are n edges and any node can be reached from any other node). The edges with cats form a directed graph. You need to add some edges from the tree to the directed graph & orient them such that there is an eulerian cycle in it. The condition for a directed graph to have an eulerian cycle is for the indegree of each node to equal its' outdegree and for the graph to be connected when ignoring orientation (except for some isolated nodes).
First, remove one of the edges from the cycle so that the tree is actually a tree and solve separately for the 3 cases (omitting it, orienting u -> v, orienting v -> u). Then just process the tree in post DFS order (so, starting with the leaves) and decide what to do with the edge from this node to its' parent (if indegree == outdegree do nothing, if outdegree == indegree-1 add the edge u -> parent, etc). At the end check if the graph is connected and all the degrees match. Answer the minimum of the 3 cases.
Makes sense, thanks!
I noticed that for P4, the difference between a set and ordered set is the difference between 105 points and 120 points. So very weirdly an ordered set would be faster than a regular set in this case. Does someone know the reason for this.
Can anyone help me with P4? I just think that we should move the shoes into the hallway whenever you want, but when the hallway is full, I don't know what shoes should I remove. Thanks!
Unfortunately, the official solution for problem Cipele is wrong. Three people from the organization committee came up with the solution based on the same incorrect observation, and somehow it managed to go through. The incorrect observation we all had was: If the hallway is not full, we will put shoes in it. If the hallway is full we return the shoes that will be used latest.
This is the example that fails:
5 1 7
1 5 4 1 3 2 5
Here it is optimal to keep shoes with label 5 in the hallway instead of shoes with label 1. We have not found any other "greedy-like" observation that fixes this problem. If anybody thinks that the problem is solvable and has a solution for it, I would be glad to hear it.
I want to apologize in my name and the name of the whole organization committee for the inconvenience.
How to do p4? Is it:
Define vi as the amount of times the shoe will be removed from the stack(to take out other values) + the amount of values we will have to take out to take pair i in the end(at its next occurrence) now you want to keep putting shoes into the hallway and when the amount of shoes reaches m you want to remove the smallest vi (the cost of the shoe) and to maintain the vi (one vi can influence another vj) you can use a segment tree (each value can be represented by an interval of time and it’s cost is going to be the number of intervals covered by i)
Does anyone know how to solve subtask 1 (n <= 20, m <= 20) of problem 5?
Hi, the model solution is relatively simple for this subtask. Try all subsets of N roads and add them to the directed graph which already has M edges. Afterwards, check if there exists an eulerian cycle in the newly formed graph. At the end print the minimal size of the subset which formed an eulerian cycle.