DRGHTS-Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

Depth first traversal

PROBLEM:

Given a forest with N nodes, where each nodes is labeled with one of the two labels {0, 1}, find

  1. how many pair of label ‘1’ nodes exist which are connected by a path.
  2. how many nodes w are there in the forest which lie on the path between two label ‘1’ nodes.

QUICK EXPLANATION:

Split the forest into trees and for each tree compute both results (1) and (2). The answer for the forest would be the sum of results of individual trees.

In a tree all nodes are connected with one another, hence (1) is equivalent to find how many label ‘1’ nodes exist in the tree. For (2) one needs to perform a depth-first traversal to compute the number of label ‘1’ nodes in the subtree rooted at a node x, for all x. Using these values one can calculate the number of nodes lying on the path between two label ‘1’ nodes (for more details see the next section);

EXPLANATION:

The problem states that there can be at most one path between a pair of nodes, i.e., the graph has no cycles. This means the graph is a union of trees.

It is easy to see that the result for both (1) and (2) can be obtained by computing the result for individual tree and then adding them together. Hence, the problem reduces to solving the problem on a tree.

In a single tree all nodes are connected to one another, hence (1) is equivalent to computing the label ‘1’ nodes in the tree. If the number of such nodes is n, then the number of pairs will be (n * (n - 1))/2.

In order to compute the result for (2), we can iterate through all nodes w in the tree and check if it lies on the path between two label ‘1’ nodes. A naive way of considering all paths among label ‘1’ nodes will certainly run out of time as there can be O (N2) such paths. Luckily, there is an easier way to check the same.

For this we make the tree rooted at some node r, and for each node x of the tree compute the number of label ‘1’ children in the subtree rooted at x. We denote this number by I(x). Now let us assume that the children nodes of w are y1, y2, …, yk. We can see that w will lie on the path between two label ‘1’ nodes if and only if one of the following conditions hold.

  1. 0 < I(w) < I(r). In this case w lies on the path between a node in the subtree and a node outside the subtree both having label ‘1’. The first inequality ensures that there is a label ‘1’ node in the subtree rooted at w, and the second inequality ensures that there is at least one label ‘1’ node outside the subtree.
  2. label(w) = 1 and I(w) > 1. In this case subtree rooted at w has at least one node other than w with label ‘1’. The path between this node and w is the desired path.
  3. At least two of the I(y1), I(y2), …, I(yk) are non-zero. In this case the desired path will be between two nodes in the subtree rooted at w, which will pass through w.

This means that if we can compute I(x) for all nodes of the forest, then we can solve the problem easily. This can be achieved easily by traversing the nodes of the tree in reverse topological order, and using the following recurrence:
I(w) = label(w) + I(y1) + I(y2) + … + I(yk), where y1, y2, …, yk are children of w.

The following code partitions the forest into trees, and computes the I() of all nodes.

bool visited[N];
int I[N];
int parent[N];
int root_id[N];  // root node of the tree to which this node belongs to.
int id = -1;  // root of the current tree.

// Perfroms the depth first traversal on the tree rooted at v, and computes
// I() of all nodes in the tree.
void do_dfs(int v) {
    visited[v] = true;
    I[v] = label[v];
    root_id[v] = id;
    
    for (int x : neighbors[v]) {
        if (visited(x)) continue;
        
        parent[x] = v;
        do_dfs(x);
        I[v] += I[x];
    }
}

// Partitions the forest into trees, and computes I() for al nodes.
void partition_and_compute() {
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            id = i;
            do_dfs(i);
        }
    }
}

TIME COMPLEXITY:

O (N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

7 Likes

I did something different for the second query. We know that a ‘0-label’ node will not lie in the path of two ‘1-label’ nodes only if they are leaves of the tree or they are connected to other ‘0-label’ leaves of the tree, either directly, or through a chain of ‘0-label’ nodes.

So, I needed to remove all such leaves recursively(or iteratively) until the only leaves that were left were ‘1-labeled’.

Finally, when I separated each tree in the graph for the first query, the number of total nodes in the tree gave me the second answer.

5 Likes

I tried to solve it other way (with no success):

Furik is interested in one question: what is the number of pairs of rooms, which have a draught between them.

I think it is n * (n-1), where n is number of rooms with opened windows in tree…

Rubik wants to know what is the number of the rooms, which have at least one draught passing through the room.

Here it is n, but only iff n > 1, for n <= 1 it is 0, because of the definition:

There is a draught between two different rooms if both rooms have opened windows, and are connected with each other by some way.

Can someone describe what did I understood wrong?

I tried something different(with no success till now) and recursively traversed the tree from one node with opened window to all other nodes and storing the path in a stack and if a node with open window was found the answer was simply the size of the stack + prev ans … I’ve tried many different test cases and matched them with accepted solutions.

Can someone help me with what i did wrong … it would be really helpful…

My solution - CodeChef: Practical coding for everyone

I wonder why my solution was not accepted. I first computed the connected components using Union Find algorithm. Then in each connected component I did the following:

  1. For Furik question I counted the no. of nodes those have open windows say its c. and then I computed (c*c-1)/2. Then added them for all connected components.
  2. For Rubik question I counted the no. of nodes those are not lying in the path of two opened window nodes for each connected component using DFS. Then I just subtracted the value from the total no. of nodes of that connected component and add them to the ans.

Could anyone help me to find out what I did wrong??
http://www.codechef.com/viewsolution/3428050

2 Likes

I solved it using bfs traversal…for every bfs tree in the forest rooted at a ‘1’ node I calculated the distance array and the parent array for every node in the tree.now for every ‘1’ marked node I recursively moved to its parent until i reached the root or a node which is visited already…all 0 marked nodes are included in the answer and all the 1 marked nodes are marked visited…so now I carry on this process for some other unvisited ‘1’ marked node in the same tree till no ‘1’ marked node is left unvisited for this tree.this I applied to all the bfs trees.I know it was a sub optimal solution but just a trick of marking the visited array while recursively going backward till the root made it pass the given time limits…i had fun solving this as a sub optimal solution struck me and i made it pass the time limits through minute but significant optimizations :smiley: nice problem.

2 Likes

@honeyslawyer : The main idea behind my solution was the same. Use BFS, Store parent and traverse recursively till u reach root or a node that already has a draught

In fact after using fast I/O my solution became the best one. I guess this BFS solution was better than the DFS solution!

@Eu1er : Stack Size will not give u the right answer, You are missing a key point here. Imagine 3 rooms with window side by side 1-2-3, with 2 edge (1-2,2-3) now suppose all 3 have window and u start from 1. Now u go to 2 and ur stack size is 1. so ans=1. again u go to 3, your stack size is 2. so ans becomes 3. But the actual ans is 2 only. You need to empty your stack after discovery of a window.

1 Like

My solution was accepted, I made a BFS forest(Root of each tree may or MAY NOT be marked) and counted number of nodes between two nodes with open windows, This had two cases a) two nodes were in two different sub trees for which i found the common ancestor and marked all the nodes between the two marked nodes and the common ancestor b) The two nodes lie one above the other in this case i simply marked the nodes which came on the way.

Here is an efficient implementation of the above : CodeChef: Practical coding for everyone

If anyone gets time could they please look at my code and tell me why I’m getting wrong answer
http://www.codechef.com/viewsolution/3453438
Thanks.

Hmm, I’m getting a wrong answer but can’t seem see, why, some basic tests locally seem to pass, anyone have a some more test cases that I could run my code through?

Here is my current solution that is failing:

http://www.codechef.com/viewsolution/3471638

Edit- Here is another version but still failing:
http://www.codechef.com/viewsolution/3471976

I’m using n*n-1/2 for calculating first answer by checking sub-trees for all “1” nodes.

The second answer I’m counting all leaves with no open windows and subtracting from the number of nodes, with a special case being 1, which I return 0.

Or am I mis-understanding the 2nd question, i.e. there is still a draught even if the room has no openwindow as a long as it is on the path of rooms that have openWindows, even if those rooms are not direct neighbours? So they can be few nodes away?

I solved this problem using a DFS that returns a parameter which tells whether the current node is to be included or not for the answer of 2nd part of the question… The description of my solution is given here

Guys can someone please tell me why my solution is being rejected:

http://www.codechef.com/viewsolution/3482076

I can’t see what’s wrong with it. I’m using the method of counting no of 1-label nodes in a tree for answer to 1 and pruning for the answer to 2.

I would really like to get some closure on this. Is my method of printing the answer somehow not being accepted?

plz post the tester’s and setter’s solution asap.

Could anyone tell me what the heck is wrong with my solution?

http://www.codechef.com/viewsolution/3498164

please tell me what is wrong with the sol

what is to be done after calculating I[] of all nodes??
Plz somebody help
This is my after reading this editorial
http://www.codechef.com/viewsolution/3931123
it is giving WA

In this paragraph : “For this we make the tree rooted at some node r, …”(5th paragraph in EXPLANATION) What is “w” ?

It’s a generic node as defined in the previous paragraph. We need to iterate over all nodes w in the tree.

What do you mean by “reverse topological order” ?Please explain.