Time Limits

General Questions
#1

Hello,

For CSES Problem Apartments: CSES - Apartments,

for the larger test cases, it gives me a time limit error

In Usaco bronze, there are also large cases, so how do I determine how much time those large test cases will take in the USACO server, and if it will pass in the 2 second time limit.

Please let me know. Thanks!

this is my code:

// https://cses.fi/problemset/task/1084

#include <bits/stdc++.h>

using namespace std;

int main()
{
    // n -  the number of applicants
    // m - the number of apartments
    // k - maximum allowed difference

    int num_app, num_apt, diff;
    int ans = 0;

    cin >> num_apt >> num_app >> diff;

    // a - the desired apartment size of each applicant
    // b - the size of each apartment

    vector<int> applicants (num_app);
    vector<int> apt_size (num_apt);

    for (int j = 0; j < num_apt; j++)
    {
        cin >> apt_size[j];
    }

    for (int i = 0; i < num_app; i++)
    {
        cin >> applicants[i];
    }


    for (int i = 0; i < num_app; i++)
    {
        for (int j = 0; j < num_apt; j++)
        {
            if (abs(applicants[i] - apt_size[j]) <= diff)
            {
                remove(v.begin(),v.end(),apt_size[j]);
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;

}
#2

Usually, you want your code to execute at most 100 million operations. Calculate the complexity of your code (In this case it’s O(NM)), and plug in the largest numbers possible.

#3

In this case, it is given that:
1≤n,m≤2⋅10^5
so O(NM) = O(4 \cdot 10 ^ {10}) = O(40,000,000,000)

it will run around 40 billion operations at worst, which is greater than 100 million. Is my understanding correct?

Thanks!

#4

Yes, that is correct.

#5

Any suggestions on how to optimize the code such that it only runs roughly a 100 million operations? Any resources or pointers would be appreciated. Thanks!

#6

This problem came from this module- I assume you read it right?

#7

I havent read it yet, because I am still doing bronze. I will check it out. Thanks!