PROBLEM LINKSDIFFICULTYHARD PREREQUISITESGraph Theory, Matching, Maximum Flow PROBLEMYou are given two strings A and B. Imagine a language which consists of An Article is a collection of Sentences. A Sentence consists of A words, such that
Find the longest Article (most number of sentences) that can be achieved and print it. EXPLANATIONOf course A ≤ B to be able to build any sentence. The problem must be broken into two pieces
First InsightIf there are at least K sentences in the longest Article, then the following network has flow
It is intuitive that in such a network, the number of times each character in A is used is K and the number of times each character of B is used is less than or equal to K. CorollaryIf the maximum flow in the above network is Let us denote the flow between two vertices u and v as F(u, v). Now we know that if the maximum flow is
Let us generate a bipartite graph G(A,B) such that the number of edges between a in A and b in B is equal to F(a,b). We wish to partition the edges in G(A,B) into K matchings of size A each. If this is possible, then we have K proper sentences. The mapping between a matching and the sentence is easy to see. On G(A,B) we can use the following algorithm to generate the matchings (we will prove why). max_degree = K repeat K times 1. Let B' be the set of vertices in B whose degree is max_degree 2. build a matching of size A which contains all vertices in A contains all vertices in B' 3. remove all the edges in the matching from the graph 4. max_degree Step 2 in the above algorithm is actually always possible. Let us see why (Material for the proofs below has been derived from the book Graphs: Theory and Algorithms by K. Thulasiraman, M. N. S. Swamy) Lemma: In G(A,B), you can always build a matching of size A
Now, by Hall's Marriage Theorem we know that there should always be a matching that saturates A. Lemma: In G(A,B), you can always build a matching that contains all vertices in A and contains all vertices in B' From the previous lemma, we can get two matchings M_{1} and M_{2} that saturate A and saturate B' respectively. Both are built independently and may or may not have edges in common.
A path from b may only end at a vertex in X  B'. Can you see why? Hint
Now,
This process for each vertex b in B'  B converts M_{1} into a matching that saturates A as well as B'. Thus, we will have a solution by repeatedly finding this matching  and removing the edges. Le ImplementationYou can calculate the value of K by performing a binary search on the value of K. Build the graph for each sample of K and then test whether a flow of size For rebuilding the sentences we can use the discussion to derive a matching that saturates A as well as B'. This will bound the complexity of our implementation by What if we collect similar sentences together? We will have to choose the smallest F(u,v) for each edge (u,v) in the matching. Also, we will have to find the smallest delta through which we can go before a new vertex must be added to B'. The smaller one of both the value is the number of sentences that can be built by this matching. After deleting the edges in the matching, we may have to run augmentations to rebuild the matchings that saturate A and B' (and hence find the matching that saturates both A and B').
An augmentation takes at most EXERCISETry to find alternate ways of constructing a matching that saturates all the maximum degree vertices. A very interesting way using flows is possible by using presinks. Using the Dinic's algorithm, the matching can be found quickly. Also using collection trick described above works like an alternate solution. Hint
SETTER'S SOLUTIONCan be found here. ( Link is broken. Will upload the file on this address shortly. ) TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 13 Mar '13, 00:07

My solution is almost identical to what was presented in the editorial (in concept, at least). Just one observation. In the first part (where the flow is binary searched), a standard flow algorithm run from scratch each time is indeed too slow. However, what I did is the following: every time I got a positive answer for a flow value F (during the binary search), I copied the flow values of the graph edges. Then, when I tested whether a value F'>F is achievable, I started the maxflow algorithm from the flow values of the previous good value F (and not all the way from zero). Then I used just one of the standard maxflow algorithms with the following enhancement:
However, for me, generating the bipartite matchings in time (i.e. solving the second part of the problem) was more difficult. Generating each matching from scratch was too slow in my solution. So, in the end, I used a standard maxflow algorithm for finding each matching, enhanced with;
answered 13 Mar '13, 01:36

"It is worth noting that the constraint on the output size (less than 30000) blocks is superflous" Had i believed this, I would have solved this sum :( . Implemented everything as discussed. When submitted i got WA, and I felt it was because of that 30000 factor which probably m missing. So some other bug caused me WA. answered 13 Mar '13, 00:28

A quick question, should those B  B' and B'  B be X  B' and B'  X ? answered 15 Mar '13, 03:20
