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

What is wrong with this approach?
Автор abhi204, история, 5 лет назад, По-английски

I came across a seemingly easy problem recently which is as follows:

Problem:

You want to buy a laptop. Each laptop has two parameters: Rating & Price. Your task is to buy a laptop with the highest rating within a given price range. Given Q tasks, each query consisting of price range required, you have to print the highest rated laptop that can be bought within that price range.

Input format:

The first line contains N denoting the number of inputs. The following N lines contain P & R denoting price and range of a laptop. Next line contains Q denoting the number of queries. The following Q lines contain two integers X & Y denoting the price range (inclusive). Output format: For each task Q, print the highest rating that can be bought within the range. If you cannot get any laptop within the range, print -1.

Constraints:

Sample Input:

5

1000 300

1100 400

1300 200

1700 500

2000 600

3

1000 1400

1700 1900

0 2000

Sample Output:

400

500

600

My approach:

1- Create a Map of laptops having key=price & value=rating (C++ maps are already sorted in ascending order by keys)

2- initialize result=-1

3- Take the query range as input and find the first key which belongs to this range. (If none of the keys belong in this range, return result)

4- Starting from this key, iterate over the map and take result=max(result, current rating) (Iterate until either the current key exceeds the query range OR traversal over the map is complete)

5- Return result

My problem:

This approach fails for all inputs except the given sample input. (I get Wrong Answer instead of TLE) Is there anything missing?

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

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

It can be solved using a segment tree approach.

  1. Sort all the price, rating pairs in ascending order according to price.

  2. Build a segment tree after that using the ratings of laptops.

  3. Using $$$X$$$ and $$$Y$$$, find the position of the lower bound in the array of the pair $$$ X, N$$$ where N is a negative number. Do this for $$$Y$$$ also.

  4. Find the max rating between those indices.

Code — https://pastebin.com/fqjYGuub

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
  • firstly you should sort input data in increasing order according to price,
  • then you should compress the prices(in the given list of prices and also in list of queries)
  • now the problem is how to find the range minimum in a given range with suitable complexity
  • and it can be solved using sparse table.
→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My approach is almost the same as yours (i just didn't use any data structure to optimise range query). But upon submission I am getting Wrong Answer for smaller inputs (instead of TLE)

    Is there any condition where my approach fails to solve correctly?

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

      Can you provide your code?

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

        My implementation in Python: 

        def Solve(N,Price,Rating,Q,Range):
    # write your code here 
    # return a list of answers of Q queries
    ans = {}
    returnli = []
    for i in range(len(Price)):
        ans[Price[i]] = Rating[i]
    for i in Range:
        a = i[0]
        b = i[1]
        maxel = -1
        for i in range(a, b+1):
            if i in ans.keys():
                maxel = max(maxel, ans[i])
            if (i > max(ans.keys())):
                break
        returnli.append(maxel)
    return returnli

        For small inputs, I am getting Wrong Answer instead of TLE. Thus, Considering that I would optimize time complexity using Segment tree or Sparse table. The answer would still be wrong!

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

          Your implementation may not work properly if the input contains many laptops of the same price. Also, it is not recommended to use the same iteration variable(e.g. i) in nested loops

          → Ответить