Saw your number of Submissions.
Respect!
1 Like
I have a nearly same approach.But I get TLE on submission.Can you point out my mistake ??, thanks.
link: CodeChef: Practical coding for everyone
assume Ai<=1e6 while reading this comment
for max function:
various approaches for bonus parts:
1.Using segment tree+processing queries offline (O(qlogn+nlogn))
2.alternatively use sparse table to solve in O(qlogn+nlogn) online.
can be done in O(q+nlogn) if we use tarjans offline algo for lca
3.updates can be handled with centroid decomposition.(there is a hld approach also but centroid is easier to implement imo) (O(qlogn+nlogn))
is there a simpler/neater non-overkill approach for updates?
this was for max part how to handle updates,solve in O(1) or even O(logn) for min part
9 Likes
My simple approach precompute LCA it is common to find lca of two nodes in logn time
Now what we have in our hand is the lca of nodes x and y
. With this LCA try finding number of nodes between the path from node x to y
. After finding number of nodes if it is greater than 100 surely overlap will occur return answer as 0
else traverse the path . from node x to lca and node y to lca store this <100 nodes in vector sort it
and check differences of adjacent pair in this vector
.
Submission Link:-SImple Solution
Hey, can anyone take a look at my solution ? I am also considering the case with 0 separately, and other cases by simple brute force. Why is it giving TLE?
while(t--) {
int n,q;
cin>>n>>q;
int a[n+1];
for(lli i=1;i<=n;i++){
cin>>a[i];
}
vector<int>adj[n+1];
loop(i,n-1){
lli x,y;
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
loop(qw,q){
lli x,y;
cin>>x>>y;
queue<lli>q;
int vis[n+1]={0};
int parent[n+1]={0};
q.push(x);
vis[x]=1;
parent[x]=x;
while(q.empty()==false){
lli node = q.front();
q.pop();
for(auto j : adj[node]){
if(!vis[j]){
vis[j]=1;
q.push(j);
parent[j]=node;
}
}
}
vector<int>temp;
while(parent[y]!=y){
temp.pb(a[y]);
y = parent[y];
}
temp.pb(a[x]);
sort(all(temp));
int mini = INT_MAX;
for(int i=0;i<temp.size()-1;i++){
mini = min(mini , (temp[i+1]-temp[i]));
}
cout<<mini<<endl;
}
}
For 30 marks , store parent of each node and backtrack .
1 Like
I stuck with same thing. Though for bonus part, I feel MOs can work.
1 Like
Anyone else like me went complete overkill and did heavy-light decomposition? It solves the first bonus though.
1 Like
Dude on line 107 you are printing something extra. Check if that’s the cause
(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)
is this type implementation have any name ?
Writing Code for Different Cases that is IF ELSE implementation Xd
Even you knew the solution, you didn’t submit it hoping you will spam in Codechef discuss.
2 Likes
Thank you for that. I’ve updated the link. And commented that part.
Actually, when I was adding comments for others to read. I mistakenly uncommented that. Even though my solution is still WA. But my approach is correct(Someone did the same and got 30 points). Now I have to find where I implemented it wrong.
Thanks again.
Just calm down and check it once tomorrow, you may be able to see what u weren’t. 
3 Likes
Doing DFS or BFS gives TLE as there are a lot of Queries and each query takes O(N) time because the time complexity of those algorithms is O(V+E). The motive of the question is to answer each query in O(1) at max 100 operations. This can easily be done by the following steps:
- Fix a node as root and compute depths and parents of each node
- Move the node deeper node toward root until the depths of both nodes are equal
- Then move both the nodes simultaneously to meet at the same node(technically, LCA(least common ancestor)
- By counting the number of total steps made. we can get the distance between nodes. If the distance is greater than 100 then, the answer is zero(pigeon hole principle/common sense)
My code: (Variables are self explanatory)
#include <bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()), ((v).end())
#define sz(v) ((int)((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define rep(i, v) for(int i=0;i<sz(v);++i)
#define lp(i, n) for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n) for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n) for(int i=(j);i>=(int)(n);–i)
typedef long long ll;
void local(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
#endif
}
vector par;
vector val;
vector depth;
vector<vector> adj;
void print(vector ar){
for(auto c:ar){
cout<<c<<" ";
}
cout<<endl;
}
void root(int id){
for(auto c:adj[id]){
if(c!=par[id]){
par[c] = id;
depth[c] = depth[id]+1;
root(c);
}
}
}
void solve(){
int N,Q;
cin>>N>>Q;
par.clear();
val.clear();
depth.clear();
adj.clear();
adj.resize(N);
par.resize(N);
val.resize(N);
depth.resize(N);
for(auto &c:val){
cin>>c;
}
//vector<vector<int>> adj(N);
lpi(i,0,N-1){
int u,v;
cin>>u>>v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
par[0] = -1;
root(0);
while(Q--){
int u,v;
cin>>u>>v;
u--;
v--;
if(abs(depth[u]-depth[v]>=105)){
cout<<0<<endl;
continue;
}
if(depth[u]<depth[v]){
swap(u,v);
}
vector<int> tmp;
int diff = depth[u]-depth[v];
int mx =diff;
if(mx>=105){
cout<<0<<endl;
continue;
}
while(diff--){
tmp.push_back(val[u]);
u = par[u];
}
while(u!=v){
mx++;
tmp.push_back(val[u]);
tmp.push_back(val[v]);
u = par[u];
v = par[v];
if(mx>=105){
break;
}
}
if(mx>=105){
cout<<0<<endl;
continue;
}
tmp.push_back(val[u]);
sort(tmp.begin(),tmp.end());
int ans = INT_MAX;
lpi(i,1,tmp.size()){
ans = min(ans,tmp[i]-tmp[i-1]);
}
cout<<ans<<endl;
}
}
int main()
{
local();
int t;
cin>>t;
while(t--){
solve();
}
}
5 Likes
Getting TLE on solution almost similar to that by the setter. Am I missing something here? Any help would be great.