Yesterday, I and my team (Nem_HCNU_Peno) did a gym contest on Codeforces, the 2011 Stanford Local Programming Contest. The problems are quite hard, and until the end of the contest we only managed to solve 5 problems.
I only coded a solution for problem C - City Driving.
A brief description about the problem is:
Given an undirected graph with $N$ nodes and $N$ edges. It is possible to go from any node to any other node. We are also given $Q$ queries: what is the minimum distance to go from node $u$ to $v$.
The complete problemset can be accessed here.
From the description of the problem we can know that the graph will contain exactly a cycle because the $N-1$ edges will become the tree, and one additional edge will make a cycle.
At first I only thought of solving it using a normal approach (like using Dijkstra) because the time limit is 10s. But I didn’t code it right away. I asked Soko and he said that the problem was like the contest on Hackerrank before (Hourrank 9) and he told me about the solution he had:
We will have two disjoint-sets union data structure (or simply DSU or union-find-disjoint-set UFDS), $ds1$ and $ds2$. So we will construct two trees based on the given graph. Each of the DSU will have a tree associated with the graph. Initially we will add the edges one-by-one from the graph to the first DSU as long as it is not forming a cycle. If there is an edge that will make a cycle, we add the edge to the second DSU instead. After that we do the same for the second DSU, so after that we will have two trees.
Then we apply Lowest Common Ancestor (LCA) algorithm for each of the tree. I use the $O(N \log N)$ algorithm for preprocessing and $O(\log N)$ per query. More explanation about the LCA algorithm can be accessed here.
After I coded it and submitted it, we got Wrong Answer.
After some discussion with Ammar about the solution, he made a test case that will make our solution fail. After that I changed my code again to handle the case. It was quite tricky to code, though.
The case that makes my previous solution wrong is that there is a cycle in the center of the graph, and the query is about from a node of the cycle to another node that is accross the previous node. If we randomly choose an edge to be removed (i.e. to be added to the second UFDS), it may have the same “shortest path” for both UFDS.
So to change the solution, I have to recode it again, modifying a lot of functions. Fortunately I can still keep my UFDS and LCA, but by adding some functions to find from a node to its root where the root is a node in the cycle.
The idea is like this:
- First, determine the cycle and the nodes that are in the cycle in $O(N)$. We can also do some precomputation to know the distance between any two nodes in the cycle
- From each of the node in the cycle, build a rooted tree (and UFDS but this is optional, but can help to make the solution easier)
- Preprocess the LCA of the trees
- After that, for each query, there are 2 kinds of possibilities:
- if node $u$ and $v$ is in the same tree, then we can use LCA’s query algorithm for both of them
- otherwise, we find from each node the total cost to go to the roots (i.e. the distance from current node to its root), then we sum up the total cost we have from both of them and the distance between those roots
Finally we got Accepted for that problem. The code can be accessed here «Source Code».