Easy Approach? Codenation Test

help
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.

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