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

TLE in C2. Exam in BerSU (hard version) of Codeforces Round #568 (Div. 2)
Автор Ashish, история, 5 лет назад, По-английски

Hey there,
Problem
My Solution
I wrote a solution which uses priority queue and pops the maximum element until the sum of elements inside the priority queue is greater than (m-ti) for all 1<=i<=n, so the running time (according to me) is n*logn*max(ti) as at every pop operation the sum will reduce by atleast 1 (1<=ti<=100), logn for priority queue operations and total of n students.
When I submitted the code, it gave me TLE on test #14.
Any help is appreciated.
Thank You.

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

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

Consider the following test case. n = 2*10^5 , m = 100, time that a student spends to answer to a ticket is 100 for all students. The number of pop operations would be much greater than you counted in your time complexity.

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

Here is my submission, I have also used Priority queues(PQ). But I have used two priority queues one minPQ and one maxPQ, instead of your removed vector.

You can go thru my submission

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

Suppose n = 1e5
t[i] = 10 for all 0<=i<n
M = 11
Now while iterating you reach i = 1e5, you have 1e5 elements in your priority queue. Your while loop runs 1e5 times as you will have to pop all elements of the priority queue except last one.
So in the worst case, the complexity is n^2 log n

→ Ответить