Hi everyone!
The third round of COCI will be held on January 14th 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 dorijanlendvaj, ppavic, jklepec, psruk, mkisic, mlicul and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you and good luck!
Reminder: the contest starts in one hour.
Nice problems! May anyone please explain how to solve Skrivaca?
Let $$$d[i]$$$ be the answer if starting vertex is $$$i$$$.
After that, run Dijkstra.
The only tricky part is 3rd one, which (I think) is solvable with block-cut tree.
UPD: Yes, block-cut tree worked.
small note: you don't need the second part, it would happen in the Dijkstra/bfs anyway
I solved the third part with the low function, after that you don't need to divide into biconnected components
Nice, thanks!
Where can I upsolve the problems? I want to submit some code for task Skrivaca.
You can now upsolve the problems, you can find them under the "Tasks" tab, in the folder "HONI", and then you can select the year and the round.
May someone explain how to get full credit on Bamboni? Getting more than half credit with $$$n^2k$$$ dp was pretty trivial... Is there some number theory optimization I missed?
Only the divisors of k are important and they are quite less.
You can solve it in a similar manner as the n^2 * k solution by dp(i, j, div) = the number of paths that end in cell (i, j) and gcd(path_product, k) = div. Notice that div is a divisor of k so the complexity narrows down to n^2 * max_number_of_divisors which should pass. The rest should be easy, but I can develop it further if you think it's needed. The answer is obviously dp(n, n, k).
wow tysm!! I had a slight feeling that only the factors of $$$k$$$ are important but ultimately couldn't prove it in contest :(
what's the idea for Baltazar?
The first observation is that if you want to increase the length of the shortest path in the graph by modifying exactly one edge you need to increase an edge that appears in all the shortest paths, so possible candidates for the solution are all edges that appear in all the shortest paths of the graph. You can check if an edge appears in all shortest paths by running Dijkstra 2 times from nodes 1 and N and also keeping track of the number of shortest paths from the source to some node, not just their length. This number can be very big, so you can keep it modulo some big prime number(for safety and avoiding collisions, you can use more modulo values; I used 4 but I don't know how many are necessary). Now you can check whether an edge appears in all shortest paths by some product of counts(computed with Dijkstra from 1 and N) in its endpoints and comparing that to the number of shortest paths also computed with Dijkstra.
Further, it's obvious that after you increase an edge of the shortest paths by 2, its new length will also increase by 2, not by 1, so the graph needs to initially have at least one path of length shortest_path + 1. If this is not the case, there is no solution and you print 0 and new line. After that, for all possible edge candidates you need to check if they lie in all paths of length shortest_path + 1. If so, you can not increase that edge, because after that you will no longer have a path of length shortest_path + 1 in the graph. Now this part seems similar to the first part computed with Dijkstra, but how exactly can you do that? Well my approach was to compute dp[node][0 / 1] and cnt[node][0 / 1] = the length and number of shortest paths from source to node such that their length % 2 == 0 / 1. You can do that with Dijkstra as I said earlier. In our problem it is required that the second shortest path of the graph is one unit longer than the shortest one, so it will have a different parity and be the smallest path with this property, so we can extract informations about it from dp and cnt tables(one of them will corespond to the shortest path and the other one to the second shortest). After that you use this tables to solve the problem as I described. Don't forget to compute cnt modulo something and use more modulo values for safety.
Could you share some peices of code ? I got the main idea but unable to understand how to make the computations in order to check if an edge lies in all shortest/shortest+1 paths
This is my code: https://pastebin.com/S83YBAVF. It may not be the best implementation, but I hope it is ok.
How to solve 3rd subtask in Dirigent?
keep track of how many adjacent elements are ordered
Can you explain it little further?
Consider an easier version of the problem: given an array, determine if it is sorted after swapping two elements. You can count how many adjacent elements are ordered ($$$a_i < a_{i + 1}$$$). The array is sorted iff this value is $$$n - 1$$$. After swapping two elements at most 4 such pairs will change, so it is easy to update the value. Now, for the original problem the logic is the same, but since we don't know where our array "starts" we also take the pair $$$(a_n, a_1)$$$ into account.
While swapping values in the original array, maintain additionally: 1) an array with the indices of all the elements, and 2) a set of "bad" indices — all those that don't have a proper (x+1 modulo n) value next to it (i+1 modulo n).
See my code implementing that idea.
Thank you, I am so sad I didn't think of that during the contest.