Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

abhi204's blog

What is wrong with this approach?
By abhi204, history, 5 years ago, In English

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?

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

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

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

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  • 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.
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

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

      Can you provide your code?

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

        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!

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

          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

          → Reply