PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Let us consider a multigraph with N vertices and M edges, where each vertex corresponds to a dish, and each edge corresponds to a patron, connecting the vertices corresponding to that patron’s preferred dishes. For Chef to be able to sell K tickets, it means that for any set of k ? K edges, the number of vertices touched by these edges is not less than the number of edges. Our task, then, is to find the smallest set of edges such that the number of vertices touched is less than the number of edges. The answer will be one less than the number of edges in this set.
What might such a set of edges look like? Let E be the number of edges and V the number of vertices. Because this is a minimal set, we must have E = V+1, otherwise we could simply remove an edge and have a smaller set satisfying the constraint. Also, there cannot be any vertices with degree 1, since the edge it touches could be removed as well. Since the sum of the degrees of all vertices is equal to twice the number of edges, there are only 2 possibilities: either 2 vertices have degree 3 and the rest have degree 2, or 1 vertex has degree 4 and the rest have degree 2.
We thus have only 3 possible structures for this graph formed by these edges:
-
Two vertices with degree 3, with 3 distinct paths between them.
-
Two vertices with degree 3, with 1 path between them and each attached to a cycle.
-
Two cycles that meet at a single vertex.
Each of these types of graphs can be searched for independently. The answer will be one less than the size of the smallest graph found.
Type 1 graphs: We can find such graphs by doing something similar to a single-source-shortest-path algorithm from each vertex, only we find the 3 shortest paths to each vertex. It doesn’t matter if the paths aren’t distinct, so long as each individual path doesn’t visit the same node twice.
Type 2 graphs: We begin by finding the shortest cycle through each vertex. Then for each pair of vertices, we make sure they don’t belong to the same shortest cycle, and take the lengths of the cycles plus the length of the shortest path between the two vertices as our graph size. It again doesn’t matter if paths aren’t distinct, as that simply implies the existence of a smaller graph.
Type 3 graphs: Here we again use a modified single-source-shortest-path algorithm from each vertex to find the 2 shortest cycles through a given vertex. Once again it doesn’t matter if these cycles aren’t distinct, so long as individually they don’t visit the same vertex twice.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.