Solution: Google Kickstart Round H 2022 | Problem C: Electricity
Problem Statement
Ben works as an engineer in a city with N electric junctions. These junctions form a network and can be visualized as a connected graph with N vertices and N−1 edges. The city is facing a power outage, due to which none of the junctions are receiving electricity, and Ben is in charge of handling the situation.
Each junction has a fixed electric capacity. Ai is the electric capacity of the i-th junction. Due to resource constraints, Ben can provide electricity to only one junction, but other junctions can receive electricity depending on their connections and capacities. If the
the i-th junction receives electricity, then it will also get transmitted to all the junctions directly connected to the i-th junction whose capacity is strictly less than Ai. Transmission stops if no eligible junction is present. Help Ben determine the maximum number of junctions that can receive electricity.
Samples
Explanation
In Sample Case 1, the optimal solution is to provide electricity to the fourth junction. This will transmit electricity to all the junctions eventually.
If the electricity is provided to the third junction, it will transmit it to the first and second junction, but not to the fourth junction. In that case, only three junctions can finally receive electricity.
In Sample Case 2, the optimal solution is to provide electricity to the third junction. This will transmit it to the first and second junctions. Note that electricity will not be transmitted to the fourth junction, since its capacity is not strictly less than that of the third junction.
If electricity is provided to the sixth junction, it will only be transmitted to the first junction.
If electricity is provided to the fourth junction, it will only be transmitted to the fifth junction.
Solution
In Simple Terms , we have been given a Tree connected graphs with nodes having some values assigned to it. And there exists a directed edge between nodes such that the edge is going from node having large value to node having small value.
Now we have to find the connected component having the maximum number of nodes .
To solve this question we will Find the answer for each Node i.e. the number of connected nodes in the current component and then we will choose the maximum answer.
For this we can use a for loop from i=1 to i=n , and for each i we can run a DFS call.
Since there are N nodes in the tree , each DFS call will take O(N) time , and we are calling DFS N-times , hence the time complexity will lead to O(N²).
Now what to do ? Can we Optimize our solution ?
Answer is Yes , We can see that there are multiple repeated calls which can be stored for further use. This observation gives us a hint to use Dynamic Programming.
(Note : Try a Dry Run on small directed tree on pen and paper , and you will see that for some Sub — calls you have already calculated answer in previous calls )
So We will Use memoization in Our DFS Calls.
Now the main Part comes , what should be the logic of our DFS Function ?
Let’s Consider the Below Tree .
Assume that we made a DFS call at 1. We will travel down to 4 and at 4 we will return 1. Means there is 1 node present in the subtree of 4 . Now same for Node 2 , we will return answers from subtree 4 plus 1 for Node 2 , meaning there are 2 Nodes present in the subtree of Node 2 .
Again if we see we will have 3 Nodes in the subtree of Node 3 ( Node 3 , Node 5 , Node 6).
For Node 1 , There are 2 nodes in Subtree 2 and 3 Nodes from subtree 3, and plus 1 for current Node , Hence there are 6 Node present in the subtree of Node 1
Let’s try to implement this logic into Code.
We will declare a dp array , where
Dp[ i ] → Number of Nodes in the Subtree of ith Node in the tree.
First we will initialize dp[i] with 1 for obvious reasons of the current node counted as 1 Node.
After that , we will traverse to all adjacent child nodes of the current node and add the answer from those nodes to our cur dp[i] .
And in the Last we will just return the dp[i], i.e. Answer of the current node.
Let’s see the code for more clear understanding.
Code
#include <bits/stdc++.h>
using namespace std;
int dfs(vector<int> adj[], int cur, vector<int> &dp )
{
if(dp[cur]!=0)
{
return dp[cur];
}
dp[cur] = 1;
for(int x : adj[cur])
{
dp[cur] += dfs(adj, x, dp);
}
return dp[cur];
}
int main()
{
int t;
cin >> t;
while(t — )
{
int n;
cin >> n;
vector<int> v(n + 1);
vector<int> adj[n + 1];
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n;i++)
{
cin >> v[i];
}
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
if (v[a] > v[b])
{
adj[a].push_back(b);
}
else if(v[a]<v[b])
{
adj[b].push_back(a);
}
}
int ans = 0;
for (int i = 1; i <= n;i++)
{
ans = max(ans, dfs(adj, i, dp));
}
cout << ans << endl;
}
return 0;
}
Time Complexity
Since We are Visiting Each Node at most once , hence the time complexity will be O(N).
Space Complexity
Since We are Using Extra space for the DP- vector , space Complexity will be O(N).
You can also Watch this solution LIVE on our YouTube now: https://youtu.be/YU9inXLHbww
Start your journey with Programming Pathshala.
Logon to www.programmingpathshala.com and take a free trial NOW!
