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®. 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

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.

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

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

I used the same approach. I removed all such leaves iteratively :slight_smile: http://www.codechef.com/viewsolution/3403008

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?

Hm, I think now it’s clear to me…

Why there is not a better test case ? :’-(

Rubik’s answer is not n. As stated by @anton_lunyov in the contest “After solving the problem I could assert that draught is passing through the room if and only if this room lies on the path between two different rooms with open windows (regardless of whether it has open window or not). Regarding Furik question, it is clear enough: the pair of rooms should be counted if and only if they are connected and both have open windows.”

1 Like

This means a node should be visited only after all its children have been visited.

That shows that I’m an ignoramus, I read that comment, but somehow ignored it :frowning:

how to check the third case

You already have the I() values of all children of a node, just check if there are two or more children have nonzero I() value.

Actually the language of problem was very confusing. I also had 28 WA. Then I read this comment and it helped a lot :slight_smile: Thanks to @anton_lunyov

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 - http://www.codechef.com/viewsolution/3436675

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

Actually i was able to solve it because of @anton_lunyov comment.Before that i interpreted as u @betlista .For me problem statement was confusing.

@sambuddha - You did everything right … the only problem(the same i had) is that we forgot to explicit typecast the count to long long which cost me around 20 WA’s … here’s your AC solution which i tried
just modified the tot_count

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

… even though i found the problem i have no clue as to why it happens … if you have any idea please share it with me …

count is int and multiplying count by count is an integer that overflows integer value…although you are putting it up in long long variable but count*count is still int

1 Like
//