I have solved 285C - Получаем перестановку using a greedy approach i.e sort all the values and then count the number of moves to make first element 1, the next to 2 and so on... But how can we come to the conclusion that this is always optimal and produces the minimum number of moves?

So I was learning suffix array and how to implement it. I was not able to implement it myself so I took unused code for constructing suffix array I was able to understand the initial steps but was not able to understand what is happening after the 'Start' in code below. Please help me. Thanks.

vector<int> suffix_array(const string& in) {
    int n = (int)in.size(), c = 0;
    vector<int> temp(n), pos2bckt(n), bckt(n), bpos(n), out(n);
    for (int i = 0; i < n; i++) out[i] = i; 
    sort(out.begin(), out.end(), [&](int a, int b) { return in[a] < in[b]; });
    for (int i = 0; i < n; i++) {
        bckt[i] = c;
        if (i + 1 == n || in[out[i]] != in[out[i + 1]]) c++;
    }
    /*Start*/
    for (int h = 1; h < n && c < n; h <<= 1) {// executes log n times
        for (int i = 0; i < n; i++) pos2bckt[out[i]] = bckt[i];
	for (int i = n - 1; i >= 0; i--) bpos[bckt[i]] = i;
	for (int i = 0; i < n; i++)
            if (out[i] >= n - h) temp[bpos[bckt[i]]++] = out[i];
        for (int i = 0; i < n; i++)
            if (out[i] >= h) temp[bpos[pos2bckt[out[i] - h]]++] = out[i] - h;
        c = 0;
        for (int i = 0; i + 1 < n; i++) {
            int a = (bckt[i] != bckt[i + 1]) || (temp[i] >= n - h)
                || (pos2bckt[temp[i + 1] + h] != pos2bckt[temp[i] + h]);
            bckt[i] = c;
            c += a;
        }
        bckt[n - 1] = c++;
        temp.swap(out);
    }
    return out;
}

Hi, I started studying string alg's and I did not really understand how do we construct a suffix array in O(n*log n). I can implement an O(n^2 log n) alg. But it can fail for reasonably long strings. Can someone please provide a detailed implementation (if possible with comments) of the suffix array. I saw the codes of some users but I am not able to understand anything from it. Please help me. Thanks.

I recently started learning graph theory and I completed the traversal algorithms. I am having difficulties in implementing the code which are applications of the traversal. So can anyone share their implementation of basic graph questions like

1. Check whether an undirected graph is acyclic if not print the cycle.
2. How to get all paths from a source vertex to a destination in a Directed graph.

Thanks!

Errichto has made to top 1 on the contribution panel.

214A - System of Equations Of course, we can do this using brute-force method. Does a better way exists please share it. Thanks.

Does anyone have a simpler approach of solving this problem? Please share with me.

Hello! I am unable to find any resource on implementing pick's theorem for a polygon in c++. Can anyone suggest me a site or code where i can understand it.

Thanks.