Qualified's blog

Why is this getting TLE?
By Qualified, 4 years ago, In English

In the new CodeForces program EDU, the first problem, linked here Problem here is my below solution. This works in

(credit to .-._._-_.-_.-._-.. for pointing out that it is O(nlog(n)) I originally put O(n) :P)

O(nlog(n))

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

string s;
vector<string> a;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(20);

	cin >> s;
	for(int i = (int)s.size() - 1; i >= 0; i--) {
		string x(1, s[i]);
		a.push_back(x);
	}
	for(int i = 1; i < (int)a.size(); i++) {
		a[i] += a[i - 1];
	}
	sort(a.begin(), a.end());
	cout << (int)s.size() << ' ';
	for(int i = 0; i < (int)a.size(); i++) {
		cout << (int)s.size() + 1 - (int)a.size() - 1 << ' ';
	}
	cout << endl;
}

Help would be greatly appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It is not actually O(n). Sorting has complexity O(n*log(n))and comparing strings is O(n). I haven't looked at the problem but maybe the intended solution must be linear whereas yours is not.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My bad, but it still should run within the time limit. 1 <= n <= 100000 so O(nlog(n)) in worst case scenario 10^5 * log(10^5) which is 10^5 * 5. Much less than 10^8.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Your solution also happens to have a high constant factor. Creating new strings, adding them to a vector using push_back (which is bad because a new copy will be created everytime), and then prefix summing up strings and sorting. Seems like it would not fit in TL according to me but I could be wrong as I've not really attempted the EDU initiative yet. Maybe someone else will help.

      Try replacing push_back with emplace_back or push_back(move(x)) so that you don't have redundant copying and check if it works. It's not likely the issue. The prefix summing of a is more likely the cause.

      Also, you updated your blog in private mode and now my first comment looks stupid as someone looking at it wouldn't know about the O(n) thing which you'd previously written.

      Also, the log in calculation should be base 2 and not 10, which makes it 5/0.301=16(approx) times 1e5.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My bad. I updated the blog to give you credit for finding my mistake. :D BTW, changing emplace_back to push_back did not help. :D

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't read it.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

First, the middle loop seems to create strings with $$$O(n^2)$$$ total size (I assume $$$n$$$ is the size of the input).

Second, the problem can't be opened unless we register for the course.

Third, using a custom dialect of C++ puts a barrier for the general public when they read your code. When you ask a question about your code and genuinely want an answer, you want to make reading it easier, not harder. Right now, the reader has to skip over most of your post, and then jump through some obscure #define hoops to understand what's going on.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think this code is O(n^2):

for(int i = 1; i < si(a); i++) {
		a[i] += a[i - 1];
}

Assuming string works similar to vector, the time complexity of adding strings should be linear in the length of the added string (i.e. the string to the right of the '+' sign) so we get the estimate of: runtime = 1 + 2 + ... + sz(s) — 1 = sz(s)/2 * (sz(s) — 1) = O(sz(s)^2).

→ Reply