PROBLEM LINK: LINK
Author: Nishit Sharma
Tester: Aman Singhal
Editorialist: Nishit Sharma
DIFFICULTY:
Easy-Medium.
PREREQUISITES:
DFS,Bitwise operations
PROBLEM:
Given an integer K and a tree with N nodes rooted at 1, where the ith node has the value A[i] . Choose any leaf node and for every node i on the simple path from root to the leaf node choose a value D such that 2^{A[i]-1}\leq D \lt 2^{A[i]}. Determine whether you can obtain the value K after performing BITWISE XOR or BITWISE AND of the chosen integers.
Quick Explanation:
Do a DFS on the tree and maintain a map to store the count of all values that occur on a path. Let Big and Small be the largest and the smallest values on the path, M be the most significant bit of K.
The answer will be “YES” if on reaching any leaf node any one of the following conditions is true.
1.Big-1 \gt M and No of times Big occurs on the path is even.
2.Big-1=M and No of times Big occurs on the path is odd.
3.Small-1\gt M and Not all nodes on the path have value Small.
4.Small-1=M
OBSERVATION 1:
Tap to view
The answer only depends on the most significant bit of K and the largest and smallest values on the path from root to leaf.
OBSERVATION 2:
Tap to view
We have to check all leaf nodes to get the correct answer. Mainting a map or a Dictionary while doing the DFS is an optimal way to keep track of values on any path.
Hint 1 :
Tap to view
Try to solve this question for the most significant bit of K, try if you can get the most significant bit in your answer to be the same as the most significant bit in K. Assure yourself that the most significant bit in your anwer will depend on the largest value on the path from root to leaf for the XOR operation and the smallest value on the path for the AND operation.
EXPLANATION:
Tap to view
Now let us see why the answer only depends on the most significant bit of K.
Consider any arbitary node with value X. For this node we are allowed to choose any value between 2^{X-1} and 2^{X}-1 (inclusive). Using basic maths we can prove that we can set or unset any bit from 0thbit to (X-2)th bit in any way we want i.e. only the (X-1)th bit is fixed in all numbers from 2^{X-1} and 2^{X}-1.Hence,solving the problem for only the most significant bit is enough because if we can set the most significant bit then we can set all the other bits according to our need.
Now we will try to solve the problem using only the XOR operation, we shall deal with the AND operation separately.
Using the above stated fact we can see that using the largest value( Big )on the path we can control all bits except for the (Big-1)th bit by doing the XOR operation.
However, the largest value Big may occur multiple times on the path, now two more cases arise here:
-
Big occurs odd number of times:
In this case the (Big-1)th bit wil be set in our answer, hence if Big-1 is equal to the most significant bit of K, then the answer is “YES”.
2.Big occurs even number of times:
In this case the (Big-1)th bit will not be set in our answer but we can still control all bits from 0 to Big-2, hence if Big-1 is greater than the most significant bit of K, then the answer is “YES”.
Now coming to the AND operation, in this operation the the most significant bit will be goverened by the smallest(Small) value on the path from root to leaf.
An important edge case here is that we can control the (Small-1)th bit in our answer if there is atleast one node on the path will value greater than Small.In other words the (Small-1)th will be compulsorily set in our answer if and only if all values on the path are equal to Small. So we again have two cases here:
- There is atleast one node with value greater than Small: Then the answer is “YES” if Small-1 is greater than or equal to most significant bit of K.
- All nodes on the path have value Small: The answer is “YES” if and only if Small-1 is equal to the most significant bit of K.
Coming to the implementation, we will visit all leaf nodes and then check if any of the above mentioned conditions is true. This can be done using DFS while maintaining a ordered map/dicionary to keep track of the smallest and the largest values on the path. See the setters solution to get a better idea of the implementation.
Bonus:
Try to print the path from root to leaf and the corresponding values chosen for each node.
Overall Time Complexity:O((N))
CODE:
Setter's Solution(C++)
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define endl "\n"
#define f first
#define se second
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
const int N=5e5+3;
map<ll,int> m;
vector<int> a;
multiset<int> s;
vector<int> v[N];
ll k;
int n;
int msb;
void init()
{
fab(0,n+1,i)
v[i].clear();
a.clear();
m.clear();
}
void findmsb()
{
fab(0,64,i)
{
if(k&(1LL<<i))
msb=i;
}
}
bool dfs( int src, int par)
{
m[a[src-1]]++;
bool ok=0;
for(auto i: v[src])
{
if(i^par)
{
ok|=dfs(i,src);
}
}
if(v[src].size()==1 and v[src][0]==par)
{
//this is a leaf node
assert(m.size()>0);
auto big=m.rbegin();
auto small=m.begin();
if(big->first > msb and (big->second)%2==0 )
ok|=1;
if(big->first==msb and (big->second)%2==1 )
ok|=1;
if(small->first > msb and m.size()!=1)
ok|=1;
if(small->first==msb)
ok|=1;
}
m[a[src-1]]--;
if(m.find(a[src-1])!=m.end() and m[a[src-1]]==0)
m.erase(a[src-1]);
return ok;
}
int main()
{
quick;
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
init();
a= vector<int> (n);
fab(0,n-1,i)
{
int x,y;
cin>>x>>y;
assert(x>0 and x<=n and y>0 and y<=n);
v[x].pb(y);
v[y].pb(x);
}
fab(0,n,i)
{ cin>>a[i];
a[i]--;
assert(a[i]<64 );
assert(a[i]>=0);
}
findmsb();
bool ok=dfs(1,-1);
cout<<(ok?"YES":"NO")<<endl;
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Tester's Solution(Python)
import sys,collections
input=sys.stdin.readline
def main():
T=int(input())
for _ in range(T):
N,K=map(int,input().split())
Tree={} #Dic for storing tree
for j in range(N):
Tree[j]=[]
for i in range(N-1):
u,v=map(int,input().split())
Tree[u-1].append(v-1)
Tree[v-1].append(u-1)
A=list(map(int,input().split()))
vis=[0 for i in range(N)] #to mark visited vertices 0 for visited and 1 for not visited
maxval=[[0,0] for i in range(N)] #Nx2 list where each i stores max value till now and its count
minval=[0 for i in range(N)] #Nx2 list where each i stores min value till now
lfnode=[] #list to store leaf nodes
#Appending node 1
vis[0]=1
Q=collections.deque([0])
maxval[0][0],maxval[0][1]=A[0],1
minval[0]=A[0]
while(len(Q)!=0):
a=Q.pop()
mv1=maxval[a][0]
mv2=minval[a]
flag=0 #to check leaf node
for i in Tree[a]:
if (vis[i]==0):
vis[i]=1
flag=1 #not a leaf node
v=A[i]
Q.append(i)
#Comparing maximum value of parent node
if (mv1<v):
maxval[i][0],maxval[i][1]=v,1
elif(mv1==v):
maxval[i][0],maxval[i][1]=mv1,maxval[a][1]+1
else:
maxval[i][0],maxval[i][1]=maxval[a][0],maxval[a][1]
#Comparing minimum value of parent node
if (mv2>v):
minval[i]=v
elif(v==mv2):
minval[i]=mv2
else:
minval[i]=minval[a]
if (flag==0):
lfnode.append(a)
flag=0 #For answer if 0 then NO else YES
K1=len(bin(K))-2 #length of K
#print(lfnode,val)
for i in lfnode:
v1,v2=maxval[i][0],maxval[i][1]
if (v1>K1 and v2%2==0):
flag=1
elif(v1==K1 and v2%2==1):
flag=1
v11=minval[i]
if (v11>K1 and v11!=v1):
flag=1
elif(v11==K1):
flag=1
if(flag==1):
break
if (flag==1):
print("YES")
else:
print("NO")
main()
If anything is unclear please let me know in the comments, it will help me improve.