0

I have implemented the following algorithms for a competitive programming problem. But for the First method, it gives a TLE (Time Limit Exceeded).

In contrast, the second implementation was accepted as the correct answer even though its time complexity is higher than the first one since it uses the .erase method inside a loop.

May I know the reason why the second implementation was faster than the first

Please refer to the first if statement inside the while(true) loop

First Implementation (TLE)

bool isEmpty (vector<int> a) {
    sort(a.begin(), a.end());
    
    return a.size() == 0 || a[a.size() - 1] == 0;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int m, n, l;
    cin>>n>>l;
    
    vector<int> k;
    vector<int> q;
    
    for (int i=0; i<n; i++){
        int ki;
        cin>>ki;
        k.push_back(ki);
    }
    
    cin>>m;
    
    for (int i=0; i<m; i++){
        int qi;
        cin>>qi;
        q.push_back(qi);
    }
    
    vector<int> bagsNeeded;
    
    for (int qi:q){
        if (qi % l == 0){
            bagsNeeded.push_back(qi / l);
        }
        else {
            bagsNeeded.push_back((qi / l) + 1);
        }
    }
    
    sort(bagsNeeded.begin(), bagsNeeded.end());
    int i = 0;
    int c = 0;
    while(true){
        auto itr = lower_bound(bagsNeeded.begin(), bagsNeeded.end(), k[i]);

        // Difference between the two implementations is inside this if statement
        if (itr == bagsNeeded.end()){
            if (isEmpty(bagsNeeded)) break;
            else {
                int bags = k[i];
                int carriable = 0;
                int j = bagsNeeded.size() - 1;
                c++;
                while(bags > 0 && j >= 0){
                    if (bagsNeeded[j] <= bags){
                        bags -= bagsNeeded[j];
                        bagsNeeded[j] = 0;
                    }
                    else {
                        bagsNeeded[j] -= bags;
                        bags = 0;
                    }
                    j--;
                }
            }
        }
        else if (itr == bagsNeeded.begin()){
            bagsNeeded[0] -= k[i];
            if (bagsNeeded[0] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        else {
            bagsNeeded[itr - bagsNeeded.begin()] -= k[i];
            if (bagsNeeded[itr - bagsNeeded.begin()] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        i++;
        if (i == n){
            i = 0;
        }
    }
    cout<<c<<"\n";
    return 0;
}

Second Implementation (Accepted)

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int m, n, l;
    cin>>n>>l;
    
    vector<int> k;
    vector<int> q;
    
    for (int i=0; i<n; i++){
        int ki;
        cin>>ki;
        k.push_back(ki);
    }
    
    cin>>m;
    
    for (int i=0; i<m; i++){
        int qi;
        cin>>qi;
        q.push_back(qi);
    }
    
    vector<int> bagsNeeded;
    
    for (int qi:q){
        if (qi % l == 0){
            bagsNeeded.push_back(qi / l);
        }
        else {
            bagsNeeded.push_back((qi / l) + 1);
        }
    }
    
    sort(bagsNeeded.begin(), bagsNeeded.end());
    int i = 0;
    int c = 0;
    while(true){
        auto itr = lower_bound(bagsNeeded.begin(), bagsNeeded.end(), k[i]);
        if (itr == bagsNeeded.end()){
            if (bagsNeeded.size() == 0) break;
            else {
                int bags = k[i];
                int carriable = 0;
                int j = bagsNeeded.size() - 1;
                c++;
                while(bags > 0 && j >= 0){
                    if (bagsNeeded[j] <= bags){
                        bags -= bagsNeeded[j];
                        bagsNeeded.erase(bagsNeeded.begin() + j);
                    }
                    else {
                        bagsNeeded[j] -= bags;
                        bags = 0;
                    }
                    j--;
                }
            }
        }
        else if (itr == bagsNeeded.begin()){
            bagsNeeded[0] -= k[i];
            if (bagsNeeded[0] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        else {
            bagsNeeded[itr - bagsNeeded.begin()] -= k[i];
            if (bagsNeeded[itr - bagsNeeded.begin()] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        i++;
        if (i == n){
            i = 0;
        }
    }
    cout<<c<<"\n";
    return 0;
}
Shakya Peiris
  • 504
  • 5
  • 11
  • An obvious (but unrelated) optimization is to set the size (or at least the capacity) of all the vectors you use, since they will be known. That saves a lot of reallocations and copying when inserting into the vectors. – Some programmer dude Jan 29 '23 at 06:51
  • Do you know about the difference between passing by value and passing by reference? `bool isEmpty (vector a)` is passing by value (and will make copies of the vector) and `bool isEmpty (const vector& a)` passes by reference and it will NOT make copies of the vector which will be a huge time saver. Note : stop using `using namespace std;` – Pepijn Kramer Jan 29 '23 at 06:59
  • If you are interested in learning more C++ then look at [cppreference](https://en.cppreference.com/w/) for examples. Get a [recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or have a go at https://www.learncpp.com/ (that's pretty decent, and pretty up-to-date). When you've mastered the C++ basics from those sources, look at the [C++ coreguidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) regularely to keep up-to-date. I tell you this because competitive coding sites really do a bad job when it comes to teaching C++ – Pepijn Kramer Jan 29 '23 at 07:00
  • 1
    *"since it uses the .erase method inside a loop"* -- err.. both implementations use the `erase()` method inside a loop, specifically inside the loop that starts `while(true)` (which happens to be one of the longest-running loops around). – JaMiT Jan 29 '23 at 07:41
  • All complexity says is what execution time (in your case) is *proportional to* for *asymptotically large* values of relevant parameters. It is not a performance guarantee. Real-world performance also depends on a proportionality constant (what complexity is multiplied by) - which is affected by inefficient implementation. In your first example, `IsEmpty()` is an example of that, since it passes a vector by value (i.e. copies the argument each time it is called, and destroys the copy on return). I haven't checked if your code (either sample) has other inefficiencies. – Peter Jan 29 '23 at 09:20

0 Answers0