Ashish's blog

TLE in C2. Exam in BerSU (hard version) of Codeforces Round #568 (Div. 2)
By Ashish, history, 5 years ago, In English

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.

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

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

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.

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

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

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

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

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

    Got it, it should be m instead of tmax, :-)

    → Reply