Easy Approach? Codenation Test

help
22

My approach :

I did a DFS and marked all the leaf nodes and stored in a map of int -> vector all the leaf nodes available in the current subtree.
By using prefix sum array we can find out the number of leaf nodes in the interval [l…r] in O(1)
For each query, I did a binary search on the distance between LCA and a leaf node in the current interval and for a particular distance I find it’s ancestor using DP (like in binary lifting). For that ancestor, the map will contain all the leafs present in that subtree. In that we can find the length of sub-array which contains values in the range [l…r] using BS again. If this subarray length and the number of leaves present in [l…r] are the same, then this current ancestor node is a candidate for the final answer. So I update the answer and check further for ancestor nodes with less distance in the BS.
I didn’t solve this problem within the stipulated time as I had some connectivity issues. Will this approach work ?

23

I solved this problem using segment tree and LCA.
Segment tree contained the LCA of nodes or -1 for non-leaf nodes.
After this, the queries were very simple.

4 Likes
24

That’s a cool approach.

25

What is the expected Time complexity of the question?

26

Anyone who can solve more than 3

27

Hey, can you give a bit more detail of this solution? Didnt get segment tree contained the LCA part…Also LCA was for multiple leaf nodes…how did u handle that??

28

Why LCA of 2 nodes only? You can have more than 2 leaf nodes in the given range…so you need to find lca of more than 2 leaves…how to do that??

29

what contest are you guys talking about?

2 Likes
30

O(N*log(N))

31

Make an array A where A[i] = i if i is leaf, else it is -1. Now you can easily construct a segment tree using this code:

Code 
int seg[4*200005]
void build(int cur, int l, int r, int A[])
{
         if(l == r)
         {
                seg[cur] = A[l]
                return;
         }
         int mid = (l+r)/2;
         build(2*cur, l, mid, A);
         build(2*cur+1, mid+1, r, A);
         int u = seg[2*cur], v = seg[2*cur+1];
         if(u == -1 && v == -1)
               seg[cur] = -1;
         else if(u == -1)
                seg[cur] = v;
         else if(v == -1)
                seg[cur] = u;
         else  
                seg[cur] = lca(u, v)
}

This building takes O(N*log(N)) time. After this you can answer the query in a similar way by finding LCA(L, R). Is it clear now?

2 Likes
32

okayyyyy…never knew this application of segment trees…have you done a problem like this earlier???

33

You can do it using sparse table as well . DSA learner series of basic graph contains 1 of this kind

34

bro which contest was that i didnt knew about that how u guys came to know about that contest ?

35

I am sure there will be enough people who solved more than 3 problems , so cut off for interview would be 4 problems maybe.

36

@chintustacks Just see on codeforces about the rampant cheating that happened.

37

Yeah. I used the same approach.
Were you able to solve the fourth question?

38

I didn’t take the test.

I would solve this using sparse-table and LCA precomputation as you mentioned the starting time and the ending time.

You can compute the LCA for each subarray of leaves of size - powers of 2.
Lca[L][i] = lca(L, L + 1, …, L + (2^i) - 1)
Computing the answer would also be easy. lca(Lca[L][i], Lca[R - 2^i + 1][i]).

1 Like
39

Yes, 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]. Basically consider the length of contiguous interval of j^{th} activity and you would arrive at this recurrence.
You can simplify this by defining pre[i][j] = \sum\limits_{l=1}^{i} \sum\limits_{k=1}^{j} dp[i-l][k]

1 Like
40

Yeah I replied before I saw that blog :sneezing_face:, its funny to think that many people have done 4-5 problems :cry:

41

The test was pretty tough.
3 and above should be enough without cheating but unfortunately :pensive: