What do you observe from the following patterns?

• $$$f(5) = 4$$$: $$$\texttt{101} \rightarrow \texttt{100}$$$
• $$$f(6) = 3$$$: $$$\texttt{110} \rightarrow \texttt{11}$$$

So you might have noticed something from Hint 0. For each operation,

• if the number is odd (the rightmost bit is 1), convert the rightmost bit to 0;
• if the number is even (the rightmost bit is 0), remove the rightmost bit.

It takes $$$1$$$ operation for a 0 bit and $$$2$$$ operations for a 1 bit (converting it to 0 then remove it).

Summing the number of operations up, the answer is $$$((\texttt{number of operations}) - 1) = ((\texttt{number of 0s}) + 2 \times (\texttt{number of 1s}) - 1)$$$.

The reason for subtracting $$$1$$$ from the result is that the program should terminate when $$$N = 0$$$ but the above algorithm counts an extra operation.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    while (t--) {
        string s;
        cin >> s;

        int ans = 0;
        for (char c : s) {
            if (c == '0') {
                ++ans;
            } else if (c == '1') {
                ans += 2;
            } else {
                throw runtime_error("invalid input");
            }
        }
        
        cout << ans - 1 << '\n';
    }
}

Assume we have to rearrange the problems, what is the optimal strategy?

Continuing from Hint 0, is the optimal strategy sorting in ascending order, descending order, or random order of the problem ratings?

Consider Rearrangement inequality

Let $$$cal(a) = \sum_{i = 1}^{n}{((n - i + 1) \times a_i)}$$$.

Consider two cases:

• Without rearranging the problems, the time spent is $$$cal(a)$$$;
• After rearranging the problems, the time spent is $$$cal(a) + k$$$.

The optimal strategy for rearranging the problems it to sort them in $$$\textbf{ascending}$$$ order.

The answer is the minimum of the two cases mentioned above.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    auto cal = [](vector<ll> &a) -> ll {
        ll sum = 0;
        int n = a.size();
        for (int i = 0; i < n; ++i) {
            sum += a[i] * (n - i);
        }
        return sum;
    };

    while (t--) {
        int n, k;
        cin >> n >> k;
        
        vector<ll> a(n);
        for (ll &i : a)
            cin >> i;

        vector<ll> b = a;
        ranges::sort(b);

        cout << min(cal(a), cal(b) + k) << '\n';
    }
}

Can the relationships be seen as a graph?

Consider the following operations:

• merging groups;
• adding or subtracting a value from a group;
• find a value in a group.

What data structure that you have learnt can be used to solve this problem?

Consider a disjoint-set data structure, the problem becomes a simple "800 implementation" problem.

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

struct DSU {
    vector<int> solved, failed, parent;

    DSU(int n) {
        solved.resize(n, 0);
        failed.resize(n, 0);
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) {
        return parent[u] == u ? u : parent[u] = find(parent[u]);
    }

    void merge(int u, int v) {
        int du = find(u), dv = find(v);
        if (du != dv) {
            parent[dv] = du;
            solved[du] = max(solved[du], solved[dv]);
            failed[du] = min(failed[du], failed[dv]);
        }
    }

    void solve(int u) {
        int du = find(u);
        ++solved[du];
    }

    void fail(int u) {
        int du = find(u);
        ++failed[du];
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    DSU dsu(n + 1);

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int u, v;
            cin >> u >> v;
            dsu.merge(u, v);
        }

        else if (op == 2) {
            int u, e;
            cin >> u >> e;
            if (e == 0) {
                dsu.fail(u);
            } else {
                dsu.solve(u);
            }
        }

        else if (op == 3) {
            int u;
            cin >> u;
            int du = dsu.find(u);
            cout << dsu.solved[du] << ' ' << dsu.failed[du] << '\n';
        }

        else {
            throw invalid_argument("Invalid operation");
        }
    }
}