Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

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

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
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 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

→ Ответить
»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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.
→ Ответить
  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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?

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

      Can you provide your code?

      → Ответить
      • »
        »
        »
        »
        7 лет назад, скрыть # ^ |
        ← 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!

        → Ответить