abhist2's blog

Looks standard problem but how to approach? Please help.
By abhist2, history, 4 years ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Build a merge sort tree and answer queries with two binary searches. Time complexity will be $$$\mathcal{O}(Q\log^2(N))$$$.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You do realize you could've just posted the link or taken a screenshot, right?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -7 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +12 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          It would have been better if you had mentioned all of this.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks abhishek for both these approaches. I understood the first one but can you briefly elaborate on BIT approach by taking some testcase?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

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

          → Reply