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

Does codeforces optimise O(n^2) to O(n) sometimes???
Автор matcoder, 6 лет назад, По-английски

This is in regards to today's Forethought Future Cup contest.
I tried to hack on this solution because it seems that it's time complexity is O(n^2) where n=10^5, but somehow it takes only 170 ms (on custom tests) to run (worst case).
I am not sure if Codeforces uses some optimisation algorithm for a repetitive function call (String.substr() in this case).
Someone please help me to clarify the doubt.

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

»
6 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

My guess that substr is basically same as memcpy. It works as fast as memory speed, so it can be up to 10^11 bytes per second.

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

    What about string comparison? Shouldn't it be O(n^2) again assuming substr is fast?

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

      String comparisons work O(n) in worst case. You can count amount of operation, which program perform in your test case .

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

        I mean the overall solution. Assume that substr works in constant time. Then the solution is O(n^2). Does the compiler optimizes the comparison as well?

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

          I don't really know, but probably string comparison is optimised too(for example compares size of the strings first and then characters one by one). For this task it will be impossible to find test, where will be more than 1 comparison of strings of equal size. For example, this code works instantly, although it's $$$O((10^6)^2)$$$.

              string t;
    string s = "a";
    int cnt = 0;
    for (int i = 0; i < 1000000; i++) {
        s.push_back('a');
        t.push_back('a');
        if (s == t)
            cnt++;
    }
    cout << cnt << endl;
          → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It could possibly be a compiler optimization. Since the length of t is monotonically increasing and the length of the substring is decreasing it may be that the substring call gets optimized out except the one time it could be true: when they have the same length.

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

I believe that the == operand for strings first checks if the sizes of the lhs and rhs are equal, and only after that it checks if the strings are equal. So, it will actually do the O(N) check only once, and the overall complexity would be O(N)

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

    Yes, I think this must be the first step for checking if two strings are equal or not.
    But, actually this code (below) runs within 0.8 s too, so I believe that it doesn't matter if size(str1)==size(str2) is true or not, in case of std::substr(). There is some other reason, maybe one of the comments mentioned above. :)

            string s="",r="";
	ll l,i,cnt=0;
	for(i=0;i<100000;i++)
	{
	    r+='a';
	    s+='a';
	    l=r.size();
	    if(r.substr(0,l)==s.substr(0,l))
    	        cnt++;
	}
	cout << cnt;
    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

but when i uses substr function in my loop my code gave tle.... please tell me why my this solution gave tle.. and when i remove substr it passed... submission which get TLE — https://mirror.codeforces.com/contest/1146/submission/53061899. Submission which get AC — https://mirror.codeforces.com/contest/1146/submission/53062932

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

    Original solution can be accepted with single change, this is $$$O(\frac{n^2}{32})$$$. You should create and copy strings as minimal times as possible. Copying of string q compiler can optimize, but looks like usage of string r is unpredictable by compiler, because depends on comparison, so we just need remove creating of r.

    UPD. Got 31 ms with naive implementation of is_equal

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

Just look at the assembly. With -O2, there are some serious optimisations involved. First of all, the substr() isn't constructed by a memory copy, it just gets a forward iterator, most likely pointing to the relevant location in s. Then, some conditions are checked, which probably includes the size comparison as part of ==, and only then, there's one call to memcmp. Keep in mind that memcmp is a beast which can compare 8 characters at once, with trivial pipelining, cache access and cache prefetching. Even $$$O(N^2)$$$ would be super fast in such a case.

→ Ответить