Given an array of ‘N’ integers, I need to perform two kinds of queries :
- Point update : U P : Arr[u] = P
- Given a L,R,P I need to find the smallest number in the range [L,R] that is greater than P.
There are ‘Q’ queries.
This question was in a Hiring challenge on Hackerearth (Challenge is over now) so I can’t provide a link to the statement. I want to know if this problem can be solved with complexity better than Q*Log^2N
I did it using merge sort tree but it’s as expensive as your’s solution. Did you solve the last combinatorics question?
I used a set and map for duplicates in every node of a segment tree. Got TLE. Yeah, I solved the last question.
Thanks, but I think that has the same complexity as my solution.
@hemanth_1 can you please explain your approach you applied to the last question? The stars and bars method was not working for me.
Let dp[i][j] be the number of ways to take ‘j’ items in the first ‘i’ boxes.
Since the limit for each box is ‘A’ for the first ‘P’ boxes, if i <= P, then:
dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+…+dp[i-1][j-A], because you can take 0 to ‘A’ items from the ith box, and the rest must come from the previous ones. For i>P you can take the summation based on ‘B’. I calculated this upto 1000 items. Now, you need to count number of ways to get sum >= X, so I calculated all possible ways and subtracted the number of ways to get sum <X using the dp table. There will be (A+1)^P * (B+1)^Q different ways.
So, the answer for a given value ‘X’ will be (A+1)^P * (B+1)^Q - (dp[n]+dp[n]+…+dp[n][x-1])
Did you get 100pts for the query problem ?
@hemanth_1 80, TLE in 4 test cases.
@hemanth_1 how much did you score out of 400? Did you receive any notifications of the interview?
I scored 350 (lost 50 in query problem), I got a mail today saying that I got shortlisted
@hemanth_1 Yep, I also received an e-mail yesterday from hackerearth.Did the cogoport team call you after that?
@hemanth_1 ok, do let me know if they call you.
@hemanth_1 did they call you?
@hemanth_1 did you use merge sort tree?
I used a segment tree, with a set and a map in every node
How did you find answer to second query using this?