How should I practice Stable Workload Redistribution Trees?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Tower Research Capital online assessment problems in FastPrep.

Is Stable Workload Redistribution Trees associated with Tower Research Capital?

FastPrep tags this as a Tower Research Capital online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Stable Workload Redistribution Trees

Learn this problem

● Hard

Tower Research CapitalNEW GRADOA

Problem statement

You are given an integer array workloads of length n. Machine i is labeled i + 1 and initially holds workloads[i] units. The total workload is exactly n.

Choose a communication network that is a tree on the n labeled machines. After the tree is fixed, you may repeatedly choose two machines whose shortest-path distance in the tree is exactly 2 and move one workload unit from either chosen machine to the other.

A labeled tree is stable when some sequence of these moves leaves every machine with exactly one unit. Return the number of distinct stable labeled trees modulo 1000000007.

Function

countStableTrees(workloads: int[]) → int

Examples

Example 1

workloads = [1]return = 1

There is one labeled tree on one machine, and its workload is already one.

Example 2

workloads = [0,1,2]return = 1

The middle-workload machine must be alone on one side of the tree bipartition. This fixes the only stable tree: it is adjacent to both other machines.

Example 3

workloads = [0,0,2,2]return = 8

Each valid bipartition side contains one zero-workload and one two-workload machine. There are two unordered valid bipartitions, and each supports four labeled spanning trees.

Constraints

1 <= workloads.length <= 120; this length is n.
0 <= workloads[i] <= n.
The sum of all values in workloads is exactly n.