Codechef Internship Test

general
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?

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.