PROBLEM LINK:
Author: Devanshu Agarwal
Tester: Teja Vardhan Reddy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming, Graph Theory
PROBLEM:
This description of the problem is very brief. It’s highly recommended to read the problem statement to have a full understanding.
You have an undirected graph of N nodes and M edges. Each node has a value. V_i denotes the value of the i_{th} node. A family is a subset of X nodes connected by X-1 edges (a tree) and it’s rooted in the node with the highest value, and the value of each node is less than the value of its parent. The respect of a family is the value of its root.
Now consider breaking the current graph into K families and removing all unused edges (resulting subgraph is called a partition). For each possible partition, you need to sum the respects of all families in this individual partition (let’s denote this sum by partition power). Now for each possible i from 1 to N, you need to calculate the sum of partitions powers among all possible partitions that has i disconnected families.
N \leq 5000
M \leq 10^5
Explanation:
Let’s review our definitions.
A family is a rooted tree with the highest value node as a root. Each node is less in value than its parent.
A family’s respect is the the value of its root.
A partition is a decomposition of the graph into some number of families resulting from the removal of a subset of edges.
A partition power is the sum of its families’ respects.
For simplicity, I will use the term tree instead of the term family from now on.
First of all, consider that we are building some partition. Let’s build it node by node. The meaning is, let’s add nodes one by one. When handling a new node, we have 2 choices:
- make it the root of a new family
- connect it to some other node that is a neighbor in the original graph
I think this should have given you a hint to the approach. We will use Dynamic Programming.
Let’s denote by W[N][T] the number of ways of constructing a valid partition using the first N nodes such that this partition contains T trees (families). Fine, let’s write this recurrence according to the choices we mentioned.
W[N][T]\, = 0 initially.
W[N][T] = \, W[N][T] \, + W[N-1][T-1]
This is the first possibility, our currently handled node (N^{th} node acts as the T^{th} root).
W[N][T] = \, W[N][T] \, + W[N-1][T] \, * bigger
Here we are adding this node to some previous partition with already T trees. But notice that any partition of those would consist of the first processed N-1 nodes and for each one of them we can attach our new node to any node among those N-1 nodes which is a neighbor in the original graph and has a bigger value. So bigger here denotes the number of nodes among the first N-1 that are connected to the N^{th} node in the original graph and have a bigger value.
So wrapping all…
W[N][T] = \, W[N-1][T-1] \, + W[N-1][T] \, * bigger
Let’s put the last brick in our solution. Calculate the sum of powers for each N and T.
Let’s denote by S[N][T] the sum of powers of all possible partitions built from the first N nodes and having exactly T trees. When adding a new node, let’s think about how many new partitions we can form and add the value of each of them, and also observe the old partitions that we attach our node to and how much their value increased.
S[N][T]\, = 0 initially.
S[N][T] = \, S[N][T] \, + S[N-1][T-1] \, + W[N-1][T-1] * V_N
Considering the first choice, we would have W[N-1][T-1] new partitions (W[N-1][T-1] old ones and for each of them we add our node as a new root). Our new node’s value was added to the power of each of them.
S[N][T] = \, S[N][T] \, + S[N-1][T] \, * bigger
Considering attaching our node to some parent, the previous partitions’ powers would remain the same but we have different ways of attaching this new node.
Wrapping all…
S[N][T] = \, S[N-1][T-1] + W[N-1][T-1] * V_N \, + S[N-1][T] \, * bigger
The answer for a certain i would be S[N][i].
Complexity: O(N^2)