Need help with a point update and range query question

general
, , , ,
1

Given an array of ‘N’ integers, I need to perform two kinds of queries :

  1. Point update : U P : Arr[u] = P
  2. 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

2

I did it using merge sort tree but it’s as expensive as your’s solution. Did you solve the last combinatorics question?

1 Like
3
2 Likes
4

I used a set and map for duplicates in every node of a segment tree. Got TLE. Yeah, I solved the last question.

5

Thanks, but I think that has the same complexity as my solution.

6

@hemanth_1 can you please explain your approach you applied to the last question? The stars and bars method was not working for me.

7

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.

8

So, the answer for a given value ‘X’ will be (A+1)^P * (B+1)^Q - (dp[n][0]+dp[n][1]+…+dp[n][x-1])

9

Did you get 100pts for the query problem ?

10

@hemanth_1 80, TLE in 4 test cases.

11

@hemanth_1 how much did you score out of 400? Did you receive any notifications of the interview?

12

I scored 350 (lost 50 in query problem), I got a mail today saying that I got shortlisted

13

@hemanth_1 Yep, I also received an e-mail yesterday from hackerearth.Did the cogoport team call you after that?

14

@assassin28 No.

15

@hemanth_1 ok, do let me know if they call you.

1 Like
16

@hemanth_1 did they call you?

17

@assassin28 no

18

@hemanth_1 did you use merge sort tree?

19

I used a segment tree, with a set and a map in every node

20

How did you find answer to second query using this?