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 at a 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 the lowest skills. Now we iterate through 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 the lowest skills. Let the index of this profile is $$$x$$$. Now we check if there is someone who has fewer skills than the person with a profile index $$$x$$$. If it exists then the answer is straightforward $$$-1$$$, else $$$x$$$ is the answer.

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

Let's say we know, there exists a lusar index at position $$$P$$$. Now If we start comparing the element from position 1 to $$$P-1$$$ and have current lusar index $$$Q$$$. $$$P$$$-th student will lose against $$$Q$$$ , making current lusar id into $$$P$$$. Nobody will lose against $$$P$$$ after that, resulting in $$$P$$$ being our final answer. (Because we know that it is our lusar element).

What if there is No lusar element? Why do we require verification for the lusar element again from the start?

Well! That's because the comparator here is not transitive. If $$$a$$$ lost to $$$b$$$ and $$$b$$$ lost to $$$c$$$ that does not imply that $$$a$$$ will lose to $$$c$$$. But If $$$c$$$ loses to $$$a$$$ here that makes one thing certain that there is no ultimate lusar between $$$a$$$,$$$b$$$, and $$$c$$$.

#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';
}

This problem can be solved using a linked-list. We can maintain a linked-list L that represents our queue currently. To handle a query of type:

1. Serve: Delete the node at the head position of the linked list.

2. Insert X Y: If we have the address of the node containing Y somewhere. We can insert a new node containing X right after Y.(See the solution for insight.)

3. Mafia X: Insert the node at the beginning of the linked list.

To store the address of the node containing string S, We can maintain a map/hashmap.

Time Complexity: $$$O(N + M \log(N)))$$$

#include "bits/stdc++.h"
using namespace std;
struct node {
    string data;
    struct node* next = NULL;
    node(string data_)
    {
        data = data_;
    }
}* head = NULL;

map<string, node*> mp;

void insert_begin(string data)
{
    //       (head,data)--->....
    //
    // (temp,data)
    node* temp = new node(data);
    mp[data] = temp;

    temp->next = head;
    //       head--->
    //		/
    // (temp)

    // temp is the new head from now on.
    head = temp;
}
void delete_begin()
{
    if (head != NULL) {
        mp.erase(head->data); // erase 1st node from map
        node* new_head = head->next; // new head will be 2nd node
        free(head); // free head memory head is null now
        head = new_head; // set head = newhead
    }
}
void insert_after(string X, string Y)
{
    node* newnode = new node(X);
    mp[X] = newnode;
    //    made (X-->NULL)

    //-- Y---Z --
    // went to node Y.
    node* temp = mp[Y];

    // set x->next = y->next
    //-- Y---Z --
    //	    /
    //	   X
    newnode->next = temp->next;

    // set y->next = x and we are done.
    //-- Y   Z --       ===>   --Y--X--Z--
    //	  \/
    //	   X
    temp->next = newnode;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string x[n];
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        insert_begin(x[i]);
    }
    int q;
    cin >> q;
    string query, X, Y;

    for (int i = 0; i < q; ++i) {
        cin >> query;
        if (query[0] == 's') {
            delete_begin(); // O(1)
        } else if (query[0] == 'i') {
            cin >> X >> Y;
            insert_after(X, Y); // O(1)
        } else {
            cin >> X;
            insert_begin(X); // O(1)
        }
    }
    while (head) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

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 the maximum sum. We can do this by using a 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;
}