dumbhead's blog

By dumbhead, 7 years ago, In English

I was trying this problem HOLI but I am not able to come up with a good solution. I was thinking of pairing up the leaf nodes of the longest path in the tree. After pairing up, I remove the two paired nodes and continue with the next longest path. But this would give a O(n^2) approach resulting TLE. Can somebody tell me an efficient approach for the solving problem ? I would be happy if somebody helps me in this. Thank you in advance.

Tags dfs
 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

The idea is the following:

Let's take a look at one edge of the tree. If this edge is removed, there are two sub-trees instead of the initial tree. Let's assume that one of these sub-trees contains x vertices. Then there're exactly y = n — x vertices in another sub-tree. There're at most 2 * min(x, y) paths going through this edge. So all we need to know is how many vertices there are in each of two sub-trees if this edge is removed. (For edge i, let it be x[i] and y[i]) It's clear that the answer is the sum for all edges: 2 * min(x[i], y[i]) * weight[i] (weight[i] — weight of the i-th edge).

There's only one thing left to do to solve the problem: calculate x[i] and y[i] for all edges quickly. It can be done with simple sub-tree dp(we need to know the number of vertices in a sub-tree). This solution works in O(N) and it's pretty simple to implement. Here's my code.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you for the reply. Can you please explain how did you get that there're at most 2 * min(x, y) paths going through an edge ? I am not getting this part.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Let's assume that for i-th edge x[i] > y[i]. If more than y[i] paths go through this edge, there'll be y[i] houses for people to stay in and more than y[i] people. So they will have to share a house.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes, I got it. The problem really simplifies a lot after this deduction which is not trivial. Got it accepted with this approach. Thanks a lot for the help.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      pigeonhole principle

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey wanted to know how u came up with the idea

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am unable to understand two things- 1.purpose of cnt array 2. what are we achieving using min(cnt[to],n-cnt[to])*2*w[v][i]

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It may be a silly doubt but are we sure doing c = 2 * (x, n — x) * weight will give max? Will we always find a configuration as I m thinking what if due to max contribution c of some edge, max contribution of some other edge may reduce.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This approach is based on pigeon hole principle.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What he is asking is how to prove there always exists a configuration (or pairing) in which every edge gets traversed exactly $$$2 \cdot \min(x, n - x)$$$ times.
      Does someone have a nice proof for this?

»
5 weeks ago, # |
Rev. 5   Vote: I like it -10 Vote: I do not like it

http://zobayer.blogspot.com/2014/01/spoj-holi.html

Got from above site contains awesome explanation w.r.t to pigeon hole principle --------------

Given a weighted tree, consider there are N people in N nodes. You have to rearrange these N people such that everyone is in a new node, and no node contains more than one people and maximizes the cost. Here cost is the distance travelled for each person.

First observation is, in order to maximize cost, all edges will be used to travel around. So, if we can calculate how many times each edge will be used, we can calculate the cost.


Now for any edge Ei, we can partition the whole tree into two subtrees, if one side has n nodes, the other side will have N — n nodes. Also, note that, min(n, N-n) people will be crossing the edge from each side. Because if more people cross the edge, then by pigeon-hole principle in one side, we will get more people than available node which is not allowed in the problem statement. So, Ei will be used a total of 2 * min(n, N-n) times.
Thus the final result is:``
cost = ∑ 2*min(ni, N-ni)*wieght(Ei) | for each edge Ei
Here, ni is the count for nodes in one side of the edge Ei and N-ni on the other side. So, we can use simple DFS algorithm to solve the problem. During the traversal, just count number of nodes in the subtree for an edge u⇒v and calculate result for each edge in the process.
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it
    But I am getting WA on SPOJ
    HOLI — Holiday Accommodation
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long int ll;
    // constraints 
    // T (1 ≤ T ≤ 10)
    //  N (2 ≤ N ≤ 105)
    //  X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 106), 
    class Graph{
    
        int V;
        list<pair<ll,ll>> *adj;
    public:
        Graph(int V)
        {
            this->V=V;
            adj=new list<pair<ll,ll>>[V+1];
        }
    
        void addEdge(ll u,ll v,ll wt)
        {
            adj[u].push_back({v,wt});
            adj[v].push_back({u,wt});
        }
    
        void print_count(ll*count)
        {
            for(ll i=1;i<=V;i++)
            {
                cout<<count[i]<<" ";
            }
    
            cout<<"\n";
        }
    
        int dfs_helper(ll node,bool *vis,ll *count, ll &cost)
        {
           // cout<<"node: "<<node<<" "<<cost<<"\n";
            vis[node]=true;
            count[node]=1; 
            // count[i] contains: no of child nodes and nodes to which 
            //                    child nodes are connected and himself not parent
    
            // Base case: for leaf nodes for whom all nbr are already visited
            //            for them "for loop " won't run and we directly
            //             return  count[node](=1) like other nodes 
            //             but it will untouched and equal to 1 
    
            for(auto nbr_pair:adj[node])
            {
                ll nbr=nbr_pair.first;
                ll wt=nbr_pair.second;
    
                if(vis[nbr]==false)
                { 
                    //cout<<"node nbr: "<<node<<" "<<nbr<<"\n";
                    // for each nbr we have to increase count by nodes in that nbr
                    count[node]+=dfs_helper(nbr,vis,count,cost);
    
                    // after above step we traversed whole subtree of the nbr
                    // so we need to calculate cost for this node---nbr edge
    
                    // notice nodes_part1=count[nbr] not count[node]
                    ll nodes_part1=count[nbr];
                    ll nodes_part2=V-nodes_part1;
    
                    ll contribute=2*min(nodes_part1,nodes_part2)*wt;
    
                    cost+=contribute;
                   // cout<<"contri: "<<contribute<<"\n";
                   // cout<<"nbr cost: "<<nbr<<" "<<cost<<"\n";
                }
            }
    
          //  print_count(count);
            return count[node];
        }
        
        void print()
        {
            for(int i=1;i<=V;i++)
            {
                cout<<i<<"=> ";
                for(auto nbr_pair:adj[i])
                {
                    cout<<"("<<nbr_pair.first<<","<<nbr_pair.second<<") ";
                }
                
                cout<<"\n";
            }
        }
    
        ll dfs()
        {
            bool *vis=new bool[V+1];
            ll *count=new ll[V+1]; //count of no. times the edge is travelled
            
            for(ll i=1;i<=V;i++)
            {
                vis[i]=false; // mark all node unvisited
                count[i]=0;
            }
    
         //   print();
            // mark all count as 1 
    
            // now their are V-1 edges and we need to update cost V-1 times
            // so we do dfs for edges but with help of vertices not edges 
            // ie instead of visiting edges we visit vertices 
            // and say a vertex is connected to 4 vertices ie one vertex has 4 edges
            // so we update cost on that vertex 4 times, eg as follows
            //         4
            //         |
            //    1----2-----3
            //         |
            //         5    
    
            // no for loop is required in dfs() bcz its a tree so one 
            // dfs call will be enough to traverse whole component in one go
    
            ll src=1; // acc. to constraints in question
                        // 1<=X<=N
            ll cost=0;
            dfs_helper(src,vis,count,cost);
            
            return cost;
           
        }
        
    };
    
    
    int main()
    {
        int t=1,T; cin>>T;
    
        while(t<=T)
        {
            int u,v,wt,V; cin>>V;
    
            // create a graph
           
            Graph g(V);
            pair<int,int>p;
    
            for(int i=0;i<V-1;i++)
            {
                cin>>u>>v>>wt;
                g.addEdge(u,v,wt);
              
            }
    
        // Maximize it distance travelled so for that
        // every edge has to be travelled at max using greedy backed by pigeon hole
        // so we do dfs and count cost
    
        int cost=g.dfs();
          
            cout<<"Case #"<<t<<": "<<cost<<"\n";
            t++;
        }
    }