count array : for a given array it stores, for each ith element number of element greater than it's value from the left.

For a given number N , there exits an permutation array (1,N) such that it gives you same count array. You are given an count array and you have to find original array.

Example : count array => 0 0 0 1 2 0

then original array would be => 1 2 5 4 3 6

Required Solution was Nlog(N).

Hope the question is clear, if there's any doubt plz comment.

For my person experience click here

I was solving some DSU question and i m not able to understand when should we do path compression and when not . For example like in these two questions .

1.Redundant Connection

class Solution {
public:
    vector<int> par,a;
    int find(int x)
    {
        if(par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges)
    {
        int n=edges.size();
        par.resize(n+1);
        for(int i=1;i<=n;i++){par[i]=i;}
        for(int i=0;i<n;i++)
        {
            int update1 = find(edges[i][0]);
            int update2 = find(edges[i][1]);
            if(update1 == update2){return edges[i];}
            else par[update1] = update2;
        }
        return a;
    }
};

2.Redundant Connection II

class Solution {
public:
    vector<int>findRedundantDirectedConnection(vector<vector<int>>& edg)
    {
        int n=edg.size();
        vector<int> par, first_edg, second_edg;
        par.resize(n+1, -1);
        unordered_map<int, int> m;
        for(auto x:edg)
        {
            if(not m.count(x[1]))m[x[1]]=x[0];
            else first_edg={m[x[1]], x[1]}, second_edg=x;
        }
        for(auto x:edg)
        {
            int a=x[0], b=x[1];
            if(par[a]==-1)par[a]=a;
            if(par[b]==-1)par[b]=b;
            if(x==first_edg)continue;
            while(par[a]!=a)
            {
                a=par[a];
                if(a==b)//if b exists in path from a to its top parent
                {
                    if(second_edg.empty())return x;
                    return second_edg;
                }
            }
            par[b]=x[0];
        }
        int a=first_edg[0], b=first_edg[1];
        while(par[a]!=a and a!=b)
        {
            a=par[a];
        }
        if(a==b)return first_edg;
        return second_edg;
    }
};

For better idea of solution 2 visit

As you can see in 2nd question while finding cycle we are not doing path compression. If anyone can explain the concept behind this it would be very helpful.

I was doing this question asked in recent HackFest in Hackerrank . I know its too simple but anyhow i m not able to score all 20 points.

string whoIsTheWinner(vector<int> v) {     
set<int> s;
for(unsigned int i=0;i<v.size();i++) s.insert(v[i]);
if(int(v.size()-s.size())%2==0 or s.size()%2==0) return "First";
return "Second"; }

Please help ..i m not able to find the solution.

I was stuck in this question Your text to link here... and the editorial doesn't seem to be much helpful to me . However in the discussion section someone explained that this is the dp formula . dp[i][j] = dp[i][j-1]*i + dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1) i m not able to understand how did he get the third term in the expression and more over i think this needs some correction as i was not able to get the right ans from this.

link for question Your text to link here... i m getting wa on testcase 11 Your text to link here... after wards i modified my solution but its not working even on testcase 1.Your text to link here... i m no where able to see where is it going wrong. If you have any other idea please describe it.. i have spend a lot of time on this question

In this problem Your text to link here... i m getting memory limit exceeded error after submitting . I have solved this question in two other ways and may be in this i may get tle even after debugging this . But i m just curious that my map will be not be constructed of more than 10^5 key values ..than why mle ? please help. submitted codeYour text to link here...