Блог пользователя Qualified

Why is this getting TLE?
Автор Qualified, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can't read it.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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).

→ Ответить