Time Limits


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)
    cout << ans << endl;


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.

In this case, it is given that:
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?


Yes, that is correct.

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!

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

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