MINBLOCK Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Shantanu Pathak
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1988

PREREQUISITES:

Trees

PROBLEM:

Given a network of N cities (numbered from 1 to N) and (N-1) roads arranged in a tree format with the root at city 1.
Each of the (N-1) roads is assigned a value of either 0 or 1.

  • If the value of a road is 0, it cannot be blocked by the government.
  • If the value of a road is 1, it may or may not be blocked depending on the decision of the government.

Initially, city numbered 1 is infected by a virus. The infection spreads from an infected to an uninfected city only if no road present on the shortest path between the cities is blocked.

The government wants to control the number of infected cities and has asked you to devise a plan. Determine the minimum number of roads (with value 1) you need to block such that the at most K cities are infected at the end.
If it is not possible that at most K cities are infected, print -1.

EXPLANATION:

The first thing we need to calculate is all the subtrees that can be saved if we blocked entry in it. One thing to note here is if we can block entry to a subtree, say subtree T, then we won’t consider the subtrees of T in our final count. We can use a DFS to calculate this.

Thus using DFS we will have an array A of our subtrees, where A[i] denote the strength of the i_{th} subtree, i.e the number of nodes in the i_{th} subtree.
Initially we assume that no road is blocked, so we have n infected cities.
Now sort the array A in descending order and reduce the infected cities by A[i] by blocking entry to the i_{th} subtree till the number of infected is greater than k.
If even after blocking all possible subtrees, the number of infected is greater than k, we give -1 as output, otherwise our final answer would be the number of subtrees that we blocked.

TIME COMPLEXITY:

O(NlogN), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

3 Likes
2

I followed a similar approach, first found the number of nodes in each subtree (including the root of subtree) and then I did bfs from node 1
If for edge (u, v) the road has 1 then i don’t push v in queue but store the number of nodes in subtree at node v. Else push node v in queue.
After that I calculated the answer with the vector.
But this failed the test cases.
Heres my code: CodeChef: Practical coding for everyone
Can someone give any testcases where this fails

3

Ya even I did the same and only the first five cases passed.

4 Likes
4

my test case 2 keeps failing, anyone got a clue where i could be going wrong.

Link to my submission : CodeChef: Practical coding for everyone

5

@adititiwari_02 it’s not failing for an undirected graph. I also tried using directed one but was failing last 5 tc.

1 Like
6

@suman_18733097 can you please give a failing test case for my approach!!

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod=(1e9+7);

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<vector<pair<int,int>> >G(n+1);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }
    if(k==n)
    {
        cout<<"0\n";
        return;
    }
    vector<int>del;
    vector<bool>ck(n+1,false);
    queue<int>q;
    q.push(1);
    ck[1]=false;
    while(!q.empty())
    {
        int k1=q.front();
        q.pop();
        for(int i=0;i<G[k1].size();i++)
        {
            if(G[k1][i].second==1&&!ck[G[k1][i].first])
            {
                int cnt=0;
                ck[G[k1][i].first]=true;
                queue<int>d;
                d.push(G[k1][i].first);
                while(!d.empty())
                {
                    cnt++;
                    int k2=d.front();
                    d.pop();
                    for(int i1=0;i1<G[k2].size();i1++)
                    {
                        if(!ck[G[k2][i1].first])
                        {
                            ck[G[k2][i1].first]=true;
                            d.push(G[k2][i1].first);
                        }
                    }
                }
                del.push_back(cnt);
                // calculate total nodes from here to all possible
            }
            else if(!ck[G[k1][i].first])
            {
                ck[G[k1][i].first]=true;
                q.push(G[k1][i].first);
            }
        }
    } 
    sort(del.begin(),del.end(),greater<int>());
    int ans1=0;
    int z2=n;
    for(int i=0;i<del.size();i++)
    {
        z2-=del[i];
        ans1++;
        if(z2<=k)
        {
            cout<<ans1<<"\n";
            return;
        }
    }
    cout<<"-1\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}
7

this obviously will fail .
u r making it directed for that the ancestor for some node will definitely change .
so make it undirected .

1 Like
8

@appu_23 Yes, the undirected graph constructed should be independent of ordering of the vertices given in input. Flipping a single edge in the directed graph could change which edges can and cannot be accessed.

9

I see, thank you! T-T

10

Can someone tell the testcase where my code fails?

#include <bits/stdc++.h>
#define int long long int

int count(std::vector <std::pair<int,int>> adj[], int root){
    int c = 0;
    std::queue <int> q;
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        while(n--){
            int t = q.front();
            q.pop();
            c += 1;
            for(auto i:adj[t])
                q.push(i.first);
        }
    }
    return c;
}

void dfs(std::vector <std::pair<int,int>> adj[], int root, std::priority_queue <int> &pq){
    if(adj[root].size() == 0)
        return;
    for(auto i:adj[root]){
        if(i.second == 1)
            pq.push(count(adj, i.first));
        else
            dfs(adj, i.first, pq);
    }
}

void solve(){
    int n, k;
    std::cin >> n >> k;
    std::vector <std::pair<int,int>> adj[n+1];
    for(int i=0; i<n-1; i++){
        int a, b, c;
        std::cin >> a >> b >> c;
        adj[a].push_back({b,c});
    }
    std::priority_queue <int> pq;
    dfs(adj, 1, pq);
    int c = 0, s = 0;
    while(!pq.empty()){
        s += pq.top();
        c += 1;
        if(n-s <= k){
            std::cout << c << "\n";
            return;
        }
        pq.pop();
        
    }
    std::cout << "-1\n";
}
     
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 0;
    std::cin >> t;
    while(t--){
        solve();
    }
}
11

same. You probably made the same mistake as I did. For each road you are supposed to add, you are given 2 values: u and v.

In the example test case and the first half test cases, u will always be a city that has been added to the tree before. In the last 5 test cases u may not exist in the tree, but v will.

This means you are most likely missing a check, if your tree contains v but not u, you want to swap u with v.

1 Like
12

Try this test case:

STDIN

1
7 3
1 2 1
1 3 1
1 4 0
3 5 1
1 6 1
6 7 1

Your Output

1

Expected Output

2

The Tree:
graph

Explanation:

  • Block the roads (1\rightarrow 3) and (1\rightarrow 6).
  • Now, the cities that are reachable are [1, 2, 4] whose count doesn’t exceed K = 3.

Check why your code is printing 1.

2 Likes
13

Thanks a Lot!!
I figured it out, and really your explanation was quite helpful.

1 Like
14

How O(n) ? sorting ‘n’ infected cities in descending order would itself require nlogn.

15

Consider this test:

STDIN

1
3 3
1 2 1
1 3 1

Expected Output

0

Your Output

1
16

Did you miss a return statement after line 135?

17

could anyone help me in finding what is going wrong? 4 passed, rest TLE
tried adjacency matrix, stored road information inside a[r][r] where r is the node that is connected by a parent with given road.
while traversing i m only storing the counts of cities for nodes that are connected by ‘1’ roads and only those that are encountered first in root node’s connections. this way we only track the maximum cities that can be cut out in every sub branch of root node.

#include<bits/stdc++.h>
using namespace std;

int trav(vector<vector<long long int>>&a,int r,vector<long long int>&con,int flag){
	//cout<<"node"<<r+1<<endl;
	long long int count=0,tm=-1;
	if(flag==0 && a[r][r]==1){tm=1;flag=1;}
	for(long long int j=0;j<a.size();j++){
		if(j==r)continue;
		if(a[r][j]==1 || a[r][j]==0){
			count+=trav(a,j,con,flag);
		}
	}
	//cout<<r+1<<" "<<count+1<<endl;
	if(tm==1){con.push_back(count+1);}
	return count+1;
}

int main(){
	
	int t;cin>>t;
	while(t--){
		long long int n,k;cin>>n>>k;
		vector<vector<long long int>>a(n,vector<long long int>(n,-1));
		vector<long long int>con;
		for(long long int i=0;i<n-1;i++){
			long long int d,b,c;cin>>d>>b>>c;
			a[b-1][b-1]=c;
			a[d-1][b-1]=c;
		}
		trav(a,0,con,0);
		//for(int i=0;i<n;i++)cout<<i+1<<" "<<con[i]<<endl;
		sort(con.rbegin(),con.rend());
		
		long long int cc=0,i=0,blocked=0;
		while(n-blocked>k){
			if(i>=con.size())break;
			blocked+=con[i];i++;
			cc++;	
		}
		if(n-blocked>k)cout<<"-1"<<endl;
		else cout<<cc<<endl;	
	}
	return 0;
}
18

Use Adjacency list instead of Adjacency matrix. It \text{TLEs} For large N.

19

Can anyone tell me on which test case will this code fail?

  1. Basically I have calculated the subtree size of all the nodes.
  2. Sorted according to size in descending order.
  3. Traversed through subtrees, and checked if they are blocked or visited,
  4. If not, then block the subtree and vis all the nodes in the subtree.
// Problem: Minimize Blocked Roads
// Contest: CodeChef - CodeChef Starters 39 Division 2 (Rated)
// URL: https://www.codechef.com/START39B/problems/MINBLOCK
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) v.begin(), v.end()
#define ll long long
#define see(x) cout << #x << "=" << x << endl;
#define tests int t; cin >> t

using namespace std;
 
bool comp2(const pair<int, int>&a, const pair<int, int>&b)
{
    if(a.second > b.second)
        return true;
    return false;
}

vector<int>adj[200005];
map<int, int>mp; // subtree size
map<int, int>p; // parent
map<pair<int, int>, int>weight;

void dfs(int node, int parent) {
	p[node] = parent;
	// see2(node, parent);
	mp[node] = 1;
	for(auto x: adj[node]) {
		if(x != parent) {
			dfs(x, node);
			mp[node] += mp[x];
		}
	}
}

int main()
{
	ios
	int t = 1;
	cin >> t;
	
	while(t--) {
		int n, k;
		cin >> n >> k;
		
		
		
		for(int i=0;i<n-1;i++) {
			int u, v, w;
			cin >> u >> v >> w;
			
			adj[u].pb(v);
			adj[v].pb(u);
			weight[{u, v}] = w;
		}
		
		dfs(1, 0);
		
		// for(auto x: mp) cout << x.se << "\n";
		// for(auto x: p) cout << x.fi << " " << x.se << "\n";
		
		vector<pair<int, int>>subtree; // sorted
		
		for(auto x: mp) {
			subtree.pb({x.fi, x.se});
		}
		
		sort(all(subtree), comp2);
		
		// cout << "sorted subtree: \n";
		// for(auto x: subtree) cout << x.fi << " " << x.se << "\n\n";

		int cnt = 0;
		int infected = n;
		
		// for(int i=1;i<=n;i++) if(dis[i]) infected++;
		// see(infected);
		
		int vis_subtree[n+1] = {0};
		for(auto x: subtree) {
			
			if(infected <= k) {
				break;
			}
			
			if(!vis_subtree[x.fi] && weight[{p[x.fi], x.fi}] != 0) {
				
				// see(x.fi);
				cnt++;
				infected -= x.se;
	
				stack<int>st;
				vis_subtree[x.fi] = 1;
				st.push(x.fi);
				
				while(!st.empty()) {
					int node = st.top();
					st.pop();
					
					for(auto next: adj[node]) {
						if(next != p[node]) {
							st.push(next);
							// see(next);
							vis_subtree[next] = 1;
						}
					}
				}	
			}
		}
		
		// see(infected);
		
		if(infected <= k)
			cout << cnt << "\n";
		else cout << -1 << "\n";
		
		
		
		mp.clear();
		p.clear();
		weight.clear();
		
		for(int i=0;i<n+1;i++) adj[i].clear();
		
	}
}```
20

Thank you :smile: