Codechef Internship Test

general
39

Can someone make an editorial for the last 3 problems Please!

1 Like
40

The last 3 questions are standard one:

  • 3rd is just mutisource BFS.
  • 4th is finding LCA using Binary lifting. Practice problem
  • 5th one is finding the diameter of a tree.
3 Likes
41

Thanks ! :slight_smile:

42

Here you go,

Just store at each node the sum from root assume root as 1 to this node lets say it x.

this can be done easily as only one path exist between root and x. Now you have sum from 1 to x . stored at x

Lets say a query comes to find sum between u and v. lets say the lowest common ancestor better known as LCA of the 2 nodes is x. then answer is sum[u]+sum[v]-sum[x] as see x occurs in both the paths of u and v from root 1.

Finding LCA can be done with Euler tour and segment trees in same time and space complexity !

1 Like
43

when will results come?

44

May be a good problem for you to practice FACTRE

2 Likes
47

This post was flagged by the community and is temporarily hidden.

49

433/500 :pensive: couldn’t debug D. Still can’t find the bug. used binary lifting.
Can anyone help debug- UJ8QuW - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like
51

This post was flagged by the community and is temporarily hidden.

53

This post was flagged by the community and is temporarily hidden.

55

This post was flagged by the community and is temporarily hidden.

56

This post was flagged by the community and is temporarily hidden.

57

You might want to read this .

1 Like
58

This post was flagged by the community and is temporarily hidden.

59

Most of them solved all.

1 Like
60

There’s an edge case when both nodes lie in same path

61

Nope there isn’t

62

@admin can you please move the problems to Practise section.

1 Like
63

Can anyone send in some source which explains calculating diameter of a graph.

64

I also solve all .