5 ms·

You can find the rating distribution filtered for >5 contests here: https://codeforces.com/blog/entry/71260 https://codeforces.com/blog/entry/71260 I am rated

by gfd 5y ago

You can find the rating distribution filtered for >5 contests here: https://codeforces.com/blog/entry/71260 https://codeforces.com/blog/entry/71260 I am rated at 2100+ so I do agree that 1300 rating is low. But at the same time it solved https://codeforces.com/contest/1553/problem/D https://codeforces.com/contest/1553/problem/D which is rated at 1500 which was actually non-trivial for me already. I had one wrong submit before getting that problem correct and I do estimate that 50% of the regular competitors (and probably the vast majority of the programmers commenting in this thread right now) should not be able to solve it within 2hrs.

the-smug-one 5y ago
I'm trying to solve this for fun, but I'm stuck! I've got a recursive definition that solves the problem by building a result string. I think it's a dynamic programming problem, but right now I can't see the shared sub-problems so :). Some real sour cherries being experienced from not getting this one!
- thorwwaskeas 5y ago
  from collections import defaultdict def backspace(s1,s2): h = defaultdict(lambda:0) for x in s1: h[x] = h[x] + 1 for x in s2: h[x] = h[x] - 1 j = 0 maxj = len(s2) - 1 for x in s1: if x != s2[j]: h[x] -= 1 elif j < maxj: j += 1 else: break return j == maxj and all(y >= 0 for y in h.values()) def random_backspace(s1): res = [] for x in s1: if randint(0,1) == 0: res.append(x) return "".join(res) def backspaceTest(s1): return all(backspace(s1,random_backspace(s1)) for _ in range(100))
pedrosorio 5y ago
> But at the same time it solved https://codeforces.com/problemset/problem/1553/D https://codeforces.com/problemset/problem/1553/D To be fair, it generated a set of (10) possible solutions, and at least one of them solved the problem.
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.
johndough 5y ago
The proposed O(N²) solution contains many unnecessary operations, e.g. the creation of list c or reversal of the input strings. Maybe it has been copied from a related problem? You can easily solve the task with half as many lines in O(N). for _ in range(int(input())): a = list(input()) b = list(input()) while a and b: if a[-1] == b[-1]: a.pop() b.pop() else: a.pop() if a: a.pop() print("NO" if b else "YES")

by gfd 5y ago

the-smug-one 5y ago

I'm trying to solve this for fun, but I'm stuck! I've got a recursive definition that solves the problem by building a result string. I think it's a dynamic programming problem, but right now I can't see the shared sub-problems so :). Some real sour cherries being experienced from not getting this one!

thorwwaskeas 5y ago
from collections import defaultdict def backspace(s1,s2): h = defaultdict(lambda:0) for x in s1: h[x] = h[x] + 1 for x in s2: h[x] = h[x] - 1 j = 0 maxj = len(s2) - 1 for x in s1: if x != s2[j]: h[x] -= 1 elif j < maxj: j += 1 else: break return j == maxj and all(y >= 0 for y in h.values()) def random_backspace(s1): res = [] for x in s1: if randint(0,1) == 0: res.append(x) return "".join(res) def backspaceTest(s1): return all(backspace(s1,random_backspace(s1)) for _ in range(100))

pedrosorio 5y ago

> But at the same time it solved https://codeforces.com/problemset/problem/1553/D https://codeforces.com/problemset/problem/1553/D To be fair, it generated a set of (10) possible solutions, and at least one of them solved the problem.

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.

johndough 5y ago

The proposed O(N²) solution contains many unnecessary operations, e.g. the creation of list c or reversal of the input strings. Maybe it has been copied from a related problem? You can easily solve the task with half as many lines in O(N). for _ in range(int(input())): a = list(input()) b = list(input()) while a and b: if a[-1] == b[-1]: a.pop() b.pop() else: a.pop() if a: a.pop() print("NO" if b else "YES")