Codechef Internship Test

general
23

ohh it was straightforward problem. idk what i was thinking. :frowning:

24

Ceil of half diameter.

25

Sure, so for each node assign the weight of itā€™s parent edge to it. And then precompute for the sum of all assigned values of nodes in the path from root to every node. Now for any 2 nodes. We can calculate the answer as ->
a[i]= weight of the edge connecting node i and itā€™s parent
S_i= Set of all nodes in the shortest path from root to i_{th} node
p[i] =\sum_{j \in S_i}a[j]
for any u,v ,
ans_{u,v}=p[u]+p[v]-2*p[lca(u,v)]

1 Like
26

yaa , did the same , but didnā€™t work

1 Like
27

Yes, it was well known problem. Thank you :slight_smile:

28

Can you please post your solution. I did the same thing but I still got wrong answer.

29

I guess you may have got WA due to int as i got he same.Converting weights array to long long worked for me.

30

anyone know about selection criteria for coding round of last year ?

2 Likes
31

will the ranklist made public?

32

orz

33

Last year it wasnā€™t made public. I suppose the same trend is going to follow.

34

Questions were too easy and standard. I solved all in 45 minutes. Still I donā€™t have hopes of selection. Most probably 600-700 people would have scored full.

1 Like
35

Got 415 points, didnā€™t know about binary lifting or LCA using sparse table.
Was anyone able to do 4th one with Python?

36

LCA on tree is very basic concept. 4th question is the first problem one encounters when they study LCA concept,in trees,in general.

So I think it was known to most and quite popularā€¦

I even had template for it so I just blind submitted as soon as I saw it.

1 Like
37

you can do using euler tour and segment trees with dfs also Binary lifting is not the only way!

1 Like
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?