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

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.

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 — they are related problems in the space-time continuum. Since we allow questions, we should also allow questions about 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 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 , 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.

• +1, but my biggest problem is with the sentence "Consumer-grade computers with that kind of hardware so rare we can safely assume the developer doesn't have one." Whilst I only run 32GB of ram, my motherboard can go to "8 x DIMM, Max. 256GB". Also who knows give it like 20 years and your standard consumer may be running 1TB of RAM... – Peilonrayz Jul 24 '17 at 8:35
• @Peilonrayz Windows 10 won't handle more than 512GB at the moment. That's still only a fraction of what this code requires. And yes, those numbers will change over time. But we're talking about why we're closing this question now, not over 10 years. – Mast Jul 24 '17 at 10:19
• currently it looks like Linux supports from 64GB to 64/128TB of RAM. Either way, I don't think sending the message "your question is off-topic at the present moment, as I don't have X amount of RAM. Come back in Y years and this'd be a perfectly on-topic question" is that great. – Peilonrayz Jul 24 '17 at 15:01
• @Peilonrayz That's not what my commented intended to boil down to, but I understand your hesitation. – Mast Jul 24 '17 at 15:04
• Regardless of OP's desired target memory: if the code can be demonstrated to work on a small input set (I usually consider at least 5 elements a good sample, as it allows enough to prove that an arbitrary input can work, and usually falls within execution time and memory constraints) but does not work on a large input set, it's perfectly on-topic as it can be demonstrated that it works, it's just bad. (And aren't we all here to make bad code suck less?) – Der Kommissar Jul 24 '17 at 21:08
• @EBrown even when the spec specifically requires larger datasets to work as well? – Mast Jul 25 '17 at 4:44
• @Mast I usually ignore the spec, but yes. Even when it requires larger data-sets. Even in that case we know the base code works, which means the result is reproducible, and as such testable. In that case, optimizing the code and expanding to a larger test case is not a major deviation from intent. – Der Kommissar Jul 25 '17 at 11:35

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.

• We've covered whether resource exhaustion is on-topic. This is about a specific-question. – Mast Jul 25 '17 at 8:06
• I'll make my answer a little more specific, then. – Toby Speight Jul 25 '17 at 8:12
• I think my point is that we can provide good reviews for the tests, and there's value to that, even if the question is off-topic by a strict reading of the rules. I'm arguing for a bit of latitude where the shortcomings don't preclude a good answer. – Toby Speight Jul 25 '17 at 8:18