Bead Ornaments algorithm

Question

I have been trying to understand this question from some time. Can someone help in understanding this question?

===============================================================================

There are N colors of beads. You have bi beads of the ith color. You want to make an ornament by joining all the beads together. You create the ornament by using the following algorithm:

Step #1 Arrange all the beads in any order such that beads of the same color are placed together.

Step #2 The ornament initially consists of only the first bead from the arrangement.

Step #3 For each subsequent bead in order, join it to a bead of the same color in the ornament. If there is no bead of the same color, it can be joined to any bead in the ornament.

All beads are distinct, even if they have the same color. How many different ornaments can be formed by following the above algorithm? Two ornaments are considered different if two beads are joined by a thread in one configuration, but not in the other.

Update/clarification

Think of the bead formation as a tree and not as a straight line. Any number of beads can be connected to a bead.

Input:

The first line contains the number of test cases T. T test cases follow. Each test case contains N on the first line - the number of colors of beads. The next line contains N integers, where the ith integer bi denotes the number of beads of the ith color.

Output:

Output T lines, one for each test case. All answers should be output modulo 1000000007.

Constraints:

1 <= T <= 20

1 <= N <= 10

1 <= bi <= 30

Sample Input:

5 2 2 1 2 2 2 1 4 2 3 1 5 1 1 1 1 1 Sample Output:

2 4 16 9 125 Explanation:

For the first case: Let us label the beads A1,A2 and B1. Initially, they can be arranged in 4 ways - “A1,A2,B1”, “A2,A1,B1”, “B1,A1,A2”, and “B1,A2,A1”.

For each of the first two arrangements, an ornament can be formed in 2 ways (A1-A2-B1 or B1-A1-A2 from the first one and A2-A1-B1 or B1-A2-A1 from the second one).

For each of the last two arrangements, an ornament can be formed in 1 way.

However, of the total 6 possible ornaments, there are only 2 unique ones : A1 - A2 - B1, and A2 - A1 - B1.

For the second test-case: The possible unique ornaments are A1 - A2 - B1 - B2, A1 - A2 - B2 - B1, A2 - A1 - B1 - B2, and A2 - A1 - B2 - B1.

For the third test-case, it might be easier to see there are only 2 types of graphs on 4 vertices: the path or the star. It’s not hard to see that there are 12 paths and 4 stars (explanation courtesy: zlangley)

For the fifth test-case, there are a lot of people who claim the total number of possible ways is 5!/2 = 60 and how the answer is 125. Well, again, you’ve to think of it as a tree. This means one possible arrangement could be. Think A as a root node and have two edges (A-B and A-C). Now, think of B as a sub-root node with two edges (B-D and B-E). This is a possible bead formation.

=================================================================================

PS: The contest i got this question from is now over and i just want to understand the question. (https://www.hackerrank.com/challenges/beadornaments)

Answer 1

Let me try to rephrase the question: modulo a given large prime, how many unrooted trees are there involving n pairwise distinct nodes (beads), subject to the constraint that, for each part of a given partition (coloring) of the nodes, the subgraph induced by those nodes is connected (i.e., it's a tree)?

Such a tree is comprised of intra-color and inter-color edges. The choice of the former, moreover, does not affect the set of valid choices of the latter, and vice versa. The choices for the intra-color edges in turn are independent for each color. For a color with k nodes, the number of possibilities is k^(k-2) by Cayley's formula. Multiply these together.

To determine the number of possibilities for the inter-color edges, use Kirchhoff's matrix tree theorem to count the number of spanning trees of a graph where each color is a node and where there are k1*k2 edges between a color with k1 beads and another color with k2, i.e., the number of spanning trees in the complete graph on beads with each color contracted. Since the answer is computed modulo a large prime, the determinant calculation can be accomplished via, e.g., Gaussian elimination, for an algorithm that is strongly polynomial-time.