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.0k8
accept rate: 25%

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

4★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) assassin284★

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) assassin284★

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

(10 Jan, 15:55) assassin284★

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) assassin284★
(11 Jan, 22:32) hemanth_16★
1

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

(13 Jan, 12:44) assassin284★
showing 5 of 11 show all
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,197
×553
×187
×83
×39

question asked: 07 Jan, 23:57

question was seen: 311 times

last updated: 13 Jan, 12:44