5 ms·

1553D is a quite confusing case though. On the AlphaCode Attention Visualization website [1], the Accepted code shown for 1553D is a O(n^2) Python one, which i

by rfoo 5y ago

1553D is a quite confusing case though. On the AlphaCode Attention Visualization website [1], the Accepted code shown for 1553D is a O(n^2) Python one, which is supposed to be TLE. It correctly implements a two-pointer solution, but failed to "realize" that list.pop(0) is O(n) in Python. I'm not sure how it passed. [1] https://alphacode.deepmind.com/#layer=30,problem=34,heads=11111111111 https://alphacode.deepmind.com/#layer=30,problem=34,heads=11...

Jensson 5y ago
Likely the python runtime has a strange string implementation for cases like this, just like javascript strings.
- Veedrac 5y ago
  It does not. Really the strings just never get long enough that O(n²) would be catastrophic; the maximum possible length is 2e5.
  - rfoo 5y ago
    2e5 is enough for making a naive O(n^2) solution to get TLE. This is likely due to the fact that in AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast.
    - Veedrac 5y ago
      > AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast. Again, it is not. CPython does not do these things. The web page says, and this is corroborated in the paper, > Solutions were selected randomly, keeping at most one correct (passes all test cases in our dataset) and one incorrect sample per problem and language. Note that since our dataset only has a limited number of test cases, passing all tests we have cannot completely rule out false positives (~4%), or solutions that are correct but inefficient (~46%). The “54th percentile” measure did use estimated time penalties, which you can see discussed in Table 4 in the paper, but 1553D was not part of that.
      - rfoo 5y ago
        > CPython does not do these things. Again, it is. https://github.com/python/cpython/blob/2d080347d74078a55c47715d232d1ab8dc8cd603/Objects/listobject.c#L707 https://github.com/python/cpython/blob/2d080347d74078a55c477... This is the memmove() I mentioned above. Like, I actually perf-d the code and confirmed this is in the hot loop. > but 1553D was not part of that. Someone submitted this 1553D code to Codeforces and it passed: https://codeforces.com/contest/1553/submission/144971343 https://codeforces.com/contest/1553/submission/144971343
        Veedrac 5y ago
        Apologies, I thought you meant ‘optimized’ in a different sense, not in terms of how list.pop is implemented, as AlphaCode wasn't involved in that. You are entirely correct that list.pop uses memmove. > Someone submitted this 1553D code to Codeforces and it passed Ah, well that shows you have a 2 second time limit, which is quite a lot of time! Not quite enough to empty a 200k element list with list.pop(0)s, but not far off; a 140k element list squeaks in under the time limit for me.

by rfoo 5y ago

Jensson 5y ago

Likely the python runtime has a strange string implementation for cases like this, just like javascript strings.

Veedrac 5y ago
It does not. Really the strings just never get long enough that O(n²) would be catastrophic; the maximum possible length is 2e5.
- rfoo 5y ago
  2e5 is enough for making a naive O(n^2) solution to get TLE. This is likely due to the fact that in AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast.
  - Veedrac 5y ago
    > AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast. Again, it is not. CPython does not do these things. The web page says, and this is corroborated in the paper, > Solutions were selected randomly, keeping at most one correct (passes all test cases in our dataset) and one incorrect sample per problem and language. Note that since our dataset only has a limited number of test cases, passing all tests we have cannot completely rule out false positives (~4%), or solutions that are correct but inefficient (~46%). The “54th percentile” measure did use estimated time penalties, which you can see discussed in Table 4 in the paper, but 1553D was not part of that.
    - rfoo 5y ago
      > CPython does not do these things. Again, it is. https://github.com/python/cpython/blob/2d080347d74078a55c47715d232d1ab8dc8cd603/Objects/listobject.c#L707 https://github.com/python/cpython/blob/2d080347d74078a55c477... This is the memmove() I mentioned above. Like, I actually perf-d the code and confirmed this is in the hot loop. > but 1553D was not part of that. Someone submitted this 1553D code to Codeforces and it passed: https://codeforces.com/contest/1553/submission/144971343 https://codeforces.com/contest/1553/submission/144971343
      - Veedrac 5y ago
        Apologies, I thought you meant ‘optimized’ in a different sense, not in terms of how list.pop is implemented, as AlphaCode wasn't involved in that. You are entirely correct that list.pop uses memmove. > Someone submitted this 1553D code to Codeforces and it passed Ah, well that shows you have a 2 second time limit, which is quite a lot of time! Not quite enough to empty a 200k element list with list.pop(0)s, but not far off; a 140k element list squeaks in under the time limit for me.