There are many ways to solve this problem. One of which is described here.

All we have to do is find the maximum number of indices such that both strings have different values. We can do this by sorting one string in increasing order and another one in decreasing order. Now count of these indices gives us the number of set bits and the remaining are unset bits.

Time Complexity: $$$O(n \log n)$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	string ans = "";
	for(int i = 0; i < (int) s.size(); i ++) {
		if(s[i] != t[i]) ans += "1";
		else ans += "0";
	}
	sort(ans.begin(), ans.end());
	reverse(ans.begin(), ans.end());
	cout << ans;
	
	return 0;
}

Go for the tutorial of GS more like BS(Hard version)

Unlike in Kadane's Algorithm, we set our max_ending_here variable to zero if and only if we are on good index and max_ending_here is less than zero.

Time Complexity: $$$O(n)$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;  cin >> n;
        vector<int> arr(n), g(n);
        for(int i = 0; i < n; i ++)  cin >> arr[i];
        for(int i = 0; i < n; i ++)  cin >> g[i];
        ll max_sum_so_far = 0, max_sum = -2e18, st = -1;
        for(int i = 0; i < n; i ++) {
      	    if(g[i] == 1)	st = 1;
            if(g[i] == 1 and max_sum_so_far < 0)
                max_sum_so_far = 0;
            if(st == -1)	continue;
            max_sum_so_far += arr[i];
            max_sum = max(max_sum, max_sum_so_far);
        }
        cout << max_sum << endl;
	return 0;
}

Let us assume that the first person is the one with lowest skills. Now we iterate though all other applicants to check whether someone has skills less than the assumed one, if yes we change our person to this one, and do the same for remaining. Now, at last, we have a profile with lowest skills. Let the index of this profile is $$$x$$$. Now we check if there is someone who has less skills than the person with profile index $$$x$$$. If it is exist then the answer is straightforward $$$-1$$$, else $$$x$$$ is the answer.

Time Complexity: $$$O(n)$$$

#include "bits/stdc++.h"
using namespace std;

struct student {
    int a, b, c;
};
bool operator<(const student& t, const student& o)
{
    int cntLess = 0;
    if (t.a < o.a)
        cntLess++;
    if (t.b < o.b)
        cntLess++;
    if (t.c < o.c)
        cntLess++;
    return cntLess >= 2;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<student> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].a >> v[i].b >> v[i].c;
    }
    int id = 0;
    for (int i = 1; i < n; ++i) {
        if (v[i] < v[id]) {
            id = i;
        }
    }
    for (int i = 0; i < n; i++) {
        if (i == id)
            continue;
        if (v[i] < v[id]) {
            cout << -1 << '\n';
            return 0;
        }
    }
    cout << id + 1 << '\n';
}

Time Complexity: $$$O()$$$

~~~~~

~~~~~

We are given a forest i.e. arbitrary number of trees. All we have to do is find the diameter of all the small trees and if there are $$$x$$$ numbers of trees. Then the answer is sum of all mini diameters and $$$x-1$$$. ($$$x-1$$$ because we need x-1 edges to join all $$$x$$$ small trees).

Time Complexity: $$$O(n)$$$

#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N], height(N), vis(N), subtree;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0, connected_components = 0;

    function<void(int, int)> dfs = [&](int v, int p) -> void {
        vis[v] = 1;
        subtree.push_back(v);
        for (int u : g[v]) {
            if (u != p) {
                height[u] = height[v] + 1;
                dfs(u, v);
            }
        }
    };

    function<int(int)> find_diameter = [&](int v) -> int {
        subtree.clear();
        dfs(v, -1);
        int ls = v; // most distant node from v.
        for (int u : subtree) {
            if (height[u] > height[ls])
                ls = u;
        }
        height[ls] = 0; // new source for dfs.
        subtree.clear();
        dfs(ls, -1);
        int mx = 0; // the maximum distance from ls that will be our final answer for diameter.
        for (int u : subtree)
            mx = max(mx, height[u]);
        return mx;
    };

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            ans += find_diameter(i);
            connected_components++;
        }
    }
    ans = ans + connected_components - 1;
    cout << ans;
}

Let we are on element $$$x$$$, we must add this element to a sequence ending with element ranging from $$$0$$$ to $$$x-1$$$, and have maximum sum. We can do this by using segment/fenwick tree. And store all the elements with their corresponding maximum sum in a map.

Time Complexity: $$$O(n \log n)$$$

#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
#define int long long
int bit[N], n, a[N], m;
void update(int idx, int val, int n)
{
    while (idx <= n) {
        bit[idx] = max(bit[idx], val);
        idx += (idx & -idx);
    }
}
int query(int idx)
{
    int sum = 0;
    while (idx > 0) {
        sum = max(sum, bit[idx]);
        idx -= (idx & -idx);
    }
    return sum;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    scanf("%lld", &n);
    map<int, int> ord;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        ord[a[i]] = 0;
    }
    for (auto i : ord)
        ord[i.first] = ++m;

    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int ansh = query(ord[a[i]] - 1) + a[i];
        update(ord[a[i]], ansh, m);
        mp[a[i]] = max(mp[a[i]], ansh);
    }
    cout << query(m) << " ";
    int res = 0;
    for (auto [x, y] : mp) {
        res += (x % MOD * (y % MOD)) % MOD;
        if (res >= MOD)
            res %= MOD;
    }
    cout << res << endl;
}