Блог пользователя maniratnagupta

Problem 706B-Interesting drink
Автор maniratnagupta, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    63616723

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Exactly the same way.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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
                  ^
                → Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

37844068

→ Ответить
»
3 года назад, # |
← Rev. 3   Проголосовать: нравится -12 Проголосовать: не нравится

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

→ Ответить