With an extra logN factor, we can use a fenwick tree. While maintaining frequency of every element in set, if the frequency is 1, update fenwick tree, upd(a[u], +1) and when the frequency becomes 0, upd(a[u], -1). At every point in dfs, do a binary search over fenwick tree to find max i such the prefixSum[i] = i . Then i + 1 is your current MEX. Here upd function adds values to index, that is why +1, -1 to track if number is present on not.
Code :- CodeChef: Practical coding for everyone
Someone please explain me that in dfs function while reinserting the node
if(cnt[value[node]] == 0)
st.insert(value[node]);
works Here while
if(st.find(value[node]) == st.end())
st.insert(value[node]);
gives wrong answer. Here @suman_18733097
We can optimise it further by finding the \text{MEX} only when we encounter a leaf node. Because the \text{MEX} of values of all nodes in the path from 1 to K (where K is a leaf node) will be always greater than or equal to that of all internal nodes encountered in the path from 1 to K.
1 Like
Can someone help me with this. I’ve tried to traverse the tree with node indexes.
Sample test case:
5
1 2 3 4 0
1 2
2 3
2 4
1 5
While reading the input, I try to build a paths array which works as follows
paths[y] = x
So,
paths[1] = 0 (zero for root node)
paths[2] = 1
paths[3] = 2
paths[4] = 2
paths[5] = 1
and so on
set[0] = A[0] (value of root)
Now, I can make my sets by iterating from (1,N) as follows:
set[i] = A[i] U set[paths[i]]
now iterating over this set list, I can find mex and max(mex) accordingly.
Is there something wrong in my assumption? Please help me out.
I missed to read it as tree instead tried to continue applying Dijktra algorithm for the shortest path. Only 2 cases passed and rest all failed.
What could have been the reason for dijkstra not working? I am still struggling to figure out.
This is my first post here. Just not sure if code long code snippet can be attached. I am pasting here.
Any help is much appreciated. 
from collections import defaultdict
def find_mex(s):
return list(set(range(len(s) + 1)) - s)[0]
def get_min_position(dist, visited):
min_ = float('inf')
idx = len(dist)
for i, j in enumerate(dist):
if i not in visited:
if j < min_:
min_ = j
idx = i
return idx
def testcase():
n = int(input())
nodes = list(map(int, input().split()))
edges = defaultdict(list)
for _ in range(n-1):
u, v= map(int, input().split())
edges[u-1].append(v-1)
dist = [ float('inf') for _ in range(n)]
dist[0] = nodes[0]
visited = set()
max_mex = find_mex({nodes[0]})
nodes_mex = [ [ {nodes[0]}, max_mex ] for _ in range(n)]
i = 0
while i < n:
if nodes_mex[i][1] > max_mex:
max_mex = nodes_mex[i][1]
visited.add(i)
for node in edges[i]:
if node not in visited:
new_set = nodes_mex[i][0].union({nodes[node]})
new_mex = find_mex(new_set)
if dist[i] + 1 < dist[node]:
dist[node] = dist[i] + 1
nodes_mex[node][0] = new_set
nodes_mex[node][1] = new_mex
elif dist[i] + 1 == dist[node] and new_mex > nodes_mex[node][1]:
nodes_mex[node][0] = new_set
nodes_mex[node][1] = new_mex
i = get_min_position(dist, visited)
return max_mex
for _ in range(int(input())):
print(testcase())
Your code is somehow dependent on the ordering of edges.
For this tc the answer should be 2 but your code gives 0.
1
4
1 2 1 0
4 1
1 2
1 3
But when I switch 4 1 with 1 4 the output is correct.
Should not this be the case when the input says E(u,v), this means there is an edge originating at u and ending at v. E(4,1) implies 4 should be the root in this case and there is no path from 1 to 4 but there is a path from 4 to 1.
As per result of this test case, I have to assume that ordering of u,v in edges does not matter. Whichever is smaller out of u and v, should be the source. Is my understanding right?
Even with the understanding of having smaller node as the source node, most of the test cases fail.
void dfs(int s,int par){
vis[a[s]]++;
if(vis[a[s]]) // what is this check for ??
st.erase(a[s]);
for(auto it:g[s]){
if(it!=par)
dfs(it,s);
}
ans=max(ans,*st.begin());
vis[a[s]]–;
if(vis[a[s]]==0) // Why this check is required ??
st.insert(a[s]);
}
The given tree is undirected. So when there is an edge from 4 to 1 then there is also an edge from 1 to 4.
How do you test this input against your code?
1 Like
//Problem Link -
/* By Krishna Kumar */
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/trie_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ld long double
#define mod 10000000
#define inf 1e9
#define endl “\n”
#define pb push_back
#define vi vector
#define vs vector
#define pil pair<ll,ll>
#define ump unordered_map
#define mp make_pair
#define pq_max priority_queue
#define pq_min priority_queue<ll, vi , greater>
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define mid(l,r) l(l+(r-1)/2)
#define bitx(x) __builtin_popcount(x)
#define loop(i,a,b) for(int i = (a);i<=(b);i++)
#define looprev(i,a,b) for(int i = (a); i>=b; i–)
#define iter(c,it) for(__typeof(c.begin()) it = c.begin();it!=c.end();it++)
#define log(args…) { string _s = #args; replace(_s.begin(), _s.end(), ‘,’, ’ '); stringstream _ss(_s); istream_iterator _it(_ss); err(_it, args); }
void err(istream_iterator it){}
template<typename T, typename… Args>
void err(istream_iterator it, T a, Args… args){
cout<<*it<< "="<<a<<endl;
err(++it, args...);
}
#define logarr(arr,a,b) for(int i = a;i<=b;i++) cout<<arr[i]<<" "; cout<<endl;
template T gcd(T a, T b){if(a%b) return gcd(b, a%b); return b;}
template T lcm(T a, T b){return ((a*b)/gcd(a,b));}
vs tokenizer(string str, char ch ){std::istringstream var((str)); vs v; string t; while(getline((var), t, (ch))){v.pb(t);} return v;};
//typedef tree<ll, null_type, less, rb_tree_tag, tree_order_statistics_node_update> pbds;
//typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pbtrie;
// void file_i_o(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(“input.txt”, “r”, stdin);
// freopen(“output.txt”, “w”, stdout);
// #endif
// }
vector<vector> graph;
vector a;
vector vis;
set st;
int ans;
void dfs(int s){
// vis[a[s]]++;
// if(vis[a[s]]) st.erase(a[s]);
vis[s] = 1;
st.erase(a[s]);
for(int child: graph[s]){
if(!vis[child]){
dfs(child);
}
// if(child == par) continue;
// dfs(child, s);
}
ans = max(ans, *st.begin());
st.insert(a[s]);
// ans = max(ans, *st.begin());
// vis[a[s]]--;
// if(vis[a[s]]==0) st.insert(a[s]);
}
void solve(){
int n;
cin >> n;
//clearing the variables
graph.clear();
a.clear();
vis.clear();
// resizing the variables
graph.resize(n+1);
a.resize(n+1);
vis.resize(n+1, 0);
loop(i, 1, n) cin >> a[i];
loop(i, 1, n-1){
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
loop(i, 0, n){
st.insert(i);
}
ans = -1;
// dfs(1, -1);
dfs(1);
cout << ans << endl;
}
int main(int argc, char const *argv[]){
//file_i_o();
clock_t begin = clock();
int T;
cin>>T;
while(T--){
solve();
}
#ifndef ONLINE_JUDGE
clock_t end = clock();
cout<<"\n\n\nExecuted In: "<<double(end-begin)/CLOCKS_PER_SEC*1000<<" ms";
#endif
}
it is passing most of the test case but failing for few testCases . can anyone explain why ?
Suppose we are at some state of dfs traversal and about to backtrack. Let the value at current node (which is leave node by assumption) be v and cnt[v] = 2. Currently there is no v in set st, therefore while backtracking we must not insert v to st , but in your second code it will check if(st.find(value[node]) == st.end()); which is true (as we removed it when we first came across v), hence it will add it to st which not the right thing to do. Hence it can lead to wrong answer.
Not to mention if(cnt[value[node]] == 0) was the exact thing needed.
paths is not a the right way to store the given tree. It work only if the edges are given in certain format : <node closer to 1> <node farther from 1>. But this need not be the case. Consider :
1 2 3 4 0
1 2
3 2
2 4
1 5
Here path[3] would never be updated and path[2] would overwritten. Adjacency list is one common way of representing graphs with large number of nodes but lesser number of edges.
I don’t understand how iterating from 1 \to N could map to MEX of corresponding shortest path from 1.
We need to add it back to the set (which represents the excluded values) when we backtrack from the last of its value. To find whether it is the last one or not we check the mentioned condition.
For getting the mex from node 1 to node i , we need all numbers [0- n] except the numbers on the nodes which are along the path from 1 to i .
So when we backtrack from a leaf node then we must reinsert the values that we removed from the set to get the mex along some other path 1 to j .
This was my logic !
Correct me if i am wrong …
My solution using First technique - Maintaining all elements in a set that are not present in current path from 1 to i :
https://www.codechef.com/viewsolution/60524534
My solution using Segment tree Range sum Query + Binary search :
https://www.codechef.com/viewsolution/60524856
Important corner case :
4
0 1 1 2
1 2
2 3
2 4
Answer = 3 and not 2
We need to reinsert only when we do not have any other value of that type in current path.
Consider path 0 \to 2 \to 1 \to 2 in st we will have \{3, 4 \dots\} when we backtrack to 0 \to 2 \to 1 should we add back the 2 ? 2 is not there in st but still, we must not add it back.
1 Like