3 ms·

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 me

by 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

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.