Help on TLE

#1

Hi,
I was working on this problom from the USACO guide:
https://cses.fi/problemset/task/1161/

This is my code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
long long N,X;
//get sum closest to c/2
long long index(const vector<long long>& in,long long c ,const vector<long long>& psum){
    long long goal=c/2;
    auto iter=upper_bound(psum.begin(),psum.end(),goal);
    if(iter==psum.end()){
        return *--iter;
    }
    long long upper=*iter;
    long long lower=*--iter;
    if(abs(lower-goal)>abs(upper-goal)){
        return upper;
    }
    return lower;
}
int main() {
    //read input
    cin>>N>>X;
    vector<long long> in(X);
    map<long long,long long> elements;
    for(long long i=0;i<X;i++){
        long long input;
        cin>>input;
        in[i]=input;
        elements[input]++;

    }
    //input reading done
    sort(in.begin(),in.end());
    //calculate prefix sums so that we can calculate the closest numbers in logN time
    vector<long long> psum(X+1);
    for(int i=1;i<=X;i++){
        psum[i]=psum[i-1]+in[i-1];
    }

    //queue to store the sticks
    queue<long long> pq;
    pq.push(N);
    long long ans=0;
    while(!pq.empty()){
        long long top=pq.front();
        if(elements[top]>0){
            //if we have that stick length is one of the desired we can pop it and mark it as used
            elements[top]--;
        }else{
            //break the current stick
            long long f=index(in,pq.front(),psum);
            pq.push(pq.front()-f);
            pq.push(f);
            ans+=pq.front();
        }
        //pop the last one because we broke it
        pq.pop();
    }
    cout<<ans;
    return 0;
}

The time complexity is X*logX but this is at worst case and most of the time it should be well below this.
these are the results:

Screen Shot 2021-05-03 at 12.21.19 PM
Screen Shot 2021-05-03 at 12.21.19 PM1098×538 42.3 KB

I am confused on how my code is timing out and how I can fix it. Can someone please help?

Thanks.

#2

What’s the problem you’re working on?

#3

Sorry, I forgot to add it. It should be in the post now.

#4

Try rewriting your algorithm using a priority_queue. That would make your code a bit more elegant. It will also probably improve the runtime of your code.

#5

The reason I am using a queue and not a priority_queue is that a priority queue has o(log(n)
) insertion and deletion while a queue has o(1) insertion.
With priority_queue I had 0.10 second on test 3, but with queue I had 0.7 seconds

#6

Overall, wouldn’t the time complexity still be the same though? Regardless, it’d be O(n\log n).

#7

Oh yeah, you are right. But the code still gets a TLE. X is fairly small so I would assume n*logN would pass, right?

#8

Remove this after using a priority_queue

This isn’t necessary.

Rethink how you’re going to implement this.