PROBLEM LINK:
Editorialist: Soumik Sarkar
DIFFICULTY:
HARD
PREREQUISITES:
Graphs, Trees
PROBLEM:
Given the number of vertices N, generate a tree where there are exactly A distinguishable vertices. Two vertices a and b are indistinguishable if there exists a permutation of the vertices [p_1, p_2, p_3, ..., p_N] such that p_a = b, and for every pair of vertices (i, j), there is an edge between (i, j) if and only if there is an edge between (p_i, p_j).
EXPLANATION:
This problem can be solved case by case. In the graphs below all the vertices colored the same are indistinguishable from each other but distinguishable from the rest of the vertices.
Case A = 1
If N = 1 there will be no edges.
If N = 2 there will be one edge between the two vertices and both will be indistinguishable.
For any other N no solution exists.
Case A = 2
The graph will be a star graph. All the leaves will be indistinguishable and the internal node will be distinguishable from the leaves.
_2.png)
If N < 3 there is no solution.
Case A = 3
The main idea for this case is to make a symmetric graph as below, so that there are are exactly 3 groups of indistinguishable vertices.
When N is odd:
_2.png)
When N is even:
_2.png)
Minimum N required for this configuration is 5.
Case A < N
For this case we can make a path graph with A - 1 vertices, and then we can attach the remaining vertices to one end. The vertices in the path will be distinguishable from each other, and the vertices added later will be indistinguishable among themselves but distinguishable from the path vertices.
_2.png)
Again, minimum N required is 5.
Case A = N
As before, we can make a path graph with A-1 vertices, and then attach the last vertex asymmetrically to one vertex in the path, i.e any vertex except the first, second, last, second-last or center. All vertices will be distinguishable from each other.
_2.png)
If N < 7 there is no solution.
Complexity is \mathcal{O}(N) per test case.
ALTERNATIVE SOLUTION:
Feel free to share any alternative solution below.
EDITORIALIST’S SOLUTION:
Editorialist’s solution can be found here.