Easy Approach? Codenation Test

help
1

Given a tree with N nodes rooted at 1 and Q queries of the type L, R. Consider all leaves with labels lying between L and R. Find their lowest common ancestor.
My approach: Using dfs tour, we can find the minimum starting time and maximum ending time for leaves lying in range [L, R] in O(log(N)). Let’s say the times are S and E, now I need to find a node such that its starting time < S and ending time > E. Also the nodes are stored as \{S_i, E_i\} where S_i, E_i denote starting and ending time. Since values are sorted according to S_i in dfs tour, I need to find a value > E in range calculated before. This can be done using segment tree.
Is there some other easy approach? @carre @everule1
UPD: Answer would be LCA of the two nodes.

2 Likes
2

Hi, this is what i think… (I am not sure that this works though)
Let original LCA = 1;
Initially store all the visiting times of the vertices. Vis[i] represents the time at which node i is visited.
Consider for each node that it is temporarily the LCA. and let start and end times of present node are {S, E}. Let Mi and Ma be the min and max visiting times of the leaves in range L to R. then check this condition (Mi >= S && Ma <= E), if this condition satisfies then update the original LCA with this temporary LCA, then traverse through the childs and do the same. Finally you will get the original LCA.
for finding Mi and Ma we can use sparse table or seg tree.

UPD : This will not work as there are Q queries, my bad.

3

How many were you able to solve, 5 problems?

1 Like
4

Nope, only 3, I was completing this one but got errors. I didn’t observe that LCA thing during the contest and spent a lot of time in Problem 1.
What about you?

5

Did you solve the n days m activity one? or the 1st one?

6

Yes, in 4th define dp[i][j] as number of ways to organize activities in [1..i] with j^{th} activity on i^{th} day. The recurrence becomes: dp[i][j] = \sum\limits_{l=1}^{B_j}\sum\limits_{k=1}^{m} dp[i-l][k] - \sum\limits_{l=1}^{B_j}dp[i-l][j]. You can simplify this by defining pre[i][j] = \sum\limits_{l=1}^{i} \sum\limits_{j=1}^{m} dp[i-l][j]
First one, I couldn’t simplify the O(N^3) DP. Do you have any idea?

1 Like
7

How many problems you re able to solve?

8

Same, only 3 :sob: I got the approach for this one but was also not able to find lca and and for the dp one with prefix sums (3 one) i had a different dp state than yours and I was not able to find what was wrong with it as it was giving correct on some cases and wrong on some :joy:, overall I am a clown :clown_face:

9

Cool, Guess I have to work hard on my DP skills :disappointed_relieved:

10

Only 2 . :sob: :sob:

1 Like
11

Did you solve first one? The conveyor belt one?

12

it is the exact same, I remember this problem very well as it was one of the first problem that I did when I was learning dp :rofl: :rofl:

4 Likes
13

This was the 4th problem(Vacations problem)

1 Like
14

I think I misunderstood the problem :confused: :confused:

15

I wasted a lot of my time on 1st doing some stupid 2D prefix sum stuff only to realise at the end that it was totally incorrect

16

Yeah the statement is very confusing as there are many conditions but the solution is quite small.

17

Same, wasted 40-50 mins :disappointed_relieved:

18

Same thing happened with me :cry:

20

@tiasmondal The statement was very confusing, I also assumed this. Check this problem SPOJ.com - Problem MARTIAN. Thanks to @agru for clarifying it.

21

Thanks, for sharing, yes statement was really confusing, also the samples were very weak.
If they could have even given the image present in the martian question lol, there would have been no way to misunderstand the question lol. The image says everything.