CHEFPASS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

EASY MEDIUM

PREREQUISITES

Graph Theory, Euler Circuit, Connected Components, Union Find

PROBLEM

You 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 EXPLANATION

The 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.

Explanation

Let each character in the set {a ... z} U {A ... Z} represent vertices of a graph. Each substring will then be an edge on this graph. You have to use all edges in A and some edges from B to create one or more Eulerian circuits.

The necessary and sufficient condition for a graph (connected or not) to be decomposed into a set of Eulerian Circuits is that

all the vertex degrees should be even.

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 V - are used in a connencted sub-graph H of B.

Lemma: If there are even number of odd degree vertices in a connected sub-graph of B, then we can always pair the odd degree vertices such that they are connected by paths in H and none of the paths considered share an edge.

Proof:

  • Suppose we find a path from a vertex a in V to another vertex b in V. We now consider these vertices paired
  • The degree of a and b due to this path getting added will become even and the degree of all the other vertices on the path will be even (by virtue of the fact that we chose two edges incident on those vertices - since, we chose a simple path)
  • Now, let us find another similar path from vertex c in V to another vertex d in V.
    • If the path does not share an edge with the previous path, then we have paired c and d.
    • If the path does share an edge, then we can take the symmetric difference of the paths and obtain two new paths that do not share an edge.
    • These paths connect c to a (or b) and d to b (or a).

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 V (that are in the connected sub graph H)

The problem can be solved by finding the connected components of B and enumerating the number of odd degree vertices in each one of them from A. If each connected component of B has an even number of vertices from A, then we can decompose the chosen edges as such to get Eulerian Circuits that use all vertices in A and zero or more vertices from B.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

2 Likes