bradyawn's blog

Why does this solution fail on large inputs?
By bradyawn, history, 7 years ago, In English

EDIT: Solved. It was not a problem with data structures, it was a logical error. I've been doing this greedy problem, and my solution fails on test case 6. For small inputs it seems to work, but for large inputs it produces strange results.

Problem: 854C - Planning

My Solution: https://pastebin.com/MQBNBHEJ

Someone else's accepted solution: 30195313 — They used a priority_queue while I used a sorted vector. This should achieve the same result, and I do not think it is the data structure that is the problem.

Any idea what the problem might be?

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

Comments Comments (2)
| Write comment?
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Priority queue always keeps the elements in sorted order and accessing the maximum/minimum element takes O(1) complexity and then rearranges itself in O(logn). So, basically you can access max/min in O(logn) in priority queue which is required to pass all the test cases. On the other hand if you are using vector you will have to sort it every time, each sorting takes O(nlogn). For n queries it will be O(n^2logn) which causes TLE.

You can see my submission I have used set to keep elements sorted.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I can't see your solution

→ Reply