Summary

The blog is made to discuss these two things:

1. Other ways to solve the mentioned problem (without the need of knowing the data structures mentioned in the editorial)
   
2. 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:

#include <bits/stdc++.h>
using namespace std;
#define forn(i,x,n) for(int i = x; i < n; ++i)
typedef long long ll;

vector<ll> a;

ll gcd(ll a, ll b) {
    return b? gcd(b, a%b): a;
}

int calc(int l, int r){

    if(l == r)
        return a[l] != 1;

    int mid = (l+r)/2, ans = max(calc(l, mid), calc(mid + 1, r));

    ll gc = 0, i = mid;
    unordered_map<ll,int> ml, mr;

    while(i >= l){
        gc = gcd(gc, a[i]);
        if(gc > 1)
            ml[gc] = i;
        else
            break;
        i--;
    }

    gc = 0, i = mid + 1;

    while(i <= r){
        gc = gcd(gc, a[i]);
        if(gc > 1)
            mr[gc] = i;
        else
            break;
        i++;
    }

    for(auto [y, i]: mr)
        for(auto [x, j]: ml)
            if(gcd(y, x) > 1 && ans < i - j + 1)
                ans = i - j + 1;

    ml.clear(), mr.clear();

    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, t;
    cin >> t;

    while(t--){
        cin >> n;
        a.assign(n,0);
        forn(i,0,n)
            cin >> a[i];
        n--;
        forn(i,0,n)
            a[i] = abs(a[i] - a[i + 1]);

        cout << calc(0, n - 1) + 1 << '\n';
    }
    return 0;
}

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)

I was trying 2019 ICPC Regionals contest on codechef for practice. Found it quite stragne that out of the 8 problems, only Game of ORs is not available for submission. Although the problem statement is visible, like the rest, but there is no submit button. Is this a glitch or was it removed for some reason?

I even tried to directly find the problem on codechef (here) but it just shows "Attention: Problem is not visible now. Please try again later." whereas other problems from the contest show up just fine.

I wanted to verify my solution for the problem, does anyone know any other OJ for this particular round? Or maybe if someone from codechef community has any info on this, it'll be a huge help. Thanks!

I've posted a similar discussion (link) on codechef as well, but feel that codeforces blogs have a much wider viewership and more active response.

I came across this problem in which you have been given a directed graph $$$G=(V,E)$$$ with $$$|V|,|E|\leq 10^5$$$ and one additional edge can be added to $$$E$$$. What can be the maximum size of a strongly connected component in the resulting graph?

If anyone knows an approach, do share.

Thanks.

EDIT: I apologize that the $$$O(V.(V+E))$$$ algorithm that I thought would solve this also turned out to be incorrect.

I read somewhere that the C++ STL parital_sort function (used to find k smallest numbers) has a running time complexity of O(n.logk).

It achieves this by going through the entire data, maintaining a k-sized max-heap, throwing away the top whenever size exceeds k, and in the end printing the k remaining elements from the heap.

Can't an n-sized min-heap be used instead and then the first k smallest numbers simply extracted from it. I understand it won't remain in-place and would require additional memory.

But time complexity wise, it would take O(n+k.logn) which is better than O(n.logk), right? (assuming k to be any number smaller than n)

Then why is the O(n.logk) version preferred? Why is it mentioned everywhere and used by the std template?