SOS - Editorial

[sonnandh]

Could you explain your dp solution ?

[un_certainty]

Can anyone help with my submission, ?

My approach is to do multi-source bfs from all the blues and when you encounter a node which is already visited just check if there is green > 0 and red > 0, also keep pushing the values of red and green from parent to child.
I have separately checked for adjacent Blues.

I even created a generated and tested but couldn’t find any wrong testcase yet.

[cubefreak777]

Try this.

TEST

1
7
BBBRRGR
1 4
2 6
3 7
4 5
6 5
5 7

Correct answer should be No

[tabr]

Thank you for telling me! Actually, there are no testcases with all Green because I only tried hard to make cases with a lot of Blue. I will do better next time!

[nichke]

Let’s denote a pair of vertices (u,v) good if the following property is satisfied:

• \exist(x \land y), S_x=R \land S_y=G, such that x and y are on the simple path between u-v

We’ll try to find at least one pair (u,v) of blue nodes such that it is not good. If we manage to do so, the answer is ‘No’, otherwise it’s ‘Yes’.

Suppose we root our tree at some arbitary vertex, for simplicity let that vertex be 1, as it is present in all such trees.

Let distance of v from 1 be d_v. Now each pair of blue nodes (u,v) can be described in exactly one of these ways:

• Let d_v>d_u, u belongs to the path 1-v
• Let d_v>d_u, u doesn’t belong to the path 1-v

Let’s check whether a pair of vertices is good if it satisfies the first condition:

We can just traverse the whole tree from root to leaves by dfs, and keep track of already seen green and red nodes using two counters/flags. Upon reaching blue node (in case it’s not the first on the path) we check whether there’s a red and green node between this and the previous blue node. Obviously if this is true, then there is a green and red node between current blue node and every other blue node on its bath from the root. Otherwise we’ve found a pair which doesn’t satisfy the initial condition.

On the other hand, what happens in the second case?

There are again two possible cases, if we consider the first level of root’s children:

• u belongs to c_i's subtree, while v belongs to c_j's subtree
• both u and v belong to the same child’s subtree

The second case can be solved recursively, by applying the first case’s solution on the needed subtree, so we just consider how to solve the first case.

We can separately check whether there’s a green node between u and v, and do the same for red nodes. If both conditions hold, it’s a good pair, otherwise we’ve found an invalid pair and the answer is ‘No’.

For every child v of root at least one of the following conditions must hold for a green node to exist between every pair of blue nodes:

• there’s a green node on path root-u for every u in v's subtree
• there’s a green node on path root-u' for every u' in root's subtree not present in v's subtree

This can be easily maintained if we build arrays valid from bottom to the top of the tree and solve the problem for every subtree.

I hope this helps, but if not, feel free to ask for any futher clarifications.

[sarvjot_42]

My DP Solution:

Lets define a good path as one which has atleast one red and one green node between any two blue nodes.
Any path can be uniquely represented by its LCA. However there are two cases:
1. The path may go down in different subtrees from LCA, i.e. a v-shaped path
2. The path may go down to a particular node only, i.e. a vertical path

Now, lets define some terminologies:
1. red[node] : 1 if subtree of ‘node’ contains a red node before [going top to down] any blue node, 0 otherwise.
2. green[node] : 1 if subtree of ‘node’ contains a green node before [going top to down] any blue node, 0 otherwise.

We will, maintain above two arrays throughout the dfs. Now lets get back to checking whether all paths represented by current node as LCA, are good or not. We’ll do a bit of case work, let current node be node.

Case 1 → color[node] == blue:
1. All the subtrees must have red[subtree] = 1 and green[subtree] = 1, because of the way we have defined red[] and green[].
2. red[node] = green[node] = 0, because in subtree of node there will be no red or green nodes before node which is blue.

Case 2 → color[node] == green:
1. Here we don’t need to fear about green[], because any path containing ‘node’ will have atleast one green node.
2. However, if number of children of node is sz, atleast sz - 1 subtree should have red[subtree] = 1, because if two or more subtrees have red[subtree] = 0, then we can join a path between these two subtrees, and these will not have a red node between blue nodes.
3. green[node] = 0, because ‘node’ itself is green.
4. red[node] = 1 if all children of ‘node’ have red[subtree] = 1, 0 otherwise.

Case 3 → color[node] == red:
Similar to Case 2.

Code for above approach : https://www.codechef.com/viewsolution/56027770

[gta_vice_city]

Hey @nichke

I am not clear with this part, can you please add more details like why and how this works?

For every child v of root at least one of the following conditions must hold for a green node to exist between every pair of blue nodes :

1. root-u
2. root-u’
   This can be easily maintained if we build arrays valid from bottom to the top of the tree and solve the problem for every subtree

[breddreamer]

My code is giving wa on this problem, can anyone tell me why? I’m using bfs to traverse all the nodes and check if there is greater than one blue node on any components.
Code Link : Online Compiler and IDE - GeeksforGeeks

[shrii_06]

You forgot to change flag to true for each test case. That’s why you were getting WA.
Link to changed code (changed line number 78)

[bugbuster404]

Can anyone plz tell me why I am getting this weird TLE ?
https://www.codechef.com/viewsolution/56723946