5 ms·

Relevant blogpost on codeforces.com (the competitive programming site used): https://codeforces.com/blog/entry/99566 https://codeforces.com/blog/entry/99566 Ap

by gfd 5y ago

Relevant blogpost on codeforces.com (the competitive programming site used): https://codeforces.com/blog/entry/99566 https://codeforces.com/blog/entry/99566 Apparently the bot would have a rating of 1300. Although the elo rating between sites is not comparable, for some perspective, mark zuckerberg had a rating of ~1k when he was in college on topcoder: https://www.topcoder.com/members/mzuckerberg https://www.topcoder.com/members/mzuckerberg

baobabKoodaa 5y ago
The median rating is not descriptive of median ability, because a large number of Codeforces competitors only do one or a few competitions. A very small number of competitors hone their skills over multiple competitions. If we were to restrict our sample to competitors with more than 20 competitions, the median rating would be much higher than 1300. It's amazing that Alphacode achieved a 1300 rating, but compared to humans who actually practice competitive coding, this is a low rating. To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down.
- 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")
- YeGoblynQueenne 5y ago
  >> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode tested, solved 25% of the easiest tasks ("introductory") and less than 10% of the intermediary ("interview") and advanced ("competition") tasks. What's more, the approach that AlphaCode takes to program generation is primitive. It generates millions of candidate programs and then it "filters" them by running them against input-output examples of the target programs taken from the problem descriptions. The filtering still leaves thousands of candidate programs (because there are very few I/O examples and the almost random generation can generate too many programs that pass the tests, but still don't solve the problem) so there's an additional step of clustering applied to pare this down to 10 programs that are finally submitted. Overall, that's a brute-force, almost random approach that is ignoring entire decades of program synthesis work. To make an analogy, it's as if DeepMind had just published an article boasting of its invention of a new sorting algorithm... bubblesort.
  - sytelus 5y ago
    Aren't you missing the point that even though success percentage is low, it is still same as estimated average human performance? So it is impressive the overall system (however cluncky it is) is indeed able to match human performance. If you don't find this impressive, do you have any other example of system that exceeds this performance?
    - YeGoblynQueenne 5y ago
      To clarify, the low percentage of 25% of correct solutions is on the APPS dataset, not against human coders. See table 10 (page 21 of the pdf) on the arxiv paper if you are unsure about the difference: https://storage.googleapis.com/deepmind-media/AlphaCode/competition_level_code_generation_with_alphacode.pdf https://storage.googleapis.com/deepmind-media/AlphaCode/comp... Evaluation against the average competitor on Codeforces is not the "estimated average human performance", it's only the average of the coders on Codeforce who are an unknown proportion of all human coders with an unknowable level of coding ability. So evaluating against that is actually a pretty meaningless metric. The benchmarking against APPS is much more meaningful but the results are pretty poor and so they are omitted from the article above. So, no. I'm not missing the point. Rather, the article above is eliding the point: which is that on the one meaningful evluation they attempted, their system sucks. Edit: Here's table 10, for quick reference: Filtered From (k) Attempts (k) Introductory Interview Competition n@k n@k n@k GPT-Neo 2.7B N/A 1 3.90% 0.57% 0.00% GPT-Neo 2.7B N/A 5 5.50% 0.80% 0.00% Codex 12B N/A 1 4.14% 0.14% 0.02% Codex 12B N/A 5 9.65% 0.51% 0.09% Codex 12B N/A 1000 25.02% 3.70% 3.23% Codex 12B 1000 1 22.78% 2.64% 3.04% Codex 12B 1000 5 24.52% 3.23% 3.08% AlphaCode 1B N/A 1000 17.67% 5.24% 7.06% AlphaCode 1B 1000 5 14.36% 5.63% 4.58% AlphaCode 1B 10000 5 18.18% 8.21% 6.65% AlphaCode 1B 50000 5 20.36% 9.66% 7.75% And its caption: Table 10 | n@k results on APPS. If there is no filtering, then n = k and the metric is pass@k. Finetuned GPT-Neo numbers reported from Hendrycks et al. (2021), Codex numbers from Chen et al. (2021). We used a time limit of 3 seconds per test to match Codex 12B, and report average numbers over 3 different fine-tuning runs for AlphaCode. Edit 2: And now that I posted this, I note that the 25% solutions are from Codex. AlphaCode's best result was 20%.
shihab 5y ago
For comparison, I used to be a very average, but pretty regular user about 5 years ago. I could reliably solve easiest 2 out of 5 problems, 3 in my lucky days. My rating is 1562.

by gfd 5y ago

baobabKoodaa 5y ago

The median rating is not descriptive of median ability, because a large number of Codeforces competitors only do one or a few competitions. A very small number of competitors hone their skills over multiple competitions. If we were to restrict our sample to competitors with more than 20 competitions, the median rating would be much higher than 1300. It's amazing that Alphacode achieved a 1300 rating, but compared to humans who actually practice competitive coding, this is a low rating. To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down.

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")
YeGoblynQueenne 5y ago
>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode tested, solved 25% of the easiest tasks ("introductory") and less than 10% of the intermediary ("interview") and advanced ("competition") tasks. What's more, the approach that AlphaCode takes to program generation is primitive. It generates millions of candidate programs and then it "filters" them by running them against input-output examples of the target programs taken from the problem descriptions. The filtering still leaves thousands of candidate programs (because there are very few I/O examples and the almost random generation can generate too many programs that pass the tests, but still don't solve the problem) so there's an additional step of clustering applied to pare this down to 10 programs that are finally submitted. Overall, that's a brute-force, almost random approach that is ignoring entire decades of program synthesis work. To make an analogy, it's as if DeepMind had just published an article boasting of its invention of a new sorting algorithm... bubblesort.
- sytelus 5y ago
  Aren't you missing the point that even though success percentage is low, it is still same as estimated average human performance? So it is impressive the overall system (however cluncky it is) is indeed able to match human performance. If you don't find this impressive, do you have any other example of system that exceeds this performance?
  - YeGoblynQueenne 5y ago
    To clarify, the low percentage of 25% of correct solutions is on the APPS dataset, not against human coders. See table 10 (page 21 of the pdf) on the arxiv paper if you are unsure about the difference: https://storage.googleapis.com/deepmind-media/AlphaCode/competition_level_code_generation_with_alphacode.pdf https://storage.googleapis.com/deepmind-media/AlphaCode/comp... Evaluation against the average competitor on Codeforces is not the "estimated average human performance", it's only the average of the coders on Codeforce who are an unknown proportion of all human coders with an unknowable level of coding ability. So evaluating against that is actually a pretty meaningless metric. The benchmarking against APPS is much more meaningful but the results are pretty poor and so they are omitted from the article above. So, no. I'm not missing the point. Rather, the article above is eliding the point: which is that on the one meaningful evluation they attempted, their system sucks. Edit: Here's table 10, for quick reference: Filtered From (k) Attempts (k) Introductory Interview Competition n@k n@k n@k GPT-Neo 2.7B N/A 1 3.90% 0.57% 0.00% GPT-Neo 2.7B N/A 5 5.50% 0.80% 0.00% Codex 12B N/A 1 4.14% 0.14% 0.02% Codex 12B N/A 5 9.65% 0.51% 0.09% Codex 12B N/A 1000 25.02% 3.70% 3.23% Codex 12B 1000 1 22.78% 2.64% 3.04% Codex 12B 1000 5 24.52% 3.23% 3.08% AlphaCode 1B N/A 1000 17.67% 5.24% 7.06% AlphaCode 1B 1000 5 14.36% 5.63% 4.58% AlphaCode 1B 10000 5 18.18% 8.21% 6.65% AlphaCode 1B 50000 5 20.36% 9.66% 7.75% And its caption: Table 10 | n@k results on APPS. If there is no filtering, then n = k and the metric is pass@k. Finetuned GPT-Neo numbers reported from Hendrycks et al. (2021), Codex numbers from Chen et al. (2021). We used a time limit of 3 seconds per test to match Codex 12B, and report average numbers over 3 different fine-tuning runs for AlphaCode. Edit 2: And now that I posted this, I note that the 25% solutions are from Codex. AlphaCode's best result was 20%.

shihab 5y ago

For comparison, I used to be a very average, but pretty regular user about 5 years ago. I could reliably solve easiest 2 out of 5 problems, 3 in my lucky days. My rating is 1562.