Summary
The blog is made to discuss these two things:
- Other ways to solve the mentioned problem (without the need of knowing the data structures mentioned in the editorial)
- The issue of MLE and whether it depends on current memory used or the combined total.
Detail
Problems with mandatory use of Sparse Tables or Segment Trees generally don't show up so early and even if they do, they have much less solves if they're purely based on the knowledge of Sparse Tables or Segment Trees.
I wonder what ways could there be to solve 1549D - Integers Have Friends without the pre-requisite knowledge of these advanced data structures. Can anyone propose other ways which they might have tried?
One approach that I tried using divide and conquer was as follows (it's to solve the longest subarray with GCD > 1
problem, which is equivalent):
I came up with this implementation:
Unfortunately, the code is throwing an unexpected Memory Limit Exceeded error (124716291). I'm not sure if it's due to the combined memory usage exceeding the permitted limits, or whether at some point during the execution, the code is trying to take up more memory than allowed.
I am aware that as the scope ends, C++ calls destructors for STL objects, yet I even tried to clear both maps manually every time their use finished.
Is there any need for explicit freeing of memory beyond what has been done? I always thought MLEs occur when the instantaneous (and not the accumulated) memory allocation goes beyong limit at some point.
Edit:
The MLE issue got resolved. Had missed the case where array size is 0 (which is possible because it's the difference array of the input)