SOS - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Takuki Kurokawa
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Depth first search (dfs)

PROBLEM:

We are given a tree of N vertices and a string C of length N where each character can be R, G or B. We need to validate the input. The input is called valid if for all pairs of vertices (i, j) where C_i = C_j =B we must have atleast one R vertex and atleast one G vertex in the shortest path between i and j.

EXPLANATION:

  • Let us consider only the edges which are not of the type R- G and construct a graph from it. We will end up with a forest of many connected components.

  • Now we can observe clearly that if we consider one B vertex in connected component C_i and one one blue vertex from different connected component C_j, the path between them in the original tree will always have R-G edge and hence those pairs are good. ( After all, we ended up with connected components because of the removal of R-G edges ).

  • Now what happens if we consider two B vertices in the same connected component ? I claim that if such a situation exists, then our answer is NO else our answer is YES. This is because if we consider the pair of B vertices with the shortest path in the component, it can be of the form B-B or B-R-R-R-\dots-B or B-G-G-G-\dots-B which clearly has atleast one of the color R or G missing. This violates our condition and thus we shouldn’t have more than one B vertex in a single connected component.

  • The condition of checking number of B vertices in a connected component can be checked with a simple dfs traversal.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Editorialist's solution

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

int cnt = 0;

void dfs(int i, string &color, vector<vector<int>> &g, vector<bool> &check)
{
      if (color[i] == 'B')
      {
            cnt++;
      }

      check[i] = true;

      for (int j : g[i])
      {
            if (check[j])
                  continue;
            dfs(j, color, g, check);
      }
}

int main()
{
      int tests;
      cin >> tests;
      while (tests--)
      {
            int n;
            cin >> n;

            vector<vector<int>> g(n);
            vector<bool> check(n);

            string color;
            cin >> color;

            for (int i = 0; i < n - 1; i++)
            {
                  int x, y;
                  cin >> x >> y;
                  x--;
                  y--;

                  if ((color[x] == 'R' && color[y] == 'G') || color[x] == 'G' && color[y] == 'R')
                        continue;

                  g[x].push_back(y);
                  g[y].push_back(x);
            }

            bool ok = true;

            for (int i = 0; i < n; i++)
            {
                  if (check[i])
                        continue;

                  cnt = 0;
                  dfs(i, color, g, check);

                  if (cnt > 1)
                  {
                        ok = false;
                        break;
                  }
            }

            if (ok)
                  cout << "Yes" << endl;
            else
                  cout << "No" << endl;
      }
      return 0;
}

Setter's solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        string color;
        cin >> color;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int x, y;
            cin >> x >> y;
            x--, y--;
            g[x].emplace_back(y);
            g[y].emplace_back(x);
        }
        string ans = "Yes";
        vector<int> dp(n);
        function<void(int, int)> dfs = [&](int v, int p) {
            vector<int> children(4);
            for (int to : g[v]) {
                if (to == p) {
                    continue;
                }
                dfs(to, v);
                children[dp[to]]++;
            }
            if (color[v] == 'B') {
                if (children[0] + children[1] + children[2] != 0) {
                    ans = "No";
                }
                dp[v] = 0;
            } else if (color[v] == 'R') {
                if (children[0] + children[1] >= 2) {
                    ans = "No";
                }
                if (children[0] + children[1] >= 1) {
                    dp[v] = 1;
                } else {
                    dp[v] = 3;
                }
            } else if (color[v] == 'G') {
                if (children[0] + children[2] >= 2) {
                    ans = "No";
                }
                if (children[0] + children[2] >= 1) {
                    dp[v] = 2;
                } else {
                    dp[v] = 3;
                }
            } else {
                assert(false);
            }
        };
        dfs(0, -1);
        cout << ans << '\n';
    }
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 10000;
const int MAX_N = 200000;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 200000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll p = 1000000007;
ll sum_nk = 0 ;

void bfs(int u , int col[] , vector<ll> adj[] , vector<int> &vis , int curr_col)
{
    vis[u] = 1 ;
    queue<int> q ;

    q.push(u) ;
    while(!q.empty())
    {
        int u = q.front() ;
        q.pop() ;

        for(int i = 0 ; i < adj[u].size() ; i++)
        {
            int v = adj[u][i] ;
            if(vis[v] == 1 || col[v] == curr_col)
                continue ;
            q.push(v) ;
            vis[v] = 1 ;
        }
    }
    return ;
}

void solve()
{   
    int n = readIntLn(1 , MAX_N) ;
    sum_n += n ;

    string str = readStringLn(n , n) ;
    for(int i = 0 ; i < n ; i++)
        assert(str[i] == 'R' || str[i] == 'G' || str[i] == 'B') ;

    string colour = "RGB" ;
    int cnt[3] = {0 , 0 , 0} ;
    int col[n] ;

    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < 3 ; j++)
            if(str[i] == colour[j])
            {
                cnt[j]++ ;
                col[i] = j ;
            }

    vector<ll> adj[n] ;
    for(int i = 0 ; i < n-1 ; i++)
    {
        int u = readIntSp(1 , n) ;
        int v = readIntLn(1 , n) ;

        u-- ; v-- ;
        adj[u].push_back(v) ;
        adj[v].push_back(u) ;
    }

    if(n != 1)
    {
        for(int i = 0 ; i < n ; i++)
            assert(adj[i].size() != 0) ;
    }
    for(int i = 0 ; i < 3 ;i++)
        cerr << colour[i] << ": " << cnt[i] << ' ' ;
    cerr << endl ;

    int flag = 0 ;
    for(int i = 0 ; i < 2 ; i++)
    {
        vector<int> vis(n) ;
        for(int j = 0 ; j < n ; j++)
        {
            if(col[j] == 2)
            {
                if(vis[j] == 1)
                    flag = 1 ;
                bfs(j , col , adj , vis , i) ;
            }
        }
    }

    if(flag)
        cout << "nO" << endl ;
    else
        cout << "yES" << endl ;
    return ;


}
 
signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);

    for(int i=1;i<=t;i++)
    {    
        solve() ;
    }
    
    assert(getchar() == -1);
    assert(sum_n <= MAX_SUM_N);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr << "Sum of product : " << sum_nk << '\n' ;
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

2 Likes

This problem is solvable also using DP on trees which I’d argue is a bit more educational in nature as it can be applied to numerous other problems as well. Here’s my solution using this technique if anyone is curious: Solution: 55909040 | CodeChef

4 Likes

Was it possible to do it with a Single DFS from any blue node, while keeping track if we have covered an R and a G node while looking for another B. If the number of true(s) = no. of pairs, YES, else NO?
Also, pass the parent node so the initial B node isn’t counted.

Not exactly like that, but rather similar to your idea - I’ve posted such a solution above :slight_smile:

1 Like

I went through it. Not having a strong hold of DP right now but I got the idea :smiley:

1 Like

I solved it by creating a new condensed tree by compressing all connected nodes of the same color into one. And then we check these 2 conditions:

  1. In the original tree there shouldn’t be B-B edge.
  2. In the condensed tree there shouldn’t be a non-blue node that is directly connected with 2 or more blue nodes.

CODE

4 Likes

I used Multisource BFS from every Blue node here is the implementation Solution: 55907639 | CodeChef
It fails two test cases does anyone knows is it correct to do so ? I store for every node the number of greens and reds that are covered by the first blue node that reaches here , then if any node in the bfs reaches the node again i check then number of reds and greens travelled by the new node before now and that of the of first blue node that visited this node. If reds>=1 and greens>=1 then we continue else we say it is invalid .
Is there something wrong in this idea ? Any help would be appreciated.

Yeah I used the same approach but I got WA and was unable to generate a case for which my code failed.

I used Multisource bfs too, still couldn’t find any test case where it fails, maybe the testcases where lousy.

Me too used the same approach but then after wa I figured out this.
1
7
RBGRBRB
1 2
2 3
3 4
4 5
4 6
6 7

MultiSource BFS passes this case :frowning:

Try this.

TEST
1
5
BBGRG
2 5
3 5
4 1
1 5

Correct answer should be No

Got it where I was wrong thanks a lot!!

Good, I also came up with DP solution like you. And yes, I thought it was really educational for participants.

My single dfs also passes this.

Yeah my code also gives no.

Try this.

TEST
1
6
BGBRRB
1 2
2 5
4 3
3 5
5 6

Correct answer should be No

1 Like

Oh i see now. Thank you.

1 Like

Test cases were a bit weak -
I submitted a solution to the problem and even before getting a verdict, I found a bug in my code. However, my submission got AC, which indicates weak test cases of the problem.
This submission takes around three minutes to run on my local machine and has a runtime complexity of O(n^2) on the following case.

n = 200000
C = GGGGGGG…
tree = 1–2–3–4–5–6…–(n-1)–n

it wasn’t working for your recent submission, it was showing Yes, So I gave those testcases.