7 2 1
4 7
1 2
2 3
3 4
4 5
5 6
6 7
Analyze this for node = 5.
Read about dijakstra’s algo to see how his code works.
This approach is really neat! Would you suggest any similar practice questions that helps build this kind of intuition while tackling such problems?
For now i don’t remember any problem.
But i am sure solving a good number of graph problems might help to build this type of intuition.
why this code is giving a runtime error, I wasted 2 hours during the contest debugging my code but it always give RTE 
Nice explanation.
Can anyone share me the resources to study these topics?? I am new to graph theory?
No, we are not computing the nearest special node but rather we are computing nearest ancestor which contains at least one special node.
1 Like
can you give solution for every subtask ,
like you have given for 100pts
hints for every subtask
I tried imlpementing it using BFS and dijkstra types greedy algorithm, I got all tcs correct except one TLE, Here is my submission, would like to know the issue. CodeChef: Practical coding for everyone
what I did is first update answers for all case where b = special nodes, and put them in a set as we do in dijkstra, but here instead of sorting it by distance from a, we will sort by the distance from A to that special node - distance of that b to special node, and continue BFS. And I think this is the correct Approach, but I am getting TLE for just 1 test case.
Hope somebody helps.
1 Like
Sub Task #1:
You can Naively brute-force for every node b. For every node b try all possible special nodes u and find the distances from u using a linear time dfs thus the complexity would be \mathcal{O}(N^2K) which will pass easily for N \le 200
Sub Task #2:
You can again naively solve for all nodes b by trying all possible special nodes but this time instead of finding the distances in linear time we will use binary lifting to find distances in logarithmic time thus giving a complexity of \mathcal{O}(NKlogN) which is good enough for N \le 2000
Sub Task #3:
This subtask is essentially equivalent to solving the problem for an array. This can be solved easily in linear time by doing some precomputation of reachable nodes for all the special nodes.
Really appreciate the effort.
just one thing, as u said that we should maximise this term D(A,L) so we should get the deepest L , ie . away from the root node. so when in the dfs1 when you are writing in the code
int dfs1(int v,int p){
d[v]=d[p]+1 ;
if(ok.count(v))
c[v]=v ;
for(int x:adj[v]){
if(x==p)
continue ;
int f= dfs1(x,v) ;
if(f&&c[v]==0)
c[v]=f ;
}
return c[v] ;
}
why we are not writing
if(f){
c[v]=f;
}
Yeah of course you can do it that way too. I wrote that extraneous condition just to match the samples exactly, you know exactly matching the samples is another level of satisfaction 
. CODE (Since there were multiple solutions possible)
1 Like
nice. I cannot even think about these things in an ongoing contests. Thrills at its peak.
whenever i see a good coder like 5>= , they will always have the DP of some anime character. I think i should start watching anime just for improving my coding . 
1 Like
Ping me for recommendations 
sure , i had watched some AOT, naruto i guess upto 154 .i will start again someday.
1 Like
for a fixed B, we are looking for the lowest ancestor of B such that subtree of B contains at least one special node.
what does this mean?
Can u please explain the logic. I also tried something similar to that but it did not work, may be i am missing something. Thanks.
Hey @c0rpulent
First of all thanks buddy. Was thinking of same approach but must have some bugs in my code so yours will be helpful in my debugging(plus might no longer use priority queu but uses sets instead 
). As for you it seems you just need 1 or 2 minor optimzation . A simplest one would be to use a simple vector instead of set for solved.
Here is your code with minor change CodeChef: Practical coding for everyone that is accepted with all cases
Hey @p1god, Thanks for replying. Today I wrote a blog on codeforces regarding this, I did some optimizations and got the correct answer, but never able to comprehend the reason. Have a read at the blog.
@c0rpulent I guess it’s the constant factor. Everytime time we use sets or queue or even an additional code it adds up a constant factor well. It doesn’t mater in most problem but sometime it can.
One example where I learnt it CodeChef: Practical coding for everyone
On initial look it looks like a simple problem solvable with O(V+E) using multiple DFS runs. So that’s why I did but it still gave gave tle in couple of use cases.
Eventually I gave a look at hints and discussion for this and found out a tual solution was using two DFS instead of three. I changed code to use two(no major changes required) and it ran. Since then I keep a look at this as well.
Long story short if you have tle coming up in only one or two test cases your answer might be correct and need minor optimization. In that case try reducing the complexity of individual statement that runs multiple time seee if they can be removed or reduced to lower complexity. That’s what I learnt