PROBLEM LINK:DIFFICULTYEASY MEDIUM PREREQUISITESGraph Theory, Euler Circuit, Connected Components, Union Find PROBLEMYou are given a set of two letter substrings that MUST be used A, and set of two letter substrings that CAN be used B. Choose some subset of B, lets call it B', such that the collection of two letter substrings A + B' span all the two letter substrings of a set of strings. A set of two letter substrings are said to span a string, if they represent all the two letter substrings of a string, after reversing some of the substrings. One must also consider the two letter substring formed by the first and the last character. QUICK EXPLANATIONThe problem description hints towards finding eulerian circuits in an undirected graph whose edges from the chosen set of substrings. One eulerian circuit will then refer to one string and you have to find if all strings in A and some strings from B represent a set of edges, such that, together they form one or more Eulerian Circuits and no substring remains unused. ExplanationLet each character in the set The necessary and sufficient condition for a graph (connected or not) to be decomposed into a set of Eulerian Circuits is that
From the edges in A, we will have an even number of vertices that have an odd degree  since, the sum of all vertex degrees in an undirected graph is always even. Let us assume some of these odd degree vertices  set Lemma: If there are even number of odd degree vertices in a connected subgraph of B, then we can always pair the odd degree vertices such that they are connected by paths in Proof:
Hence, repeating this process of pairing, we will either have paired all the vertices, or one vertex will remain because there were odd number of vertices in The problem can be solved by finding the connected components of SETTERS SOLUTIONCan be found here TESTERS SOLUTIONCan be found here
This question is marked "community wiki".
asked 20 Aug '12, 00:27
