LelouchRiBritannia's blog

By LelouchRiBritannia, history, 8 years ago, In English

Today I submit the solution for : Problem I — Gym 101061 using scanf/printf and it gives me TLE (Time limit exceeded on test 2). This is my solution:

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

const int MAX = 1e5 + 10;

int T;
char s1[MAX], s2[MAX];
int c1[30], c2[30];

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%s", s1);
        scanf("%s", s2);

        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));

        for(int i = 0; i < (int)strlen(s1); i++) c1[s1[i] - 'a']++;
        for(int i = 0; i < (int)strlen(s2); i++) c2[s2[i] - 'a']++;

        int res = 0;
        for(int i = 0; i < 26; i++) res += abs(c1[i] - c2[i]);

        printf("%d\n", res);
    }
}

But when I change to cin/cout, I get AC in 15ms. This is the second solution:

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

#define endl '\n'

int T;
string s1, s2;
int c1[30], c2[30];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> T;
    while(T--){
        cin >> s1 >> s2;

        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));

        for(int i = 0; i < (int)s1.size(); i++) c1[s1[i] - 'a']++;
        for(int i = 0; i < (int)s2.size(); i++) c2[s2[i] - 'a']++;

        int res = 0;
        for(int i = 0; i < 26; i++) res += abs(c1[i] - c2[i]);

        cout << res << endl;
    }
}

I'm used to scanf/printf because I think it's fast but this time brings a huge doubt. Can anybody explain this for me? Is it because in cin/cout solution I use cin.tie(NULL)?

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

The huge difference doesn't come from I/O.

Actually, time complexity of strlen() is O(n) while size() is O(1).

Thus, time complexity of first one is O(n2) which will definitely get TLE.

»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

You can store the sizes of s1 and s2 in separate variables before looping, then your solution still remains O(n).