PROBLEM LINK:
Setter: Takuki Kurokawa
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
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.