maniratnagupta's blog

Problem 706B-Interesting drink
By maniratnagupta, history, 7 years ago, In English

Why my problem going time limit exceeded even I am implementing binary search my solution

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution uses Array.LastIndexOf. This Java function iterates over the complete array, so the complexity will again be O(n). Look with the binary search for the smallest element a[i] that is greater than x, then the answer is i.

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

    I am sorting then using binary Search but it is still giving TLE. Can you check this one and let me know why?

    63616723

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

      Your binary search implementation is wrong. The idea behind binary search is, that the search range gets halved each time. In your implementation you decrease the search range only by one (via left++ and right--), so the complexity is as bad as just doing a linear search.

      For a binary search you need something like left = mid + 1 instead of left++ and right = mid-1 instead of right--. But no guarantee, that this is the only mistake. I only glanced over your code for a second.

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

        Btw, that's also a very long way of writing the binary search.

        I would write it like that:

        int l = -1;
int r = list.size();
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (list.get(m) >= k)
        l = m;
    else
        r = m;
}
return l + 1;

        The idea behind my though process is: I sustain two invariants the complete program. l is the largest shop that I know of in which I can buy the candy. At the beginning I don't even know if I can buy it at the first shop, so I initialize it with l = -1. r is the smallest shop where I know that I can't buy the candy, so at the beginning it is list.size(), since I don't know if I can buy from the last one or not.

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

          I want to know, how we could have done this problem if prices at some shops would be same?

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

            Exactly the same way.

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

              But we also have to keep track of the frequency of prices ?

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

                No, that doesn't matter.

                I wrote that in my code I find the largest shop that I know of in which I can buy the candy. This is maybe a little imprecise. Correctly it should be: I find the largest index such that I can buy from the shop corresponding to the index.

                And that handles duplicates per default. E.g. if the prices are $$$2, 3, 5, 5, 6$$$ and I have $$$5$$$ coins. Then I find the index 3.

                prices:  2, 3, 5, 5, 6
indices: 0, 1, 2, 3, 4
                  ^
                → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The following is a simple C++17 implementation using upper_bound function.

37844068

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -12 Vote: I do not like it

In your binary search implementation, if x equals to arr[mid] then you are using LastIndexOf (which has O(n) complexity) that's why you are getting TLE I recently solved this problem and I faced the same problem you need to replace LastIndexOf with binary search which finds the last occurrence of any element like this one.

public static int binarySearchFindLastOccurence(int[] arr, int target) {
        int mid, right = arr.length-1, left = 0;
        int endIdx = -1;
        while (left <= right) {
            mid = left + (right-left) / 2;
            if(arr[mid] > target) {
                right = mid-1;
            }
            if(arr[mid] <= target) {
                if(arr[mid] == target) endIdx = Math.max(endIdx, mid);
                left = mid + 1;
            }
        }
        return endIdx;
    }

Please don't copy the code try to understand it. Here is my solution for further reference Solution

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

    come on man, its a 3 year old post.

    → Reply