What is it's time complexity?

general
,
1

image
As you can see in the above picture that I got an AC in the problem ABCDEF of SPOJ with a time of 2.64 seconds but on the problem page the time limit is mentioned as 1 second. Then why did I get an AC?

2

unexpected good things happen to good people i guess lol

4 Likes
3

I also got AC at 6 sec for some other question. Its time limit was 1 s.

1 Like
4

Here is my code for the problem:

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)

int main()
{
    FASTIO
    int n;
    cin >> n;
    vector<int> s(n);
    rep(i,0,n) cin >> s[i];
    map<int,int> x, y;
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            rep(k,0,n)
            {
                x[s[i]*s[j]+s[k]]++;
            }
        }
    }
    rep(i,0,n)
    {
        if(s[i] == 0) continue;
        else
        {
            rep(j,0,n)
            {
                rep(k,0,n)
                {
                    y[s[i]*(s[j]+s[k])]++;
                }
            }
        }
    }
    int ans = 0;
    for(auto i = x.begin(); i != x.end(); i++)
    {
        auto j = y.find(i->first);
        if(j != y.end()) ans += (i->second)*(j->second);
    }
    cout << ans << "\n";
    return 0;
}

If I am not wrong then the time complexity for this solution should be 3*(n^3)*log(n), and it is well enough for the given constraints. So I don’t understand why the time is 2.64 seconds whereas the time should be within 1 second as per the time complexity.

5

Have I calculated the time complexity correctly?

6

I think so

7

I think SPOJ reports the total time taken over all test files, not the maximum. I can’t seem to find the source for this anymore, but it makes sense, at least.

2 Likes
8

@galencolin Is my calculation of the time complexity correct?

9

I think so