Link to the problem on UVa Online Judge
In this problem you must think more than you have to code, you must reason.
First of all if you think of candidates as nodes of a graph, then you'll understand that we are facing a tournament graph (A directed graph in which between any two vertices there is exactly one edge in one direction).
First we have to build the graph in O(n^2 * m), how do we build the graph? For any two candidates if we know voter j prefers which one in O(1) then we can build the graph in the desired order. After we read a voter's preference list we must save candidate i is the k-th person in this voter's list. Then for any two candidates and a voter we will understand the one who he prefers.
After building the graph we must think of different situations, situations that a candidate is winner. The simplest situation that may come to mind is a cycle. In a cycle every node can be a winner. If you look closer each node of a Strongly Connected Component can be a winner. What's the relation between two SCC's? If edges are from SCC A to SCC B, then each node of SCC A can be a winner if no other SCC has edges to SCC A. So we must put these SCC's in topological order and anyone in the first SCC can be a winner.
So the desired candidate can be the winner if he is in the first SCC in the topological order.
Another solution to this problem comes from a similar reasoning and that is : if you have a path to any other node then you can be the winner. Think of this situation and try to understand that if you have a path to a node then you can win any person on this node, especially the last node on this path.
How do you know if you have a path to all the other nodes? You simply use DFS(desiredCandidate), and if all the other nodes are marked as seen, then you have a path to all the other nodes.
In this problem you must think more than you have to code, you must reason.
First of all if you think of candidates as nodes of a graph, then you'll understand that we are facing a tournament graph (A directed graph in which between any two vertices there is exactly one edge in one direction).
First we have to build the graph in O(n^2 * m), how do we build the graph? For any two candidates if we know voter j prefers which one in O(1) then we can build the graph in the desired order. After we read a voter's preference list we must save candidate i is the k-th person in this voter's list. Then for any two candidates and a voter we will understand the one who he prefers.
After building the graph we must think of different situations, situations that a candidate is winner. The simplest situation that may come to mind is a cycle. In a cycle every node can be a winner. If you look closer each node of a Strongly Connected Component can be a winner. What's the relation between two SCC's? If edges are from SCC A to SCC B, then each node of SCC A can be a winner if no other SCC has edges to SCC A. So we must put these SCC's in topological order and anyone in the first SCC can be a winner.
So the desired candidate can be the winner if he is in the first SCC in the topological order.
Another solution to this problem comes from a similar reasoning and that is : if you have a path to any other node then you can be the winner. Think of this situation and try to understand that if you have a path to a node then you can win any person on this node, especially the last node on this path.
How do you know if you have a path to all the other nodes? You simply use DFS(desiredCandidate), and if all the other nodes are marked as seen, then you have a path to all the other nodes.
No comments:
Post a Comment