### aim_cm's blog

By aim_cm, history, 2 months ago,

Hi everyone,

I need help in a question. It came to one of the contest I gave around 4 days ago. It was a hiring contest of a good indian company.

My approach was to store ai and bi as pairs in vector and sort them. So for each query we can get the count of chocolates having sweetness greater than x using binary search on vector but now how to get the count of lifetime greater than y? I got stuck here. I still couldn't think of something. Can you tell me how to approach?

It'll be really great if anyone can help me or give me some insight.

• -2

 » 2 months ago, # |   0 Auto comment: topic has been updated by aim_cm (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by aim_cm (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   +4 Build a merge sort tree and answer queries with two binary searches. Time complexity will be $\mathcal{O}(Q\log^2(N))$.
•  » » 2 months ago, # ^ |   0 Thank you so much. I didn't know about this. Will learn it right away. :D
•  » » » 2 months ago, # ^ |   +1 Here's a good tutorial: https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277
•  » » » » 2 months ago, # ^ |   +1 Oh thank you so much, That's so nice of you.
 » 2 months ago, # | ← Rev. 2 →   0 You do realize you could've just posted the link or taken a screenshot, right?
•  » » 2 months ago, # ^ |   0 I am really sorry to post the screenshots like this but it was hiring contest so link was private and taking screenshot was also not allowed I guess. Will make sure to take screenshot or take clear pictures in future.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -7 So you are cheating?Edit: Sorry for suspecting you for no reason. But it is weird that it is not legal for you to take the problem screenshot no more.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +12 It was 4 days ago and it was 1.5 hrs contest. I tried to solve it on my own even after contest but couldn't. So I just posted the question and asked for help. I dont think that's cheating as I can't do or access the question now. I think it's upsolving.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +5 It would have been better if you had mentioned all of this.
•  » » » 2 months ago, # ^ |   +5 You can also solve this problem by using an offline algorithm, sort the queries and the array based on non-increasing X. After this, the most easy way would be to use PBDS, and keep inserting values B[i] until your A[i] >= X, then just count number of elements in the PBDS which are >= Y. If you don't want to use PBDS, you can use coordinate compression on B[i] and use BIT, to calculate the same, just that you would need to binary search for index while querying on the BIT. Time complexity will be — O(QlogQ + (N + Q)logN)
•  » » » » 2 months ago, # ^ |   0 Thanks abhishek for both these approaches. I understood the first one but can you briefly elaborate on BIT approach by taking some testcase?
•  » » » » » 2 months ago, # ^ |   +2 The purpose of BIT here is to count the no. of elements > Y, i.e curr_elements in BIT-elements <= Y in the BIT. So similar to inserting element in PBDS, you will do upd(B[i], 1) in the BIT, i.e increment value at index i in the BIT by 1. If the values of B[i] lied in [1, N], we could have proceeded directly, but now, we need to compress those values into [1, N], so that we could perform our update and queries on the BIT.The only thing which you need to take care while updating and querying is that you need to find the appropriate index, and to do that, you can create a separate array C, containing sorted order of B[i], and use binary search to figure out the correct index to query in the BIT. For update you would have already done compression and have the index at hand. You can try this to do this on a sample B, like B = [10,2,-100,15,4].
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 ㅤ
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 0xF5 You have to attach the querries pair with index. So after processing queries offline, you can sort queries using index and print them.
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 ㅤ
•  » » » » » » » » » 2 months ago, # ^ |   0 Sure
•  » » » » » » 2 months ago, # ^ |   0 Ya understood it. It's somewhat similar to using BIT for inversion count problem. Thanks
 » 2 months ago, # | ← Rev. 3 →   -13 ㅤ
•  » » 2 months ago, # ^ |   0 I think the time complexity you gave is not right. Let's assume when we query we get i = 0 everytime, hence we sort (t2.begin()+0,t2.end()) which will make it nlogn. So it the complexity will become O(nlogn + Qnlogn) which will not run under 1 or 2 seconds. Let me know if I understood it wrong.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -12 ㅤ