Sum of Maximum GCD from two arrays. Incorrectly closed, due to memory error

Question

Yesterday we got the question Sum of Maximum GCD from two arrays.

There was some language in it that I thought was in the gray area. And so myself and the OP exchanged a comment:

I have concern with two of your sentences: "it has successfully passed some of the test cases." If it doesn't pass all the test cases, then this is unfortunately off-topic. Also "But it does throw runtime exceptions", are these intended? It doesn't, to me, look like it should. And so you may want to re-phrase the sentence, if it does work as intended. – Peilonrayz 18 hours ago

@Peilonrayz I feel it's logically correct and that's what I've tried to better. But the website that accepts my code and runs it against their test cases masks the test cases. So all I see is the reason the code failed against them - which is listed as a runtime exception - that's what I meant when I said that. It passes for my test case on my local machine. I guess what I'm looking for is for someone to tell me if there's some obvious error that I'm making in terms of array handling or something of the sort and also if this is the most optimized way of writing this code. – sinewaver 18 hours ago

The OP is correct, logically it seems correct. And the only possible error, I know of, that can be raised is a MemoryError. There are no index errors in the code, and should work correctly on any input given enough time and memory.

Looking at the constraints, we know \$N\$ is \$1 \le N \le 5 \times 10^5\$. Which means the worst case sized array will be around t = [(1000, 1000) for _ in range((5 * 10**5)**2)]. Doing some basic math, I found this to be roughly ~2275GB of RAM large. Where the OP wanted to make two to three of these.

As we all know, if this were due to getting a time limit exceeded, "“Time Limit Exceeded” and programming challenges", then it'd be on-topic. However consensus shows that if it's an out of memory error, "Does getting OutOfMemoryError really mean broken code?", then it's on-topic too.

None of the five users that voted to close the question however commented to say why they're closing. And so I can only assume it's due to my comment having two upvotes. Which doesn't actually say it's broken. And so I don't think just starting a vote to re-open this question would work. Which is why I'm requesting it be re-open on Meta. If it is on-topic.

Answer 1

This question has been re-opened in the meantime. 200_success has a great point here:

Performance and scalability are among the key concerns we frequently address. I don't see running out of memory as much different from time-limit-exceeded — they are related problems in the space-time continuum. Since we allow time-limit-exceeded questions, we should also allow questions about memory-optimization where the program runs out of memory.

While I disagree with this simplification, it may be a necessary one. The rules of the site would simply get too complicated if we don't.

First, why I disagree.

Say a piece of code takes 20 seconds to execute the worst-case scenario on the online judge's system. Good chance it will fail for time-limit-exceeded but run perfectly fine on the machine of the user who developed it.

Say a piece of code takes 130 GB of RAM to successfully execute the worst-case scenario. In most languages, it would take the same amount of RAM on any system, include that of the developers. Consumer-grade computers with that kind of hardware so rare we can safely assume the developer doesn't have one. In this specific-question, we're talking ~2275GB of RAM, like you said. In other words: the OP has never run his code on any sufficiently large input and didn't come close to testing the worst-case scenario.

The size of the input is explicitly part of the specification. The following still holds:

Code on CodeReview should work to the best knowledge of the OP. If the objective of the code is to handle 500 kB at most but the code crashes at 2 GB, the code is considered working. If those are reversed, it isn't.

Technically, it's broken code and OP should've known. Since it's too difficult to defend that to the rest of the world, I'd say: allow it anyway. Any answer targeting the memory consumption is likely to bring the amount used to decent amounts. It's perfectly re-viewable in current form for smaller inputs and answerers can take it from there.

Answer 2

Resource exhaustion (time, memory, other) doesn't necessarily mean that the program isn't ready for review.

If the program never succeeds, with even a small input set, then it obviously needs more work before review. But in this case it sounds like the question is, "My program works for these inputs; how can I make it scale better?" I consider that an on-topic question.

For this question, a good answer would probably start by examining the (limited) test cases, and showing how to improve them to actually exercise the limits given in the specification, and then move on to how the program code can be changed to help the tests pass.

I do think there's something of a problem with questions referencing "secret" test cases rather than providing their own, but I suppose that's something that won't be going away, so we'll need to learn to live with it. But we can certainly help by teaching how to generate test sets to properly stress implementations.