Codechef Internship Test

general
70

please watch video of CodeNCode (best for Binary Lifting)

71

Is it only for 4th-year undergrads?

72

can you please help me with Chemical Explosion Problem. Which concept is used to solve it. Whatever help you can provide me will be appreciable
Problem Link

73

OMG, are you serious? :open_mouth:

74

The question is actually Find maximum distance between two nodes in a tree. You can solve it using 2 dfs (basic approach). There are many articles regarding it.
The answer of the question is ceil(maxDistanceBetweenTwoNodes/2).

Explanation :
Let the longest path in the tree be 1->2->3->4->5->6
1 -> chemical A
6 -> chemical B
After day 0 : A -> 2 -> 3 -> 4 -> 5 -> B
After day 1 : A -> A -> 3 -> 4 -> B -> B
After day 2 : A -> A -> A -> B -> B -> B
After day 3 : A -> A -> AB -> BA -> B -> B

Hence the answer is ceil(5/2) = 3.

75

just calculate diameter of given tree let say it be d
ans will be (d-2)/2+1
for calculation of diameter of tree just google it out it is pretty straight forward dp

76

how much time it take you to solve all :stuck_out_tongue:

77

You can refer to this blog

78

Actually I forgot about the contest. That’s why I started solving from about 7:20 and I completed all till 8:15.

79

great :stuck_out_tongue:

80

yes but how did you calculated that diameter… when i was searching yesterday i came across this term diameter of graph, but i didnt got any efficient algorithm to calculate that. if their is any resource plz share

81

can you plz share any resource about that 2 dfs approach

82

just search diameter of tree. in question given graph is tree. for tree it can be done in 1dfs only
time complexity. - O(dfs*logm) or O(dfs) depending on implementation.

84

For longest Path using 2 dfs, the approach is same for tree as well as graph.
Have a look.
See my approach also.

85

I used binary lifting in problem 4 but still got TLE.
Can please anyone help me with this: https://paste.ubuntu.com/p/rZBpC8cvb5/

86

I have done the same thing but I got WA on few and TLE on other testcases…
I used binary lifting. Can you share your code

87

Solved all but due to slow submission, a lot of time was wasted

88

Used printf and scanf and tle changed to AC like breeze!

89

Sure you here it is

AC_CODE 
#include<bits/stdc++.h>
using namespace std ;
const int mxN =1e5+2 ;
int n,q,r,s=0,eu[mxN],ev[mxN],ew[mxN],anc[mxN][18],d[mxN],a[mxN],ps[mxN];
vector<int>adj[mxN],adj1[mxN] ;
void dfs(int v,int p){
  anc[v][0]=p ;d[v]=d[p]+1 ;
  for(int i=1;i<18;i++)
    anc[v][i]=~anc[v][i-1]?anc[anc[v][i-1]][i-1]:-1 ;
  for(int x:adj[v])
    if(x^p)
      dfs(x,v) ;
}
int lca(int u,int v){
  if(d[u]<d[v])
    swap(u,v) ;
  for(int i=17;~i;--i)
    if(d[u]-(1<<i)>=d[v])
      u=anc[u][i] ;
  if(u==v)
    return u ;
  for(int i =17;~i;--i){
    if(anc[u][i]^anc[v][i]){
      u=anc[u][i],v=anc[v][i] ;
    }
  }
  return anc[u][0] ;
}
void dfs1(int v,int p){
  for(int x:adj1[v]){
    int u = (ev[x]^eu[x]^v)  ;
    if(u==p)
      continue ;
    a[u] = ew[x] ;
    dfs1(u,v) ;
  }
}
void dfs2(int v,int p){
  s+=a[v] ;
  ps[v]=s ;
  for(int x:adj[v])
    if(x^p)
      dfs2(x,v) ;
  s-=a[v] ;
}
void solve(){
  cin >> n>> q >> r ;
  for(int i=0;i<n-1;i++){
    cin >> eu[i] >> ev[i] >> ew[i];
    adj1[eu[i]].push_back(i);adj1[ev[i]].push_back(i) ;
    adj[eu[i]].push_back(ev[i]);adj[ev[i]].push_back(eu[i]) ;
  }
  dfs1(r,0) ;dfs2(r,0) ;dfs(r,0) ;
  while(q--){
    int u,v,ans;cin >> u >> v ;
    ans = ps[u]+ps[v]-2*ps[lca(u,v)] ;
    cout << ans << '\n' ;
  }
  for(int i=0;i<n+1;i++)
    adj[i].clear(),adj1[i].clear(),a[i]=0,d[i]=0,ps[i]=0,s=0;
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}
90

Hang on, what’s wrong with codechef’s syntax highlighting isn’t it weird ?