You are not logged in. Please login at www.codechef.com to post your questions!

×

Need help with a point update and range query question

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

asked 07 Jan, 23:57

hemanth_1's gravatar image

6★hemanth_1
1.3k9
accept rate: 26%

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

(08 Jan, 12:01) hemanth_16★

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

link

answered 08 Jan, 03:48

assassin28's gravatar image

1★assassin28
102
accept rate: 0%

edited 08 Jan, 03:53

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

(08 Jan, 11:59) hemanth_16★

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

(08 Jan, 17:48) assassin281★

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.

(09 Jan, 16:19) hemanth_16★

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])

(09 Jan, 16:22) hemanth_16★

Did you get 100pts for the query problem ?

(09 Jan, 16:23) hemanth_16★

@hemanth_1 80, TLE in 4 test cases.

(09 Jan, 17:36) assassin281★

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

(10 Jan, 15:55) assassin281★

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

(10 Jan, 21:09) hemanth_16★

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

(11 Jan, 19:15) assassin281★
(11 Jan, 22:32) hemanth_16★
1

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

(13 Jan, 12:44) assassin281★

@hemanth_1 did they call you?

(21 Jan, 03:11) assassin281★
(21 Jan, 23:45) hemanth_16★
showing 5 of 13 show all
Answer is hidden as author is suspended. Click here to view.

answered 10 Jan, 11:41

sameenamahin's gravatar image

0★sameenamahin
(suspended)
accept rate: 0%

@hemanth_1 did you use merge sort tree?

link

answered 22 Jan, 01:01

akash_321's gravatar image

4★akash_321
665
accept rate: 0%

edited 22 Jan, 01:01

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

(22 Jan, 14:14) hemanth_16★

How did you find answer to second query using this?

(22 Jan, 15:41) akash_3214★

You need to find the smallest number > P in [L,R]. Since there is a set in every node of the segment tree, you can use upper_bound to find the smallest number > P in the range for that node. Since every query will visit at most O(logN) nodes, you only need to do this those many times. Finally, you will return the minimum of all upper_bounds that you found in all the nodes that you checked.

(24 Jan, 21:29) hemanth_16★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,302
×760
×202
×131
×53

question asked: 07 Jan, 23:57

question was seen: 674 times

last updated: 24 Jan, 21:29