Internet Problem Solving Contest

IPSC 2005

Solution to Problem F – Find The Right Words

This task belonged to the harder ones. At first we make a complete weighted bipartite graph. Its first partition consists of the letters chosen by one player. The second partition consists of words from the wordlist which contain the 2 letters chosen at the beginning of the game. The weight of an edge between a letter c and a word w is |M|+1-|w| (where M is the longest word and |w| denotes the length of the word w) if w contains c and 0 otherwise. Then we find a perfect matching in this graph with maximum weight. A matching in a graph is a set of pairwise disjoint edges. A perfect matching is a matching which contains all vertices of one (the smaller) partition. The weight of a matching is the sum of weights of its edges. We will find a perfect matching with maximum possible weight. It is clear that the words in the maximum matching are different, contain all the characters and the sum of their lengths is minimal because otherwise the matching formed by the words with smaller sum of lengths would have higher weight. If any of the characters is matched with a word with an edge with weight 0 then there exists no solution to the task and we will output -1.

So it is enough to solve the maximum perfect matching problem for weighted complete bipartite graphs. Let the partitions have sizes N1 and N2 respectively (N1<=N2). We will show an O((N1+N2)4)$ algorithm. Note that there are more efficient algorithms known, but this one was already fast enough.

The term size of a matching will denote the number of edges in it. The optimal matching of size k (Mk) is a matching whose weight is minimal over all possible matchings of size k. We will find optimal matchings of sizes 0, 1, ... , N1. M0 is clearly an empty set and MN1 is the answer to our problem. We assume that we have found Mk and we find now Mk+1.

Let's make some definitions first. Let's have a matching M. Matched edge (vertex) with respect to M is an edge (vertex) in M. An alternating path is a path whose starts at an unmatched vertex in one partition and ends at an unmatched vertex in the second partition and the edges along it alternate between unmatched and matched, that is the first edge along the path is unmatched, the second is matched, the third is unmatched and so on. Let PM denote the unmatched edges and QM the matched edges in M of some path P. The cost of P (cost(P)) is the sum of the weights of the edges in PM minus the sum of the weights of the edges in QM. cost(P)=wt(PM)-wt(QM). By augmenting a matching with an alternating path P we will denote the "flipping" of the edges in path P - that is every matched edge in P will become unmatched and vice versa. An augmenting path is an alternating path which will increase the weight of the matching by augmenting the matching with this path.

Let's go back to the problem of finding Mk+1 from Mk. We find the augmenting path P with the largest cost. Then we augment Mk with P to obtain Mk+1. By definition of cost(P) it follows that wt(Mk+1)=wt(Mk)+cost(P). It is easy to prove that Mk+1 is indeed the maximum matching of size k+1. So we have to find the augmenting path with maximum cost. One possible way to do it is to collapse all unmatched vertices into two new vertices UL and UR. Then we direct all matched edges from left to right retaining their weights and direct all unmatched edges from right to left and assign them their negative weight. Than we will find the shortest path between UL and UR and it is clear that this path will be the augmenting path with the largest cost. The resulting graph will have no cycles so we can do it by Bellman-Ford algorithm in O(NM) which results to an algorithm in O(N2M).

The second aproach which is used in the example solution works as follows: We will do it in k iterations. In the i-th (0<=i<=k) iteration we will find for every vertex wr in one of the partitions an augmenting path with largest cost to some unmatched vertex in the second partition considering only paths of length 2i+1 and shorter. Let's call it ci(wr). The length of any augmenting path can't be longer than 2k+1. The 0-th iteration is easy. For every vertex wr in one of the partitions we will find its unmatched neighbour connected with an edge with maximum weight. The i-th iteration works as follows: We check for every wr whether there exists matched ws in the same partition such that: ci-1(ws)+wt(wr,mate(ws))-wt(ws,mate(ws)) > ci-1(wr) (mate(ws) denotes the matched neighbour of vertex ws), i.e. there is more expensive alternating path to wr that comes directly from ws via mate(ws) - if so, we update ci(wr) accordingly. Then we will choose such unmatched wr whose augmenting path has largest cost. Every iteration runs in O(N2), there are at most N iterations for every Mk and 0<=k<=N so our algorithm runs in O(N4).