matcoder's blog

Does codeforces optimise O(n^2) to O(n) sometimes???
By matcoder, 6 years ago, In English

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.

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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.

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

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

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

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

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

        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?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +33 Vote: I do not like it

          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;
          → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

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

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)

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

    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;
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.me/contest/1146/submission/53061899. Submission which get AC — https://codeforces.me/contest/1146/submission/53062932

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

    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

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

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.

→ Reply